yukicoder contest 225

すごくいい問題っていうのとは違うけど、実装が適度に難しくて気持ちいい。本当に久しぶりの20位以内。

No.892 タピオカ

ΣAの偶奇。簡単な問題で使わない情報があるの好き。

No.893 お客様を誘導せよ

問題文を読むのに時間がかかって後回しにしたが、順番に取っていくだけ。vectorを使いreverseするとpop_back()で対応できる。計算量はO(N*max(P))。解いてるときは深く考えなかったが、Nもmax(P)も10^5（合計人数は10^5以下のまま）だったらどうするんだろ。空でないvectorのインデックスたちをループ毎に作り直せばいいか（遅いようでオーダーは変わらないやつ）。

No.894 二種類のバス

切り上げを足して引くだけだが、AとBの最小公倍数が64bit整数に収まらない場合があるのでその判定が必要。できれば整数でやりたかったが、色々考えてdoubleで計算して2*T以上かで判断した。雑に判定できればいいので浮動小数点数が楽。

（writer解を見て）なるほどなあ、片方のバスのうち何回同時だったかを数えればいいのか。

No.895 MESE

難しそうに見えて、考えていくとけっこうスルスルと解ける。ビットの被りがないのでわりと単純な状況。大小関係の条件は要するに最上位ビットの位置。xの最上位ビットはbit0と決まっているし、そこからyの最上位ビットまではxが占める。yの位置を全探索できそうだ。あとは残りのビットだがこれはどう配置しても条件を満たすのでコンビネーションを2回やるだけ（整数の組が何個あるかわかる）。zは残りのビットに均等にばらけるので、例えば5個中3個をzが占めるなら 整数の組の個数*11111b*(3/5) となる。

No.896 友達以上恋人未満

問題文読むのに10分以上かかった。3.5秒で2^24は微妙なところで、定数倍が軽ければlogが付いても大丈夫かも。長さMODの配列を持てば各レーティングのうなぎが何匹いるかわかる。問題は倍数であることだが、logが付いていいなら1の倍数から順に愚直で間に合う（結果をその場に上書きすることでMLE回避できる）。レーティング0に注意。あとはA,Bを生成しながら答えを出力してxorとっていくだけ。計算量はO(N+MOD*log(MOD))。解説見るとloglogにまで落とせるらしい。さすがに、俺がC++で定数倍にかなり気を使って2122msなので、自分の解法が想定解ならずいぶんギリギリだと思ってた。

AGC038

2完。Bを通したあと37.1。いいAGCだったけど、結果として平凡な順位なのがね。まあ結果はいいか悪いか普通かなので、普通のときまで落ち込んでたらやってられんけど。

A - 01 Matrix

各行で少ないほうが0であるような個数をXとして、同様に各列についてY、方程式を作り様子をうかがう（W*Aとか出てきてWAは嫌だなあと思う（縁起が悪いとかじゃなくて単純に精神ダメージがあるから困る））。とりあえずNoのケースを持ってこようと思い少し試すが見つからない。サンプルを見るが、ない！これはあからさまに怪しい。ただ、そんな都合よく作れるかなあという感覚があり、Noが存在しないと決めつけはしない。10分くらいして順位表を見ると青の人もけっこう通している。少しして、何も考えず構成しにいったら作れた。これがAGCだ！最近のAGCのAは変化球が多かったので、いいストレートが来ても打てなかった。悔しいけど、仕方ないところでもある。さて、書いて出したらWAになった。AとBが逆。入力が「H W A B」なのに、Hに対応するのがBっていう。まあ、サンプル2の出力をちゃんと視界に捉えながら何も考えず提出したのが悪いけど。でも、問題も悪いと思う。

小さいほうって条件がまるっきりわかってなかったね。最大公約数とか考えてかなりうまい数になってないと無理って感覚だった。一見同じように見えて実は全然違う世界に放り込まれてる。気づけないにしても、同じだと確信できないなら疑いたい。

B - Sorting a Segment

ある区間が昇順かは累積和でわかる。K=1がなくてK=Nはあるのか。操作はN-K+1通りしかない。K=4で124356みたいなケースを考え、昇順にした結果が同じになるなと気づく。そうなる条件を探って、隣の区間と同じになる条件を考えることに思い至り、それは（長さK+1の区間の中で）先頭が最小値で末尾が最大値になることだ。とりあえずセグ木でそれを実装してサンプルを試してみるが、さすがにこれだけでは通らない。そもそも順列が変化しない操作があり、それが2個以上あったらそれだけ種類数は減る。最初に考えたようにそれは累積和で検出できる。改めて考えを整理する。N-K+1個の操作を隣と結果が同じものをつなげて区間とし、違う区間同士が同じであるケースについては、変化しない操作の数を区間の末尾だけカウントすればいい（全体を数えて各区間の長さ-1を引く）。元から昇順の区間は連続して現れるか被らず離れて現れる、1243576みたいに断絶したら再び123457が現れることはない、そういうところも一応全部詰めて大丈夫そうなので実装（雑ではあるんだけど）。けっこう複雑だったんで、一発ACは嬉しい。

C - LCMs

まあ100万なので1000までの素数168個を列挙して素因数分解したい。単純に行くと各A_iに注目して他のAたちとの和をO(N)かけずに何とか求める、その際に最大公約数で求めてもよさそう、みたいな。ただ、これ「和」なんだよね。掛け算した結果の和。積ならまだ希望がありそうだけど。だから他の方針を考えようとするが、わからない。和。これは無理だ。

D - Unique Path

3頂点を選んで0 0 0ならOKみたいな。全体をグラフにしちゃうのありそうだよね。しかし、1 1 0で多重辺はダメだから他の頂点を経由する必要があるし、とんでもなく複雑。これは時間内には無理だ。

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にできるか こう書くと難しく感じるなあ

ABC140

終了後36.8。最近ABCは、過度な緊張をせずそれでいて始まったら体温が少し上がる程度に集中できて、いい感じだ。レーティングが低い状態なので、この結果でも微増。それはそうとtokuminiさんに追いつけないのは悔しい。コンテスト内容はわりと満足。Fを全然考えないまま残り10分になって完全に失敗したと思ったが、想定誤解っぽいのを提出することができた（Fをやらずに終わるのがすごく嫌だったが、最低限できた）。

A - Password

3乗。一瞬3^Nと迷う（Nが桁数という言語化できないレベルでの誤解かな）。

B - Buffet

めちゃんこ難しいB。最近簡単すぎたのでこのくらい難しいのを望んでいたけど、こういう系統の難しさは別に面白くないからなあ（単に苦手分野なだけでは？）。満足度Cを得る条件をAの入力時に処理したが、実装はすぐ浮かんだけどちゃんとした理解は本当に難しかった。

C - Maximal Value

そこそこ悩む、いい感じのC。問題文にはmaxと書いてあるのに実装にはminが出てくるのが面白い。最初、b[0]だけ特別扱いしてn-1回ループを回そうとしてた。n-2回なのね。解けるかどうかという意味では簡単なんだけど、解き進める中で「へーそれ知らなかった」というのがいくつか出てきてやりがいがあった。

D - Face Produces Unhappiness

難しそうに書いてあるけど典型じゃんと気づく（ややがっかり感ある）。こうなると、問題文から真面目に考えるのではなく、LとRの切り替わり回数だけが重要だとほぼ確信したうえでそれを証明する方向で考えることになる。ちゃんと証明できたわけではないが、まあよさそうなので提出。

E - Second Sum

1番目ならできるかなあとか考えつつ。最初に考えたのは、全体の1番と2番を取ってきてそれらを両方含む区間を処理して、あと1番だけを含むのと2番だけを含むのと1番と2番の間にあるのと場合分けする（そういえば1番も2番も含まず1番と2番の間にもない区間を見落としてたな）。しかし、複雑すぎてこの方針では解ける気がしない。ここでセグ木の匂いを感じ取る（昨日yukicoderでセグ木コンテストがあり、AtCoderではめったに使わないよねとツイートした）。でもBITで済むねｗ。Pを大きいほうから追加していく。すると、自分より大きいものが指定区間に何個あるかがO(logN)でわかる。方針は、各P_iが2番目になる区間の数をカウントするというもの。すぐ左の大きいやつを含むかすぐ右の大きいやつを含むかしかないのでいける。BITは二分探索できるけど、さすがに使い慣れないので普通に（10^5なのでO(Nlog^2N)も余裕）。左右両方を書かないといけないので（今思うと実装量増えても右だけにするって方法もあったな）かなりしんどい。両側について一番近い大きいやつの位置を求め、右側の大きいのをとるときは、左側が0個の範囲*右側が1個の範囲。右側が2個以上も含めてたり左側にそもそもないときの扱いとか無限にバグらせてINF時間が過ぎた。左側の二分探索ほんとに苦手。これ捨ててFに行くことも考えたけど、まあ今回は簡単な（）Eを手堅く取りに行く。色々な立ち回りができてるのいいね。最後にn * (n - 1) / 2を足すように最初してたけど、期せずしてちょっとした検算になった（0-indexedにすると1が0になって答えに寄与しなくなるのもなんか混乱して時間食った）。実装に1時間近くかかってる（つらい）。復習のしがいはある。

F - Many Slimes

Eの実装に注力する前に一応読んだ（読んで寝かせると時間を有効に使えそう）。ただちゃんと読めてなかった感がある（Eの早解きになる可能性もあるわけであまり時間かけたくなかった）。なんか「最初のスライム」と「生成されるスライム」の区別がわからなくて、「あなたは最初にスライムを生成します」みたいな話かと思ってた。スライムによって生成されるスライムのことね。

最初のスライムは（体力を変えないまま）最後まで残る。大きい順にソートしてよい。一番大きいやつが、最初のスライムなのは確定。その次も確定では？その次も小さいのを生成するメリットないよね？ということで貪欲を書いて提出、WA。なにげに5分くらいでこれ実装できててすごい。4分前のWAで実装ミスでもなさそうなので望みはうすい。でも、「この方針の穴はどこだろう」と悩むところまで短時間で行けたのはうれしい。Fに挑戦することもないまま終わるのかと思ってたから。これはちゃんと挑戦できている。短時間だけど、最低限よかった。

（追記）当時考えていたのは下のような例。

5
9 8 8 7 3 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1

貪欲にとっていくと3が多くて無理になる。これを、先に3を使うことで改善できないかと考えていた。しかし、小さい数をとるメリットはない。よってこの貪欲は正しいという結論になってしまった。さて、布団の中で次の例を思いついた。

3
9 8 8 8 3 3 3 2

8が多いからダメと判定するか？いや、9は8を何回でも生成できる！つまり、これも最初の例もYesだ。残った中で最大のものを常にとる必要はない。大きいのがあるのに小さいものをとるメリットはないが、とれる中で最大なら残った中で最大のものを後回しにできる。なぜ気づかない。まあそれは問題が絶妙に難しいからだが、なぜ証明できないのに納得してしまった。証明が苦手すぎる。ゴミのような感情に頼って問題を解いている。