狠狠撸

ARC #041 解説
解説スライド担当 : @sugim48

問題 A – コインの反転

問題概要
? 表向きのコインが ? 枚、裏向きのコインが ? 枚ある。ちょうど ? 枚の
コインを選び、それらすべてをひっくり返す。その結果、表向きのコイ
ンは最大で何枚になるか？
? 1 ≤ ?, ? ≤ 106，1 ≤ ? ≤ ? + ?

解法 1
? ひっくり返した結果、表向きのコインをできるだけ多くしたい。
? まずは裏向きのコインからひっくり返していき、? に満たなければ表
向きのコインもひっくり返していく。
? ちょうど ? = ? ならば、すべてのコインを表向きにできる。? ≠ ? なら
ば、ズレの分だけ裏向きのコインが残る。
? 答えは ? + ? ? |? ? ?|

解法 2
? 今回は ?, ? ≤ 106 が小さいので、全探索ができる。
? （表向きのコインをひっくり返す枚数）+（裏向きのコインをひっくり返
す枚数）= ? である組を全通り試し、答えの最大値を求める。

問題概要
? 縦 ? マス、横 ? マスの盤面があり、各マスにアメーバが何匹かず
ついる。ただし、壁際にはいない。
? 各アメーバが 4 匹に分裂し、上下左右のマスへ 1 匹ずつ移動した。
? 今の盤面が与えられるので、はじめの盤面を 1 つ求めよ。ただし、
解は少なくとも 1 つ存在する。
? 3 ≤ ?, ? ≤ 500

考察
? 次の例を考える。
0 1 2 0
1 5 5 2
3 5 5 4
0 3 4 0
0 0 0 0
0 ? ? 0
0 ? ? 0
0 0 0 0

考察
? ここに注目すると、このアメーバは下のマスから来たと断定できる。
0 1 2 0
1 5 5 2
3 5 5 4
0 3 4 0
0 0 0 0
0 ? ? 0
0 ? ? 0
0 0 0 0

考察
? よって、ここのアメーバの数が決まる。確定したアメーバの分は左の
盤面から引いておく。
0 0 2 0
0 5 4 2
3 4 5 4
0 3 4 0
0 0 0 0
0 1 ? 0
0 ? ? 0
0 0 0 0

考察
0 0 2 0
0 5 4 2
3 4 5 4
0 3 4 0
0 0 0 0
0 1 ? 0
0 ? ? 0
0 0 0 0

考察
? よって、ここのアメーバの数が決まる。確定したアメーバの分は左の
盤面から引いておく。
0 0 0 0
0 3 4 0
3 4 3 4
0 3 4 0
0 0 0 0
0 1 2 0
0 ? ? 0
0 0 0 0

考察
（上左右からの影響は差し引いてあるので）
0 0 0 0
0 3 4 0
3 4 3 4
0 3 4 0
0 0 0 0
0 1 2 0
0 ? ? 0
0 0 0 0

考察
? 以下同様
0 0 0 0
0 0 4 0
0 4 0 4
0 0 4 0
0 0 0 0
0 1 2 0
0 3 ? 0
0 0 0 0

考察
? 以下同様
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 1 2 0
0 3 4 0
0 0 0 0

解法
? 上の行から順に答えを埋めていく。解の存在が保証されているので、
矛盾なく答えが求まる。
? 計算量は O(??)

問題概要
? ? 個のマスが一列に並んでいて、その上に ? 匹のウサギがいる。各
ウサギは左か右を向いている。
? 各ウサギは、自分の目の前が空きマスならば、ジャンプしてそのマ
スへ移動できる。
? ウサギがジャンプする順番を決められるとき、ジャンプの総回数の最
大値を求めよ。
? 1 ≤ ? ≤ 105，? ≤ ? ≤ 109

考察
? 背中合わせのウサギたちは互いに影響しない。
? 例えば、次のような区間は別々に考えることができる。

考察
? 次のような区間は終了形が一通りに決まるので、ジャンプの総回数
を計算できる。

考察
? 次のような区間は終了形が複数通り考えられる。

考察
? ぶつかる位置を全通り試し、ジャンプの総回数の最大値を求める？
→ ? ≤ 109
なので、最悪 109
通り試すことになり厳しい。

考察
? ジャンプの総回数を数えてみる。
3 回
4 回
5 回

考察
? ぶつかる位置が右に 1 マス動くと、ジャンプの総回数が 1 増える。
? 左側の 2 匹のジャンプ回数が 1 ずつ増え、右側の 1 匹のジャンプ
回数が 1 減るため。
? この例では、できるだけ右に寄せるのが最適。

考察
? 例から分かる通り、ウサギの少ない側に寄せるのが最適。
? 終了形が決まれば、ジャンプの総回数を計算できる。

解法
? ウサギたちを区間に分ける。
? 区間ごと別々に、ジャンプの総回数の最大値を計算する。
? その総和が答えである。ただし、オーバーフローに注意！
? 計算量は O(?)

問題概要
? ? 頂点 ? 辺の連結な無向グラフが与えられる。
? 好きな頂点から始め、好きなだけ辺を辿っていく。
? 辿った辺には赤 → 青 → 赤 → 青 → … の順に色を塗る。ただし、色
は上書きされる。
? 目標の辺の配色は可能か判定せよ。
? 2 ≤ ? ≤ 2,000，1 ≤ ? ≤ 2,000

例 2
? 可能である。ただし、上書きされる色は破線で示している。

考察
? まず、色が「上書きされる」というのがややこしい。

考察
? そこで、辺の辿り方を未来から過去へと逆向きに考えてみる。
? すると、「一度塗った色は上書きされない」というルールに変わる。
→ この方が考えやすい！

考察
? 未来から過去へと考え直すことによって、次のように問題を言い換え
られる。
? 始点とはじめの色（赤 or 青）を好きに選び、好きなだけ辺を辿っていく。
? 辿った辺には赤青交互に色を塗る。ただし、色は上書きされない。
? 目標の辺の配色は可能か判定せよ。
? 見通しが良くなった！

考察
? ?, ? ≤ 2,000 と小さいので、始点とはじめの色は全探索できそう。
? 例えば、ここを始点に、青から始めてみる。

考察
? 次に塗る色と目標の色が一致していれば、その辺を塗ることができ
る。
? 色は上書きされないので、一度塗った辺は自由に行き来できる。

考察
? 分かれ道はどう辿ればいいか？

考察
? 分かれ道はどう辿ればいいか？
→ 実は、どれを先に選んでも同じ。

考察
? 分かれ道の選び方が自由なので、深さ優先探索や幅優先探索など
で貪欲に辺を塗っていける。
? すべての辺を塗れたら、目標の辺の配色ができたことになる。

想定誤解法
? 始点とはじめの色を全探索する。
? 深さ優先探索や幅優先探索で貪欲に辺を塗っていく。
? すべての辺を塗れたら、すぐ “Yes” と判定する。
? そうでなければ “No” と判定する。
→ 重要なポイントを見落としている！

考察
? 次の例は不可能に見えるが、実は可能である。

考察
? ここを始点に、青から始める。

考察
? 深さ優先探索や幅優先探索で次のように塗れる。
? 三角形の閉路ができたのがポイント。

考察
? 一見詰まったように見えるが、三角形の閉路を回ることで赤 / 青を
反転できる。

考察
? 再び三角形の閉路を回り、すべての辺を塗れた。

考察
? 奇数長の閉路を回るごとに赤 / 青を反転できる。
? よって、奇数長の閉路が完成すれば、あとはどんな塗り方も可能！

解法
? 始点とはじめの色を全探索する。
? 深さ優先探索や幅優先探索で貪欲に辺を塗っていく。
? すべての辺を塗れたら、すぐ “Yes” と判定する。
? 奇数長の閉路が完成したら、すぐ “Yes” と判定する。
? そうでなければ “No” と判定する。
? 計算量は O(??)

狠狠撸

Arc041

More Related Content

Arc041