Ccmmutty logo
Commutty IT
・5 min read

ABC225 茶色コーダーが解けた所まで

AtCoder競技プログラミングアルゴリズム
https://picsum.photos/seed/aabd4d1e1e104bc488afdbe5dfcdce19/600/800

AtCoder Beginner Contest 225

ABC225の問題を、本番で自分が解けた所までの解説です。
94分で4完＋3WA。残り数分で何故かF問題に特攻するも無事玉砕。 茶diffまではもっと安定させたいですね。

A - Distinct Strings

Difficulty: 12

if文で条件分岐してあげる(想定解法、スマート）

3つのパターンに場合分けしてあげると良し
  • Sに含まれる3文字が全て同じである
    • 答えは明らかに1通り
  • そうではなく、Sに含まれる3文字が互いに異なる
    • 答えは3!=6通り
  • 上記2つのどちらでもない場合、Sは2文字が等しい＋1文字だけ異なる文字で構成されている
    • 答えは3通り

想定解

python
# 入力
S = input()

# 3文字全て同じパターン
if S[0] == S[1] == S[2]:
    print(1)
# 3文字全てが互いに異なるパターン
elif S[0] != S[1] and S[1] != S[2] and S[2] != S[0]:
    print(6)
# 2文字等しい+異なる1文字のパターン
else:
    print(3)

力技（本番で恥ずかしげもなくこちらを提出）

python
# 入力
S = input()

# パターン作成
L = []
a = S[0]+S[1]+S[2]
b = S[0]+S[2]+S[1]
c = S[1]+S[2]+S[0]
d = S[1]+S[0]+S[2]
e = S[2]+S[0]+S[1]
f = S[2]+S[1]+S[0]
L.append(a)
L.append(b)
L.append(c)
L.append(d)
L.append(e)
L.append(f)

# setに直して重複排除
s = set(L)

# 要素数が答え
print(len(s))

B - Star or Not

Difficulty: 62

グラフ理論のお話

  • 木とか、頂点とか、枝とかの説明はwiki参照…余裕があったら整理して纏めたい…。

結局どういう問題？

  • 頂点の数と、頂点の数より1つ少ない辺（＝どの2点が結ばれているか）の情報が与えられます
  • 与えられた情報からできたグラフの形が、
    • 「どこか1つの頂点と、他すべての頂点に1本ずつ辺が結ばれているか」を判定してください
    • 「他全ての頂点（N-1)の数、辺が繋がれている頂点はありますか？」と言い換えても良いかもしれません
python
# 頂点数入力
N = int(input())

# 辺接続数格納用のリスト
L = [0]*(N+1)  # 0-indexに直したいため、要素数：N+1の配列

# 辺情報入力
for i in range(N-1):
    a, b = map(int, input().split())
    # 頂点a,bの辺接続数をインクリメント
    L[a] += 1
    L[b] += 1

# もし、「一番多く辺が接続されている頂点に、接続されている辺の数」が、N-1（ほか全ての頂点の数）本であれば、Yes。そうでないならNo
if max(L) == N-1:
    print('Yes')
else:
    print('No')

C - Calendar Validator

Difficulty: 326

タイトルから推察

  • カレンダーバリデーター：カレンダー検証機…？
  • 左上が1のカレンダー、最終日が(10100×710^{100} \times 7)日のものを考える
    • その縦長なカレンダーから、入力された行列Bが切り出せるかの判定

カレンダーの切り抜きであるために必要な条件を考える

  1. 特定の要素Bi,jB_{i,j}は、1つ左の要素Bi,j−1B_{i,j-1}に1を足した値であること
  2. 特定の要素Bi,jB_{i,j}は、1つ上の要素Bi+7,jB_{i+7,j}に7を足した値であること
  3. 7の倍数が出てきて良いのは、最終列だけ
python
# 入力部
N, M = map(int, input().split())
L = []
for i in range(N):
    tmp_L = list(map(int, input().split()))
    L.append(tmp_L)

# 1要素ずつ確認していく
for i in range(N):
    for j in range(M):

        # 1つ左の要素 + 1 = 今の要素でないなら、それはカレンダーの切り抜きではない
        if j != 0:
            if L[i][j - 1] + 1 != L[i][j]:
                print('No')
                exit()

        # 1つ上の要素 + 7 = 今の要素でないなら、それはカレンダーの切り抜きではない
        if i != 0:
            if L[i - 1][j] + 7 != L[i][j]:
                print('No')
                exit()

        # 最終列以外で、値が7の倍数であるなら、それはカレンダーの切り抜きではない
        if j != M-1:
            if L[i][j] % 7 == 0:
                print('No')
                exit()

# 全要素問題なければ、それはカレンダーから切り出したものである
print('Yes')

D - Play Train

Difficulty: 778

データの管理方法

  • 特定の電車に対して、
    • 電車iの前に繋がっている電車は？
    • 電車iの後ろに繋がっている電車は？
  • この2つを、それぞれの配列で管理する
  • クエリ3が来たら、前に繋がっている電車と後ろに繋がっている電車を芋づる式に引っ張り出す
python
from collections import deque

# 入力
N, Q = map(int, input().split())

# 前に繋がっている電車、後ろに繋がっている電車管理用配列
front_L = [-1] * (N + 1)
back_L = [-1] * (N + 1)

for i in range(Q):
    query_L = list(map(int, input().split()))

    # クエリ1：連結
    if query_L[0] == 1:
        x, y = query_L[1], query_L[2]
        front_L[y] = x # yの前に繋がっている電車はx
        back_L[x] = y # xの後ろに繋がっている電車はy

    # クエリ2：分離
    if query_L[0] == 2:
        x, y = query_L[1], query_L[2]
        front_L[y] = -1 # yの前に繋がっている電車は存在しない
        back_L[x] = -1 # xの前に繋がっている電車は存在しない

    # クエリ3：出力
    if query_L[0] == 3:
        
        # 前に繋がっている電車、後ろに繋がっている電車を追加していくのでqueで左右から足していく
        que = deque()
        x = query_L[1]
        que.append(x) # 最初に注目している電車
    
        # 前に繋がっている電車を芋づる式に求める
        while True:
            x = front_L[x] # 電車xの前に繋がっている電車を新たにxと置く
            if x == -1: # もし、前に何も繋がっていないならそこで芋づる終了
                break
            que.appendleft(x) # queの左側に追加
        
        # クエリで入力された電車xに値を戻して…
        x = query_L[1]
        
        # 後ろに繋がっている電車を芋づる式に求める
        while True:
            x = back_L[x] # 電車xの後ろに繋がっている電車を新たにxと置く
            if x == -1: # もし、後ろに何も繋がっていないならそこで芋づる終了
                break
            que.append(x) # queの右側に追加
            
        # queをリストに直して、長さと一緒に出力
        output_L = list(que) 
        print(len(output_L), *output_L)

Discussion

コメントにはログインが必要です。