AISing Programming Contest 2019

A - Bulletin Board

よく読めば問題の趣旨は推測できる。しかし、本当にそう書いてあるという確信はもっとよく読まないと得られない。例えば、自分がこの問題文を、厳密性を損なわず書くのは難しい。現実問題として、小考で投げてAC。

B - Contests

一見して、ABCのBとは違う。しかし、よく読むと問題のクラスを3つに分けて1個ずつ使うってことだから、カウントして最小値。最初、maxと書いてサンプルが合わなかった。熱っぽかったので、こういうブレはある。ただ、頭はちゃんと動いていて、淡々とそれなりの速度で解くことはできていた(ので少し安心した)。

C - Alternating Path

サンプルで問題の意味を確認。次に図を描く。長い黒白黒白黒白という並びを作ってみると、そこに現れたマス同士は白黒ステップで行き来できることに気づく。行き来できるやつ同値類でまとめられるじゃん!市松模様の範囲がわかればいい。そこで、市松模様をベタヌリに変えるためにi+jが奇数のところを白黒反転させる。そしてライブラリの塗りつぶしを貼る。塗りつぶした面積ではなく、白黒それぞれの個数が必要だったと気づき処理を加えて、オーバフローにも気をつけて書く。AC。早期に人権を得たのであとはDEを楽しむだけ。

D - Nearest Card Game

死にました。

高橋くんはまず最大のカードを取り、大きい順に取っていくが、初めて青木くんが取ったカードに当たったときのことを考える。この位置がわかれば、青木くんはその時点で、その位置で終わる連続した区間を取っているし、高橋くんはその位置の次から全部と、青木くんが取った区間の最初の位置の前から1つ飛ばしのカードを取っていくだけなので、累積和(普通のと奇数番目だけの累積和)で求まる。位置は二分探索で求まりそうだ。区間としてValid(脳内でこの言葉を使っていたがここで使うのが妥当かはわからないし発音も間違っている)か判定して、Validであればそれしかないとしていいよな。ただ、Validなのは点なので、二分探索するにはiが大きくなるほど成り立つような片側の条件にすればいい?条件がどっち向きなのかが複雑。x >= a[n - 2]のケースは分岐で処理。サンプルが通らず、高橋くんと青木くんがk個ずつ連続する区間を取ったとき、青木くんの区間がValidでなくてもいいことに気づく。高橋くんが押し寄せてるから最後だけ反対側に行くしかない。そのとき条件はorでいいのか?そもそも、xがうんと小さいときとかどうなんだ。そうじゃなくても、xの左側だけたくさん取ってるケースもあるがそれは。xに一番近いカードをいきなり高橋くんに取られた場合は?そういったケースを一つ一つ処理するのは人間には不可能に思える。視点を変えればまとめて解決できるかもしれないが、思いつかない。非常に苦手な展開だ。orやandや否定を全部試すが通らない。もう思考したくないしできないししていない。高橋くんが先に取るから2個前を考える必要がある?青木くんの区間は2通りのうち片方が行けるならOK?色々がアイデアが採用されてたまに否定されてなぜ正しいと思ったかわからなくなったりいやそっちが間違いだと思ったり。解ける問題だとはかなり早い段階で思っているので、それ以上の楽しみがない。進めない。何も見えないから苦しい。自分はなぜこんな苦しい思いをしているのかわからない。

(2021/5/10追記)解いた。当時書いてたように苦手なタイプ。高橋君と青木君がK個ずつカタマリで取ったときを考えて二分探索。高橋君は後ろからK個取り青木君がそれに次ぐK個を取ったとして、青木君の左端と高橋君の左端をxとの差の絶対値で比較して青木君側が大きくなければOK(等しいときは左側を取るので)(正しい区間はより左かもしれないが、ここでは被ってないことだけを判定)。被らず取れる最大個数Kがわかったので、青木君が取る正しい区間を求める。さっきと同じように端を比較し必要なら左に1つずらす(2つ以上ずれていたらお互い1個ずつ追加で取っても被らないので最大のときはそうならない)。あとは残りを交互に取るだけ。