Atcoder-ABC198をpythonで問題を解いてみた
目的
- Atcoderで上を目指すべく頑張っている中でABC198を解いたので、解説してみる
- pypy7.3を使って解いている
A問題
考察
- 与えられる、整数Nに対し1~N-1まで数え上げれば良さそう
- N<=15 のため全探索しても計算量的に問題なさそう
- A君に1つ挙げた場合、B君にはN-1つあげることになるので、A君にあげる数に着目し数え上げれば良さそう
実装
N = int(input()) ans = 0 for n in range(1, N): ans += 1 print(ans)
結果
B問題
考察
- 回文かどうかは、文字の両端から値をチェックし続ければ良さそう
- pythonの場合は文字列を配列のように扱えるし、後ろから数える場合もマイナスをindexとして指定すればいいので、それで良さそう
- 頭に0をいくつつけるかは、文字の後ろに0がいくつあるかを数え上げ、それと同じだけ頭につけるので、良さそう
実装
N = input() flag = True cnt = 0 for i in range(1, len(N)): if N[-i] == "0": cnt += 1 else: break S = "0"*cnt + N for i in range(len(S)): if S[i] != S[-i-1]: flag = False break if flag: print("Yes") else: print("No")
結果
C問題
考察
- 到達点P(X,Y)までの、行き方が複数パターンありそう
- 半径Rで、ちょうど行くパターン
- 途中まで、半径Rで行き、直前でジグザグに行くパターン
- 半径R内に点Pがあり、2手で移動するパターン
- 問題といてる途中は、半径2R以内の点に対して、2手で行けることの確証はなかった
- なんとなく、そうなんじゃね？くらいに思ってて、ダメだったらやり直そうと思ってた
実装
- 半径内の点への場合わけが漏れていて、1回WAになった
from math import sqrt R, X, Y = map(int, input().split()) d = sqrt(X**2 + Y**2) if d % R == 0: print(int(d//R)) else: if d > R: p = d // R - 1 print(int(p+2)) else: print(2)
結果
D問題
TLEで解けず、コンテストは終了した
考察
覆面算という分野の問題らしい- 知らなかったので、コンテスト中にググった
- どうやら、inputのうち、10種類の文字列がある場合は解けないらしい
- 当たり前といえば当たり前か
- inputのうちユニークな文字列と、数字の辞書を作り、条件にマッチさせるまでぶん回せば良さそう
from itertools import permutationsを使えば良さそう
実装
めちゃくちゃTLEした、コンテスト後会社の後輩の指摘により無事解けた(自分の力ではない)
- 最初はこんな感じで解いてた
- 理由はよくわかってないが、
combinationsしてから、permutationsした方が若干早かった- 計算的には等価な気もしなくもないが、この辺りは深掘りが必要そう
permutationsのみでも、ACできたので、この辺りは不要ぽい
from itertools import combinations, permutations from sys import stdin def to_i(dic, s): n = 0 for c in s: n = n * 10 + dic[c] return n def solve(s1, s2, s3): uni_w = set(s1+s2+s3) if len(uni_w) > 10: return None for c in combinations(range(10), len(uni_w)): for p in permutations(c): dic = {k: v for k, v in zip(uni_w, p)} if dic[s1[0]] == 0 or dic[s2[0]] == 0 or dic[s3[0]] == 0: continue a, b, c = to_i(dic, s1), to_i(dic, s2), to_i(dic, s3) if a + b == c: return a, b, c return None def main(): S1, S2, S3 = stdin.readline().strip( ), stdin.readline().strip(), stdin.readline().strip() ans = solve(S1, S2, S3) if ans is None: print("UNSOLVABLE") else: print(*ans, sep="\n") if __name__ == '__main__': main()
結果
E問題
考察
- 与えられるデータは無向グラフである
グラフと木 from 京大 マイコンクラブ
www.slideshare.net
- グラフを全探索するということで、深さ優先探索を利用して解く
- stackの動きに合わせて、各ノードの色の数をcountしていく
- 深く潜って行くたびに +1する
- 浅く戻るときは、-1することを忘れないようにする
実装
ansにデータを入れる際にnot inでも調べ、重複を弾いていたが不要だった- むしろ、
inが O(n)なので、ansが大きな場合に、TLEを連発することになった- forで何度も巨大なlistに
not inするので計算量が莫大になった
- forで何度も巨大なlistに
- むしろ、
graph[a].append(b)のみで、sampleは通るが、bのノードに先にたどり着いてしまった場合aに遷移できない場合があり、全探索できてなかった- 無向グラフの場合は両方に有向辺を生やしてあげると素直に実装できてよいとのこと
- 会社の強い後輩のアドバイスでシュッと解けた
- 無向グラフの場合は両方に有向辺を生やしてあげると素直に実装できてよいとのこと
- graph, c_dictは今回辞書型だったが、別にlistでも問題はない
- むしろ、too muchなのでlistの方が良い
from collections import deque N = int(input()) C = tuple(map(int, input().split())) graph = {i: deque() for i in range(N)} c_dict = {C[i]: 0 for i in range(N)} for _ in range(N-1): a, b = map(int, input().split()) graph[a-1].append(b-1) graph[b-1].append(a-1) stack, seen, ans = [], [False]*N, [] def check(c): if c_dict[C[c]] == 1: ans.append(c) def dfs(i): seen[i] = True stack.append(i) c_dict[C[i]] += 1 check(i) while stack: s = stack[-1] if not graph[s]: p = stack.pop() c_dict[C[p]] -= 1 continue next = graph[s].popleft() if seen[next]: continue seen[next] = True stack.append(next) c_dict[C[next]] += 1 check(next) for i in range(N): if not seen[i]: dfs(i) ans.sort() for a in ans: print(a+1)
結果
追加
dfs は自分でスタックを管理するとバグらせやすいので再帰でかくアプローチが一般的な気がしますとのことで再帰でもdfsを実装してみた練習問題
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_B&lang=ja
n = int(input()) graph = [[] for _ in range(n+1)] for _ in range(n): u, k, *v = map(int, input().split()) graph[u] = v time, find_time, finish_time = 0, [0]*(n+1), [0]*(n+1) def dfs(v): global time time += 1 find_time[v] = time for next in graph[v]: if find_time[next] == 0: dfs(next) time += 1 finish_time[v] = time for s in range(1, n+1): if find_time[s] == 0: dfs(s) for i in range(1, n+1): print(i, find_time[i], finish_time[i])
