htkb-proconの日記

初心者がPythonで問題解いた記録

AISing Programming Contest 2019

ooo-- 1607 -> 1604

反省しきり。

A - Bulletin Board

AC: Submission #3983509 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

縦と横それぞれいくらずらせるかを掛ければいい。

B - Contests

AC: Submission #3984497 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

そのまま3回走査しただけ。

C - Alternating Path

AC: Submission #3988567 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

誤読で何度も実装方針を変えるハメになった。求めるべきは黒のマスから始まって白のマスで終わる経路だけなので、黒・白・黒……とたどっていける連結成分の中の黒と白の数を数えるだけの話だった。問題文を流し読みして、交互に色違いをたどって行ける任意の頂点の組み合わせ数を求めるのかと思い、上に戻ったり左に戻ったりするのを数えるためにどっちから来たのかも持つdp[y][x][4]みたいなdp組むのかな……みたいなことを考えていた。アホすぎる。

実装は同じ連結成分に同じ数字を振っていって、その代わり白のマスだったら符号をマイナスにする。で数字を振った二次元配列をchain.from_iterable()でflattenしてcollections.Counterに食わせて数を数えさせ、各iについてcounter[i] * counter[-i]を足していった。

D - Nearest Card Game

高橋くんが右から取る数について二分探索するところまではたどり着いていたので、Cで時間を溶かさなければ……と悔やんだが、実際にACするまでかなりバグらせて時間がかかったのでどっちみち多分無理。

ちょっと手でシミュレートしてみるとすぐ気付くが、高橋くんが1で青木くんが0とすると、カードの取り方は

01010100000001111111

のような感じになる。01交互のゾーンと0000011111のゾーンが、xによってはどちらか片方のみ、あるいは両方現れる。青木くんがx周辺をウロウロしている間に高橋くんが右を全て取り終えるまでが0000011111のゾーンで、高橋くんが青木くんを飛び越えた以降は010101になる。

右のゾーンの範囲が定まれば01交互ゾーンも定まるので、右のゾーンについて二分探索を考える。最初は高橋くんが取る長さについて二分探索を考えていて、高橋くんの一番左のカードの左隣(つまり青木くんの取る一番右のカード)とxの距離を数えて、二分探索で同じだけ左に行ったときのインデックス番号を取ろうとしたんだけど、この距離は負になりうるしうまくいかない。

で考え直してみると、0000011111ゾーン全体の長さ全体についての二分探索を考えれば、青木くんの右端のカードと左端のカードも定まる(高橋くんが先手なので青木くんゾーンは全体の長さの半分切り捨て)。で、|左端のカード-x| <= |右端のカード-x|の場合は青木くんゾーンがもっと左にある、もしくは正しい位置と考えられ、|左端のカード-x| > |右端のカード-x|ならば青木くんゾーンはもっと右にあると考えられる。

f:id:htkb:20190113053828j:plain

上の図でいうとmid=4のときも7のときも青木くんゾーンの位置は正しくないんだけど、|左-x| <= |右-x|を満たす範囲で最大のmid(=6)のときが答えになるのでこれをOK、そうでなければNGとし、二分探索でこれを求めた。

AC: Submission #3994020 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

予想に反しこれでも時間ギリギリで、二分探索 in 二分探索解はpypyでも通らなさそう。