ABC209 参加記録
- 4完1ペナ 22分でした
A - Counting
のとき、答えは
個です。問題文の制約を見ると
の場合も普通にあるのでそのときだけ気をつけます。（ここで 1ペナもらいました。勿体無い。。）
A, B = map(int, input().split()) if A <= B: print(B-A+1) else: print(0)
B - Can you buy them all?
なので、純粋に一個一個代金を足し合わせて、最後に所持金
と比較すれば間に合います。
N, X = map(int, input().split()) A = list(map(int, input().split())) res = 0 for i in range(N): res += (i%2 == 0) * A[i] + (i%2 == 1) * (A[i] - 1) if res <= X: print('Yes') else: print('No')
C - Not Equal
そのままやろうとすると調べ上げるのに時間がかかってしまいます。
まず、この問題の条件を調べ上げるにあたって、 の順番は特に関係ないことがわかります。
次に、一度使った数字が使えないことから、
が大きいときよりも、小さいときの方が使える候補が少なく、強い制約であることがわかります。
数え上げでは、強い制約から考えていくとうまくいく場合があります。今回の問題は を小さい順に並べてから使って良い数字をカウントしていくと、場合分けなどせずに数え上げることができます。
MOD = pow(10,9)+7 N = int(input()) C = list(map(int, input().split())) C.sort() cnt = 0 ans = 1 for c in C: ans *= c - cnt if c - cnt == 0: print(0) return ans %= MOD cnt += 1 print(ans)
D - Collision
道路の長さが同じということから、街どうしを結ぶ最短経路の道路の本数が偶数なら街で出会い、奇数なら道路で出会います。 与えられるグラフは木になっているので、適当な頂点から BFS などで距離を求めて、高橋くん、青木くんの出発点の値の偶奇が一致しているかどうかで判定することができます。
提出コード
from collections import deque import sys input = sys.stdin.readline def main(): N, Q = map(int, input().split()) graph = [[] for _ in range(N)] for _ in range(N-1): a, b = map(int, input().split()) a -= 1; b -= 1 graph[a].append(b) graph[b].append(a) # BFS fr = 0 que = deque([fr]) goneset = set([fr]) count = [0] * N while True: fr = que.popleft() for to in graph[fr]: if to in goneset: continue count[to] = count[fr] + 1 que.append(to) goneset.add(to) if len(que) == 0: break for _ in range(Q): c, d = map(int, input().split()) c -= 1; d -= 1 if count[c]%2 == count[d]%2: print('Town') else: print('Road') if __name__ == "__main__": main()
E - Shiritori
本番では、先頭3文字と末尾3文字を有向グラフで表し、巡回部分を DRAW で固定した後、そうでないところに対して DFS を行い末尾から、「この頂点から始まった場合の勝ち負け」を判定をしていくことをしました。しかし WA と TLE どちらもとれず、、後々考えると巡回部分の DRAW や勝ち負けを記入する際のルールが一部間違っており、考察不足でした。。
まず、この問題では、しりとりで使う単語の先頭3文字と後ろ3文字で有向グラフを使うと見通しが良くなります。例えば、有向グラフにおいて、行き先がなければ次の単語が言えず「負け」です。逆に、「負け」に矢印が出ている頂点は「勝ち」です。単語の中から「負け」になる末尾3文字の単語を言えば勝ちになります。（下図の例で、ghi の始まりの単語がないので負け。def 始まりで、defghi を言えば、相手を負けにできるので勝ち。）
有向グラフをプログラム上で扱うときは、3文字の英字と頂点番号を対応させておくと良いです。今回は出てきた3文字順に0から順番に数字を振っていくようにしました。
3文字の英字と頂点番号を対応づけさせるコード例
strings = dict() # 3文字の単語と頂点番号を対応させる辞書 for _ in range(N): s = input()[:-1] bfs = s[:3]; afs = s[len(s)-3:] if bfs not in strings: strings[bfs] = cnt cnt += 1 if afs not in strings: strings[afs] = cnt cnt += 1
さて、ゲームの問題では、後ろから勝ち負けを判定していくのがセオリーです。先程の例のように、「負け」の頂点へ有向辺が出ていれば「勝ち」というようなルールを整理します。頂点の次数を「その頂点から出ている有向辺の数」とし、勝ち負けが確定した頂点への有向辺を削除する（次数を減らす）操作をしていくと、以下のように考えることができます。
- 次数が 0 である頂点は「負け」
- 「負け」に移動できる頂点は「勝ち」
- 「負け」に移動できない頂点で、次数が 0 となった頂点は「負け」。
最後の条件について考えます。次数が 0 でないときは、「負け」には移動できないが、「勝ち」以外の頂点へ移動できることになります。これが引き分け状態となります。次数が 0 のときは、行き先が全て確定していて、それが「勝ち」であるパターンしか残りません。したがって「負け」で確定します。
以上より、各頂点の状態の更新が止まったら、「勝ち」「負け」、そして勝ちでも負けでもない「引き分け」と割り振れば良いです。
実装では、次数が 0 の方から探索するので逆向きのグラフにしています。
提出コード
from collections import deque import sys sys.setrecursionlimit(10**7) input = sys.stdin.readline def main(): N = int(input()) slist = []; strings = dict(); cnt = 0 # 次数 d_out: 出ていく辺の本数で定義 for _ in range(N): s = input()[:-1] bfs = s[:3]; afs = s[len(s)-3:] if bfs not in strings: strings[bfs] = cnt cnt += 1 if afs not in strings: strings[afs] = cnt cnt += 1 slist.append(s) graph_reverse = [[] for _ in range(cnt)] d_out = [0] * cnt for s in slist: bfs = s[:3]; afs = s[len(s)-3:] graph_reverse[strings[afs]].append(strings[bfs]) d_out[strings[bfs]] += 1 ans = ['*'] * cnt que = deque([]) for i, x in enumerate(d_out): if x == 0: que.append(i) ans[i] = 'L' n = 0 while que: # 次数が 0 のところからスタート # 操作 # 行き先の状態が確定していたらスキップ # 次数を減らす # Lose から伸びている辺は Win を書く # Lose から伸びておらず、次数が 0 なら Lose を書く fr = que.popleft() for to in graph_reverse[fr]: if ans[to] != '*': continue d_out[to] -= 1 if ans[fr] == 'L': ans[to] = 'W' que.append(to) elif d_out[to] == 0: ans[to] = 'L' que.append(to) # Win Lose 判定 for s in slist: bfs = s[:3]; afs = s[len(s)-3:] res = ans[strings[afs]] if res == 'L': print('Takahashi') elif res == 'W': print('Aoki') else: print('Draw') if __name__ == "__main__": main()
