ABC384

5完。WA投げ大会。めちゃくちゃイライラする。この程度の問題(F)も時間内に通せないこと、時間がかかることでコンテスト中にFを詰め切るとかGを考えるとかの楽しみがゴミみたいな能力しかない自分には与えられないこと、そういうことにめちゃくちゃイライラして声が出る。前半は調子いいと思っていたので、本当に実力のなさがEFで顕在化した感じ。

A - aaaadaa

処理自体は簡単だが、どういうときにこの処理をしたいのかみたいな気持ちがわからなかったので、少し時間をかけてしまった。

解説の捉え方いいね。元の文字は使わない、元の文字との比較結果によってc1とc2の2通りに潰すんだと。

B - ARC Division

400ずれるだけなのを利用したけど、Dから1を引いて400を掛けておくべきだったね。2000や3200や400を書いて、長くなってしまった。コーディングの時間は大して変わらないと思うけど、確認(見直し)の時間がかなりかかったので。

C - Perfect Standings

やるだけ。配点は配列で受け取って、全員の名前と得点をビット回して生成してソート。

D - Repeated Sequence

存在するなら、その連続部分列の先頭からNの倍数個の項を取れるだけ取り除いて残ったN個未満の列があるので、それにあたるものが存在するかをしゃくとり法で探せばいい(コンテスト中はAでのNの倍数の位置から切り出すことを考えてた気がするけど今考えるとその必要はない)。入力を受け取ったら2回繰り返した列にしておく。最初のN項の合計を求めて、存在するかどうかは変わらないのでSをそれで割ったあまりに置き換えておく(累積和を書いてたけど必要なかった)。開始位置はN通り、終了位置は長さを2*Nにしてあるので考えなくていい(どこから始めてもしゃくとり幅がNに達したら(置き換え後の)Sを超えるため)。

E - Takahashi is Slime 2

貪欲に吸収していくだけで簡単に見える。1/X倍未満というのがオーバーフローしそうで注意が必要ってくらい(例によってdoubleで概算して大きいのをはじいてから整数の乗算でやればよい)。BFSを書き換えて、priority_queueで小さい順に処理する。サンプルが通らず、P,Qを0-indexedに直すのを忘れてたり、stringの入力を書き換えたので数値をH*W回受け取るべきところH回しか受け取ってなかったり。サンプルが通って提出してWA。データの持ち方として、頂点には訪問済みフラグと強さ、priority_queueには強さと位置を入れていたが、強さを入れるのが1番目か2番目かが逆なコードを見て「逆だった!なんでサンプル通ったんだ!?」と思ってしまい頂点のデータの持ち方を逆にして提出、実際は頂点とpriority_queueで別のデータだったのでそこはどちらでも正しいコードであり(そのことに気づいたのがいつかはおぼえてないが)、当然WA。そこからかなり考えて、根本的に実装がおかしかった。隣を見て吸収できるならして、priority_queueに入れて強さが小さい順に探索っていう、何の意味もないことをしていた。BFSとダイクストラって確定タイミングが違うんだよな。確かに吸収できるならしていいが、現在の体の周囲にあるスライムで最も強さが小さいものから順に吸収するとしたほうが実はすっきりする。隣を未探索のものの管理と小さい順に取り出すというのと2つの目的でキューを使っている(!)。吸収できなかったやつをpriority_queueに入れて、あとで吸収できたらそいつの隣を探索するんだよ。訪問済みフラグは、priority_queueに入れたかであって、吸収したかではない。吸収できるかは最終的にpriority_queueから出てきたときに確定する。

解説では、「1/X倍未満」について特に触れられず、実装例では割り算でやっていた。切り上げ除算してそれ未満なら吸収できるとしている。確かに、割り切れる場合はそれでいいし、割り切れない場合もそれでいい。これは使えるようになりたいな。

F - Double Sum 2

A_iが2^24未満と小さいので、全ビットパターンカウントできる。ただ、最初の何桁だけのパターンとかも全部持つ必要があるので、メモリ使用量は2倍にしかならないけど、ちょっと考える(高速ゼータ変換も浮かび難しそうで身構えたけど単に全部やればいいだけだった)。配列を24個用意するわけにもいかないので(グローバル変数ならアクセスしたページ(?)だけメモリにカウントされるっぽいのでいけるかもしれないけど)、例えば(2進法で)0010で終わる数を表すには10010と先頭に1を付けることにする。これで、0から24まで最初の何桁のパターンを長さ2^25の配列に収めることができる。A_iを固定して、足して下j桁は0になるがその次の桁は1になるというパターン数がこれでわかる。他の要素との和は普通にやると2回発生するのに対し自分自身との和は1回なので、ややこしいので除いておく(処理する前に自分のカウント分を減らして処理が終わったら戻す)。自分自身との和はあとで愚直をやる。当てはまるパターンの個数でコードを書いていたけど、和でやろうとしていた時期もあり、それはメモリ2倍になるのが嫌(メモリが足りることは確認したが、2倍になっても大丈夫か考えるのが面倒)だから個数で何とかならないか考えようとした(この心の動きはあまりよくないかもしれない)。和の下j桁が0になる(これは、-A_iと下j桁が一致することと同値(言われてみればそうだがこれがまた難しかった))とき、自分自身をjだけ右シフトしたものが個数分寄与する。相手の寄与は相手主体のときに足されるからいいだろうというやり方。下j桁の処理がよくわからなくて、サンプルが合ったから提出してしまった。WA。まず下j桁を0クリアしておく(どうせシフトするから関係なかったか?)。下j桁が0のときは相手も0なので何もしなくていい。そうでないとき、相手の個数分1が増えるけど、相手主体のときにも1を足されてしまうので、0.5を足したい。なので他を2倍して1を足して最後に2で割る。2倍すると、本来相手と1,1を2回やるところ2,0と0,2でちょうど正方形分になるので、2で割れば三角形になってそこに斜めを愚直で足せば答え(コンテスト中はわからなかったので何で割るかは添え字ガチャみたいのをした)。これもWAでコンテスト終わり。

過剰に2倍していたのを整理して直後に提出したが、これもよく見ると同じ意味だったのでWA。冷静に(?)考え直し、24桁(-A_iと)一致する場合が間違っていることに気づいた。そもそも24桁未満の場合しか処理してない。そして24の場合、長さ2^25の配列の外にアクセスしてしまうコードだったので、そんなものはないということで0を使うことにして提出、WA。そんなものはないじゃなくて、下25桁の情報が必要だった(ビット位置24は常に0とわかっているのに!)。下24桁が一致してその次の桁が0で一致しないものの個数が必要なコードだった。もう考えるのが嫌になったので単に24を25にして(計算量を増やして)提出してAC。unorderd_mapでやればmax(A)の配列とかなくてもできるなと気づいた(実際には遅そうだけど)。

G - Abs Sum

まずK=1で考えて、自分より小さいものの個数と和がわかればいい。実際にはKは大きいが、そこまで大きくないので工夫したい。XY両方動くのもきついが、(Bの各要素視点でやってるとき)Xが動くとY個全部変わってしまうのがつらい。