ABC141

Eを通したあと37.1、終了後36.6。得意セットだったみたいで、5完早解きに成功。調子はよかった。Fがわからず。1時間以上やってて解けないの力のなさを感じて本当に嫌な気持ちになる。全完できてないのに「コンテスト時間がもっと長ければ」と思わないときはあまり楽しめてない。今回は、(100分じゃなくて)80分でよかったんじゃないのという感じ(80分までは楽しめてた)。

A - Weather Prediction

3回コピペする必要があるので面倒。今気づいたけど1回のコピペで「Sunny, Cloudy, Rainy」が得られるのか。コピペが済んだらループを書くだけ。

B - Tap Dance

「RUDのいずれかである」は「Lでない」と言い換えられる。if文を2つ書きかけたが、きれいに書けてよかった。

C - Attack Survival

面白そう。簡単そう。それはただの第一印象なので、具体的に解いていく。ポイントが増えることはなく、誰かが0になってもマイナスになっても全員がそうなっても最後までやる。Q回とわかっているので、全員のポイントからQを引いて、正解した人に1を足していけばいい。これもきれいに実装できた。

D - Powerful Discount Tickets

まず、「Y枚の割引券を使う」ことと「1枚の割引券をY回使う」ことが同じかどうかを知らないことに焦る。紙に2進法で適当な数を書いてみると、同じでありそうだとわかる(どっちも小数点の位置をYずらすだけ)。あとは大きいA_iから順に1枚ずつ適用していくだけ。優先度付きキューは最近使ったのですぐ思いついたが、ソートして何か上手くできないかも考える(こっちのが好みなので)(完全に解けてたわけではないので無駄な時間ではない)。しかし難しそうなので優先度付きキューで実装(今気づいたけどソートしてあっても割引したらバラバラになっちゃってまるっきりダメそう)。優先度付きキューなのに決まった回数だけ処理するのが珍しくて面白かった。これもきれいに実装できた。

E - Who Says a Pun?

問題を概ね理解して制約を見るとNは5000以下。2乗が通る。何かN通りあるものを固定して処理できる。最初の部分文字列の開始位置とか部分文字列の長さとか色々あるけど、第一感は「2つの部分文字列の開始位置の差」。他のも少し探ったけど、結局はこれで当たりだった(ローリングハッシュは一瞬考えたけど、どんなテストケースでも99.9%大丈夫と思えなければ使えないと思いすぐ後回しにした)。SとSをdずらしたものを重ねて文字が一致するところを光らせる。最大で何文字連続で光ってるかはO(N)でわかる。あとはdをO(N)通り試せばいい。被ったらダメなので最大でd文字までしか取れないことに注意する(ここがかなりややこしい(実装は簡単だが))。ここまで早解きに成功して黄パフォ。

F - Xor Sum 3

提出できなかった考察コメント。提出できない悲しさがあることを忘れていた。始まる前は、力を発揮できるか心配してるからね。発揮してこれだよっていう。碁盤(碁石を手で動かして考えるのが便利な問題たまにある)と向き合っていた時間が長かったので、もうちょっと頭の中だけで考える時間もあってよかったかなと、あとから思った。

//xorするより足したほうが得 0個にしてもいいとしてよい
//2つに分ける できるだけ立ってるビットが被らないようにしたいよねー
//あるビット位置に注目すると、全体が奇数個なら仕方ないとして、偶数個なら奇数と奇数に分けたい
//偶数個のときしか分け方影響しない 上位から正の偶数個のやつを見て決めていく
//奇数と奇数に分けることは確定 その奇数がいくつかわからないし、その位置のビットが立ってないやつも影響しない
//swapするなら、上位のビットが同じでその位置のビットが異なる同士 swapだけではダメなケースがある
//上位を見て実現できないことが判定できればいいが
//上位Kビットで達成できれば片方で立ってるのは合計K+偶数ビット
//N個のうちいくつかを使ってAll1にできるか こう書くと難しく感じるなあ