Learning Algorithms

アルゴリズムの勉強メモ

AOJ

AOJ Prime Caves

AOJ

AOJ Prime Caves 感想 実装がめんどくさい 解法 どう見てもDPするだけ。$\ m \leq 10^6\ $なので、$\ 1000 * 1000\ $の正方形のマスを用意して考えればよい。すごく面倒だが、各数を投げるとその配列上での位置を返す関数を作る。これは各正方形の左上の数が…

AOJ Graph Automata Player

AOJ

AOJ Graph Automata Player Graph Automata Player | Aizu Online Judge 感想 ICPCのチーム練習で解いた。好きな感じの問題なので、じーーっと考察していると解法がわかった。 解法 ある頂点に注目して考える。ある状態から次の状態に遷移するとき、その頂点…

AOJ Slim Span

AOJ

AOJ Slim Span Slim Span | Aizu Online Judge 解法 まず全域木の中で、重みが最小となる辺を固定する。その重み以上辺のみを使って、$Kruskal$法によって最小全域木を作り、その時の$Slimness$を求め、その最小値をとる。 辺はあらかじめ重みで昇順にソート…

AOJ Patrol

AOJ

AOJ Patrolパトロール | Aizu Online Judge無向オイラー路の判定をするだけなので、スタート地点とゴール地点の字数が奇数でかつ他の点の字数がすべて偶数であるかどうかを判定するだけである。入力の受け取り方の方が面倒な問題......。問題解いてる部分は…

AOJ Kobutanukitsuneko

AOJ

AOJ KobutanukitsunekoKobutanukitsuneko | Aizu Online Judgen個の文字列が与えられる。それらすべてを使ってしりとりができて、さらに最後に使った文字列の最後の文字が最初に使った文字列の最初の文字を一致させることが可能かどうかを判定する問題。x...…