AtCoder Regular Contest 040 解説
- 1. AtCoder Regular Contest 040 解説 AtCoder株式会社 3/19/15
- 2. ARC ?040 ?A問題 ?解説 ? 「床塗り」 snuke
- 3. 問題概要 N*N ?のマス?目が?赤と?青のインクで塗られている ? ?赤のマスが多いか、?青のマスが多いか、同じかを判定せよ ? 1 ?≦ ?N ?≦ ?100
- 4. 解法 ?‘R?’ ?の個数、?’B?’ ?の個数をそれぞれ数え、?比較する ? ?文字列列の扱いに慣れていると良良いでしょう
- 5. ARC ?040 ?B問題 ?解説 ? 「直線塗り」 snuke
- 6. 問題概要 N ?個のマスが直線状に並んでいる ? ?高橋君は全てのマスを塗りたいと思っている ? いくつかのマスはすでに塗られている ? ?高橋君はマス ?1 ?からスタートする ? 1 ?秒の間に、 ? ?隣隣のマスに移動する ? ?右 ?R ?マスを塗る（マス ?i ?~～ ?マス ?i+R-‐??1 ?までを塗る） ? 1 ?≦ ?N ?≦ ?100
- 7. 解法 まず、移動にかかる時間について考える ? 最も右にある ??‘.?’ ?を塗ることができる場所まで進めば?十分 で、それ以上進むメリットはない ? つまり、最も右にある ??‘.?’ ?がマス ?i ?だとすると、 ? max(0, ?i-‐??R) ?回進めば?十分 ?
- 8. 解法 次に、銃を撃つ回数について考える ? ?最も左にある ??’.?’ ?を探す（これをマス ?i ?だとする） ? ?マス ?i ??～ ?マス ?i+R-‐??1 ?までを塗る ? を繰り返すのが最善となる ?
- 10. ARC ?040 ?C問題 ?解説 ? 「Z塗り」 snuke
- 11. 問題概要 N*N ?のマス?目があり、いくつかのマスは既に塗られている ? インク発射装置を使うと、Z字型の領領域を塗ることができる ? すべてのマスを塗るためには装置を何回使えばいいか ? 1 ?≦ ?N ?≦ ?100
- 13. 解法 このとき、 ? ??のマスより上の?行行にあるマスと、 ? ??のマスと同じ?行行で?のマスの右にあるマス ? は既に塗られているはず ? ここで、?のマスを塗る?方法について考えると、 ? Z字の右上の?角を?に合わせて塗る塗り?方が他の塗り?方より も真に良良いことが分かります
- 14. 解法 解法としては、 ? ?まだ塗られていないマスのうち右上のものを探す ? ?そのマスにZ字の右上の?角を合わせるように塗る ? を繰り返し、全部のマスが塗られるまでに繰り返した回数を 答えれば良良い
- 15. ARC ?040 ?D問題 ?解説 ? 「カクカク塗り」 snuke
- 16. 問題概要 マス?目があり、いくつかのマスには障害物がある ? 「今いるマスを塗って隣隣のマスへ移動する」を繰り返す ? 移動するたびに90度度向きを変えなければならない ? スタートのマスが決まっているとき、すべてのマスを塗るこ とが可能か判定せよ ? 1 ?≦ ?N ?≦ ?50
- 17. 部分点（40点） 1 ?≦ ?N ?≦ ?50 ? マス?目が少し?小さい
- 19. 部分点（40点） 経路路について考えたとき、あるマスに注?目すると、そこから は上or下と左or右の2本の線が伸びるはず ? つまり、上下?方向のどちらかちょうど?一?方に線が伸びている はず ? 上下?方向の線だけ書いてしまおう ? 各列列に注?目すると、上下?方向の線の書き?方は?一意に定まる
- 21. 部分点（40点） 解法をまとめると、 ? スタートの向き、ゴールの位置、ゴールの向きをすべて試す ? 経路路の線を書いて、それが正しいか判定する ? ゴールの位置の候補がN^2個、判定がO(N^2)なので、 ? 計算量量はO(N^4)となる
- 22. 満点解法 1 ?≦ ?N ?≦ ?400 ? マス?目が?大きい ? ゴール位置の候補を減らす ?
- 23. 満点解法 スタート?ゴールの経路路上の特徴を考える ? スタート?ゴールでは、上下?方向 ?or ?左右?方向のどちらかに しか線が出ない ? つまり、上下?方向 ?or ?左右?方向のどちらかの?方向に対しては 障害物と同じような扱いになる ?
- 24. 満点解法 上下?方向（or ?左右?方向）に線を書き?入れるとき、それぞれ の列列には空きマスが偶数個なければいけない ? 奇数個だと端数が出てしまう ? ゴールは「上下?方向 ?or ?左右?方向のどちらかの?方向に対して は障害物と同じような扱いになる」マスなので、空きマスが 奇数個の列列（or ??行行）になければならない ? つまり、ゴールの位置としては、空きマスが奇数個のある列列 （or ??行行）のうちのどこかしか試さなくていい！