問題 提出コード 解法 、それぞれを始点とする任意の頂点への最短距離をあらかじめ求めておきます。から頂点への最短距離を,から頂点の最短距離をとします。また、との距離をとします。 頂点に辺を張った際、仮にの順に頂点を通り、問題の条件を満たすとする…

問題 提出コード 解法 基本的にはBFSをしていけばよいです。 にいるときに、掃除済みの汚れたタイルの状態がになるような掃除の手順の中での最短手順 とします。 汚れたタイルは高々10枚なので、掃除済みかどうかの情報をbitで持っても、1024通り程度にしか…

問題 提出コード 解法 探索か何かをしつつ、今いる頂点について色を決ようとすると、その頂点から距離2以内で、すでに色が決まっている頂点がいくつあるかを調べる必要があり、とても大変です。 そこで、今いる頂点から行くことができる頂点について、色を決…

問題 提出コード 解法 木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。 ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。 これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶…

問題 提出コード 解法 それぞれのターンで、ある頂点を指定すると、その頂点を根とする木について、葉になっている頂点が消えることになります。 そして、どのような頂点の選び方をしても、木についている頂点を減らすのに一番時間がかかる部分は、木の直径…

問題 提出コード 解法 マスが黒になるのは、初期状態における黒いマスとのマンハッタン距離を全て調べ、そのうちの最小値回だけ操作を行ったときになります。 ので、全てのマスについて、初期状態に存在している黒いマスとのマンハッタン距離の最小値を調べ…

問題 提出コード 解法 まず、問題の条件を満たすようなパターンについて整理します。1つめのサンプルを見てみると、例えば下のようなパターンがあり得ます。 青が太郎、黄色が次郎、緑が花子さんの統治している国になります。 結局のところ、 太郎君(花子さ…

問題 提出コード 解法 普段のグリッドに対するBFSが2次元ならば、今回は4次元です。 Len君が、Ren君がにいるときに、そこから行くことができる4通りの方向に進みます。 そして、に行くことができるかどうかを調べていき、それぞれがゴールのマスに同時にたど…

問題 提出コード 解法 何も考えずにうしくんのゴールへの行き方をBFSで求めようとすると、マス目を移動するたびに安全なマスかどうか調べるため、時間内に解くことができません。 しかし、この問題ではイノシシが移動することはないため、安全なマスであるか…

問題 提出コード 解法 黒の杭と拡大隣接してるマスは、幅優先探索を用いて行うことができます。白も同様です。 ということで、それぞれの色について、拡大隣接しているマスをすべて洗い出します。 その処理が終わったら、片方の色についてのみ拡大隣接してい…

2/9に東京で行われました、@matsu7874さん主催の競プロオンサイトイベント、に参加してきました！ コンテスト自体は全8問で、2時間のセットでした。自分は、ABCDEGの6完でした！ B式A+B 集合写真 線香 最短経路は何本ありますか ガソリンスタンド 射的 感想 …

問題 提出コード あきらかにこれで使えそうな問題ですね… 解法 グラフにおいて、スタート地点（入次数が0である頂点）に近い方から順番に、その頂点がゴールだったと仮定した場合における最長の距離を確定させていきます。 幅優先探索のようなものをします。…

問題 提出コード 解法 bitDPです。だんだん詰め合わせ感が増えてきました。 同じ階層でからに移動するパターン数 とすると、これをの行列に見立てて乗すると、が答えになります。 を求めることさえできれば、あとはこの行列式のを求めていき、程度で答えが求…

問題 提出コード 辺被りを考慮しないコードも提出してみたのですが、どうやらないらしいです 解法 cnt[i] = i番目の町へ行く最短経路の数(で割った余りをとります) とすると、cnt[b]が答えになります。初期値は、cnt[a]=1です。 あとは、aから幅優先探索をし…

問題 提出コード 解法 橋検出アルゴリズムを用いてもいいのですが、今回は制約が小さいので、全ての辺に対して 辺を繋ぐ頂点の片方から、その辺を使わずにもう片方の辺にたどり着くことができるか という幅優先探索を行うだけで十分間に合います。 そして、…

問題 提出コード 解法 スタート地点から座標へ向かうルートのうち、黒のマスを合計回、白のマスを回通るようなものが存在するかどうか とします。すると、これは現在の座標と、通った黒と白のマスの個数をセットで記録しつつスタート地点から順番に幅優先探…

問題 提出コード 解法 珍しく探索問題です。 番目の人が駐車するには、スタート地点から頂点へ向かう、次の条件を満たすルートが存在します。 スタート地点を含む、通り道に存在する頂点の番号すべてがより大きい ということで、基本的には幅優先を行い、今…

問題 提出コード 解説の解法が綺麗すぎますね！！ 解法 1とN以外の頂点を、 1から、Nを通らないとたどり着けない頂点 Nから、1を通らないとたどり着けない頂点 1とNどちらも、もう片方の頂点を通らずにたどり着ける頂点 の3種類に分けることができます。図で…

問題 提出コード 解法 真っ暗な部屋が多くて16個しかないので、真っ暗な部屋に関する何かしらの情報をbitで持つことができます。 基本的な考え方は、幅優先探索です。 例えば回指示を出すとしたとき、指示列の選び方は種類になります。全ての部屋に対して、…

問題 指定された変形方法が与えられるので、指定された単語から、目的の単語に変形する、最小回数を求めなさいというものです(できなければ-1を出力します)。 提出コード 解法 後ろから見てもいいことが特にない(実装してWAを出しました)ので、前から素直に…

問題 提出コード なんか最近すごい似た問題を見たような…(前日の練習会でこの問題を解いていました) ある頂点から、AとBが書かれている頂点どちらか片方にしかいけなくなった時点でその頂点を消してしまいます。 これを繰り返していき、頂点が残っていればYe…

問題 N個の国と、P個の友好関係があります。 自分の国はXです。今、ある団体からLという国が脱退することを表明したので、回りの国も脱退するかどうかを考えています。 ある国は、友好関係を結んでいる国のなかで半分以上が脱退を表明していたら、その国も脱…

コップ | Aizu Online Judge 提出コード ハノイの塔の制限をきつくしたような問題です。 基本的には幅優先探索をベースに考えます。 1回の手順で行う操作はA→B、B→A、B→C、C→Bの4通りなので、ある状態に対して、その4通りを行えれば行う、ということを繰り返…