perogram

幅優先探索

C - ダブレット ~経路復元~

Quiz https://arc011.contest.atcoder.jp/tasks/arc011_3 AC Code https://arc011.contest.atcoder.jp/submissions/6535492 解法 wordをグラフのNodeとする 編集距離が1のNode同士をつなげる bfsでfirst wordからlast wordまで到達できるか調べる 経路復元 …

E. Subsequences (easy version)

Quiz https://codeforces.com/contest/1183/problem/E string sが与えられる K個の部分文字列を作るのに必要な最低コストを求めよ 部分文字列tを作るコストは、sから取り除いた文字数である AC Code https://codeforces.com/contest/1183/submission/5617960…

8パズルの最短での解き方 How to solve 8 Puzzle

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_B Submission http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3610307#1 参考 http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2084544#1 解法 各盤面を状態としたb…

C - Infinite Grid

Quiz https://atcoder.jp/contests/s8pc-6/tasks/s8pc_6_c Submit https://atcoder.jp/contests/s8pc-6/submissions/4981908 解法 editorialの通り 感想 100個くらいつなげて到達可能なら行けそう 迷路で到達可能かどうか、ということで幅優先で解いたらTLE…

No.3 ビットすごろく

Quiz https://yukicoder.me/problems/no/3 Submit https://yukicoder.me/submissions/330413 解法 ある地点からの移動先は(2箇所以下に)固定されている よって、ある地点に戻って来たら、それは最短距離ではない 同じ地点を訪れないようにしながら最短距離を…

C. Connect (Codeforces Round #542 [Alex Lopashev Thanks-Round] (Div. 2))

Quiz https://codeforces.com/contest/1130/problem/C Submit https://codeforces.com/contest/1130/submission/50620759 解法 高々1つのみ橋を作れる 始点から幅優先で歩ける領域を確認 終点からも同様 始点領域の全点と、終点領域の全点でトンネルを掘って…