久しぶりに bfs やら ord を書いたのでメモ。 import sys input = sys.stdin.readline h,w = map(int,input().split()) s = [list(input().rstrip()) for i in range(h)] to = [[] for i in range(26)] for i in range(h): for j in range(w): if 96 < ord(s…

atcoder 再開。水色になった。 01-bfs というやつらしい。+0 を append で、+1 に遷移するものを appendleft でdeque に入れてあげると、O(1) で heap みたいなことができる。heap で回したら TLE した。 よくある bfs や今回初めて書いた 5*5 の移動をメモ…

まず、根になる頂点は、Bには含まれておらず、そのような点 a がただ一つ存在することが分かる。 そして、次に Ai = a となっている辺を全て取り除くと、Bに含まれない点 b が新たに1個以上現れる。その点は、a しか親になりえないので b の親は a とわかる…

1,...,n のうちの頂点 i から bfs をはじめて最短何回で全頂点辿れるかを計測しつつ、i から１回で通れる頂点, 最短２回で通れる頂点,,, をリストに入れておく。 答えが -1 にならない条件は i から同じ回数で辿りつける任意の２頂点が辺を持たないことであ…

4完。Eは難しかった。Dが bfs するだけなのは分かったが一から実装するのに手間取った。dfs だけライブラリとして持っていたのに... bfs も作りました。 # 木(辺のリスト作成) n, m = map(int, input().split()) g = [[] * n for i in range(n)] for i in ra…

Code Jam - Google’s Coding CompetitionsAしか解けず５点差で通過できず。C何とかして部分点取りたかった。インタラクティブはまだ入力の仕方がわからないので諦め。 Aは４方向に i 回目に 2**(i-1) 移動でき、(x,y) = (0,0) から、最終的に目的の座標に到…

atcoder.jp与えられた’１’のマスを移動できる最大値を求める問題。 普通の bfs だと例えば 1 1 0 1 1 0 1 0 0 が与えられたときに a[1][1]をスタートとしても 3 2 0 2 1 0 3 0 0 のような移動距離を返してくる（本当は a[2][0] = 5となってほしい） そこで通…