[Python] ABC015 C 幅優先探索
幅優先探索で実装します。 問題 C - 高橋くんのバグ探し 回答 N, K = map(int, input().split()) T = cur_vals = for n in range(N): new_vals = [...
幅優先探索で実装します。 問題 C - 高橋くんのバグ探し 回答 N, K = map(int, input().split()) T = cur_vals = for n in range(N): new_vals = [...
この問題ではメモ化再帰を使う必要はないのですが、前述の問題を、練習のためメモ化再帰を使って解きなおします。 問題 C - 高橋くんのバグ探し 回答 defaultdict defaultdict をメモに使ってみます。 .fo...
問題 B - 高橋くんの集計 回答 切り上げ math.ceil(x) import math N = int(input()) A = list(map(int, input().split())) cnt_bugs = 0 cnt_...
問題 A - 高橋くんの研修 回答 A = input() B = input() if len(A) > len (B): print(A) else: print(B)
問題 C - AtColor 回答 いもす法を使います。 いもす法 改札にチケットを何枚入れれば良いのかを、いもす法で解いてみた 累積和は itertools の accumulate を使います。 itertools.accum...
問題 B - 価格の合計 回答 ビット演算 >> で1ビットずつずらしながら、& でそのビットが立っているかを確認します。 Python ビット演算 超入門 n, X = map(int, input().split()) a =...
問題 A - けんしょう先生のお菓子配り 回答 a = int(input()) b = int(input()) remainder = a % b shortage = 0 if remainder > 0: shortage = b - ...
問題 D – 阿弥陀 回答 ダブリング ダブリングとは、 2倍することをlogN 回繰り返すことで Nに到達できることを利用する手法です。 繰り返し 2 乗法 ( バイナリ法 ) あみだくじにはダブリングの手法が適用できま...
問題 D – 阿弥陀 回答 30点回答 前回の方法で一つのあみだくじであれば解くことができるので、次にあみだくじを複数つなげることを考えます。 一つのあみだくじの開始地点から到達地点への変換を辞書に記憶し、この辞書による変換を複数回一つ...
問題 D - 阿弥陀 10点回答 10点の回答を理解するのに1時間ぐらいかかった…。 あみだくじは、「置換」の問題として考えることができます。 横線は「互換」に相当して、その「互換」の組み合わせ、つまり「リストの要素の交換」で単体のあみだくじは考え...