ABC246

6完。直前までぷよぷよ最強リーグを観ていて、ちゃんとトイレの時間を残して切り上げて間に合ったと思いきや、鉛筆が見当たらないというトラブル。ぷよぷよの前はずっとプロセカやってた(想いのカケラの割り振りを調べたり考えたり)ので、準備はちゃんとしたつもりでも抜けがある可能性が大きくなり気分的にも対処が難しくなる。A問題では少し探したあとにボールペン(使いたくない)を使った。のちに鉛筆は見つかったが、かなりの時間をロスした。

ずっと競プロやプログラミング以外のことをやっていると、やはり(短期的にも)パフォーマンスは落ちるのかもしれない。今回はなんとか青パフォで、軽傷で済んでよかったねという感じ。最近ABCに対する(コンテスト前の)緊張感が(ratedなのに)減ってきて、それを自覚していたから時間には気をつけていたが、それだけではなく多少の準備運動も必要だと思った。せっかくの集中して取り組めるratedコンテストなんだからね。

A - Four Points

かなり面倒なやつという記憶だったが実際どうだっけ。xorを使いたいので考えると使えそうなので使う。x座標を考えると、制約から同じものが2回登場し、求める座標は残った一つと同じ。y座標も同様で独立に求まる。

B - Get Closer

これはいい問題。基本的な処理。長さの逆数を掛ける(実装上は速度が必要ないので割った)。

C - Coupon

X円未満のものに使うとクーポンの値下げ能力の一部が無駄になるのでそれを最小化。まず無駄にならないぶんは使ってしまう。これで、すべての商品の値段がX円未満か、またはクーポンを使い切った状態になる(実装のイメージはすぐ浮かんだが、ここが「または」になるので詰めるのに時間はかかった)。そこで値段を降順にソートし、クーポンが残っている限り適用していく。こういう、考察ちゃんとやるタイプのC問題久しぶりで嬉しい。

D - 2-variable Function

解ける気がしない。先にEを読んで心を落ち着かせる。因数分解したり都合のいい変形がないか考えたりしていたが、そもそも3乗なのでa(bはaより大きくないとして一般性を失わないのでそうする)は10^6以下。別に多数のクエリが来るわけでもない。aを全通り試せそうだ。aの上限を求め、デクリメントしながら(しゃくとりみたいに)bを大きくしていく。O(N^(1/3))なんだね。aの上限は、まずdoubleで雑に求め、3乗がN以下になるまでデクリメントし、次に3乗がN以上になるまでインクリメントする。

E - Bishop 2

どっかで見たような問題(Pond Skaterだった)。BFSだけど、同じマスのチェック回数をO(1)にできるかというのが問題。どんな向きで来たか記録しておいて同じ向きには行かないようにするのを考えた。確信までが遠いのと、これの実装でコンテストが終わったら嫌だというので、先にFをやった。

「あれ、既に行った場所までで止まればただのBFSで行けるんじゃね」と思って実装する。しかし、例外を普通に構成できた。違う向きのときは訪問済みでも貫通する必要がある。ナナメにまっすぐ次の移動先を探すとき、同じ向きでやるのは1回でいい。4種類の向きのフラグを持つ。同じ向きのフラグがあったらそこから先は全部やってあるということだ。素のBFSの処理と比べて各マス4回しか通らないからOK。しかしTLEで、訪問済みのときcontinueしてたからそのとき通過フラグをセットしそこなっていた。TLEのジャッジが終わらないうちにACした(たぶん初めて)(6秒のTLEは18秒でそれが8個)。

F - typewriter

めちゃくちゃ簡単だと思ったが、サンプルを見ると同じ文字が複数ある場合もあるタイプライターなのね。まあ包除っぽくて、それでも簡単そうに見える。2つの段の両方で打てる文字列は、打てる文字集合の共通部分からなるものだ(それは打てるしそれ以外は打てないので(直感が働かず、証明しないと不安だった))。各段の文字をビットに詰め込む。2^18通りの選び方があって、選んだ段たちの文字集合のandをとって共通する文字数のL乗を計算する。段の個数が奇数なら足す(1個は奇数なので)、偶数なら引く。0個の段を選んだとき、全部の文字を打てることになってびっくりした(orじゃなくてandだからねー)(0も入れて符号を逆にすると、長さLの文字列のうちこのタイプライターで打てないものの個数が求まる)。実装上0個は除外する。

サンプルが合わないばかりか実行時間が異常に長くなったりして原因がわからなかった。かなり時間を費やし、FではなくGのサンプルを試していたことに気づいた。0個のケースを考えるのを含めて9分かけてる。これ自作のサンプルダウンローダー(実行ボタンを押すと、Firefoxで見てるタブのサンプルをVisual Studioで試すようにしてある)の不具合で、直し方わからんし頻度も低いから放置してたんだけど、当たるのが久しぶりすぎて全く警戒してなかった。

(解説を読んで)それもどこかで見たやり方だけど思い出せなかった。

G - Game on Tree 3

わからず、Eに行った。どこでも0にできるのが難しい。0にする場所は上からでよさそう(今考えるとあやしいが、少なくともこれまでに選んだ頂点の祖先を選ぶことはないとしてよさそう)。最後、とりあえず真の答えより小さくない答えを出すコードを書いたつもりが小さくてその原因もわからなかった。

(追記)改めて考えてもわからない。だいぶ経って、二分探索を思いついた。なるほどね。しかしそこからも難しい。何個0に書き換えておけばいいかで木DPできそうに見えるけど、部分木の根が書き換え対象かで場合分けが必要かどうかわからない。毎回1個だけ書き換える余裕があるが、その-1をどこにつければいいかわからない。時間をかけてもダメで、しっかりダイブする必要があった。0にする必要があるのは、直接の子とそれ以外。直接の子が0個なら1個余裕ができるし、1個ならイーブン、2個なら1個必要になり、まあ和をとるだけ。結局、解説にある式になるんだけど、直接の子のやつはmaxの外側で足すというのが手癖では書けないポイント。難しかった。