ARC110

4完。BもCも苦手だったが、Dが得意だったおかげでいい順位。

A - Redundant Redundancy

やったことある問題な気がする。答えから1を引くと 2, 3, ... , N の公倍数になるので、最小公倍数を計算して1を足せばよい。念のためN=30のケースを計算したが、ちゃんと13桁になっていた。ていうかこれText提出できるやつじゃん。

B - Many 110

解けそうだとはすぐに思ったが、イヤな感じがしてCと交互にやった。

サンプルを見て、他の部分文字列と重なっててもいいことを確認。場合分けしたくはなかったが、3文字未満を全部手動でやる(簡単ではある)ことで実装できた。3文字の繰り返しになっているか、その3文字に0がちょうど1個であるか、1個ならその位置はどこかを調べる。Sの中で最初に現れるTの終端位置を見て、そことSの終端の距離を3で割ると、あと何個あるかわかる。

C - Exoswap

考察は面白かった。またchokudai speedrunでググって「N回スワップ」を見たりもした。与えられた順列を昇順にする設定なの親切(なので途中で忘れた)(1, 2, ... , N を並べ替えてこれにせよみたいのかと思った)。色々考えたけど、1を左端に持っていく必要はあってそのために道中のスワップは使うから他の用途に使えないのは確定ってことに気づいて解けた。1を移動させたら未確定内の左端を同様に確定させる。1が元あった位置とその右とのスワップは、1がそこにあるうちはできないので、1の移動とそれ以外は独立に考えることができる。面白かった。

実装が地獄だった。小さい順に見つけてスワップで運ぶ。見つけた場合はその位置まで飛ばす?まあそのままでもいいか。んでちゃんとソートされてるかチェック、スワップ回数もチェック。これで一応サンプルは動く。ただ証明がない。可能な場合この方法でできるし、問題文の条件をすべて満たしていればそれでOK。ということで、操作が1回ずつ出現していることもチェックすればいい。提出、RE。操作が1回ずつかチェックするところ、操作回数が違うときもやってた(B問題の実装に引きずられた)。ジャッジが終わって詳細を見ると、TLEも1個ある。2重ループになってるの気にしてなかったああ!計算量は線形だからと思っていたけど、それはちゃんと書いた場合なんだよね。後半の数が1の移動で前半に閉じ込められたとき、2乗になってしまう。その辺をちゃんと書いて提出。なんとかAC。これはね、コンテスト中にかけたいタイプの時間ではない。相当な苦手問題だった。テキトーに書いてたほうが通ったんじゃないかとか思ったし、次の問題を読みながらもC問題の言い訳ばかり頭に浮かんでしまう。コンテスト中ここまで疲れてしんどい状態になるのは久しぶりだ(そういえば最近これを回避できていたね)。

D - Binomial Coefficient is Fun

「問題の雰囲気からして、この二項係数AとB逆じゃね?」と思った。よく読むとN個の積の総和だし不可能に見える。まあ少しずつ考えていく。3000だからこのサイズのパスカルの三角形作れるなーとか。さて、まずBが何通りあるか考える。Mがでかいけど、M個のボールにN-1個の仕切りを入れるやつだ。そして、その仕切られた区間の中にA_iが入ってくる。積だし(各区間の通り数の積が全体の通り数になる)なんかまとめて計算できないかなと思う。B_iのが小さいこともあるから面倒くさそうだけど、これ個数の決まってるAを先に入れたら?Aと仕切りが並んでいるところへM-ΣA個のボールを入れる。あれ、ひょっとしてもう解けてますか。となると実装がしたい(AtCoderでたまにある答えがめちゃくちゃ単純な式で表せるやつか~?とか思いながら)。Mがでかいけど、コンビネーションを1回求めるだけなので間に合う(ΣAは高々400万)。実装できたけど、サンプルが合わない。ここで、ちょうどMではなくM以下だったことに気づく(これは忘れていたというか、読んだのがはるか過去でどうしようもない感じ)。さすがに軽すぎるので一ひねりしてある。ただ、これはパスカルの三角形をナナメに下るだけなので知ってそう。「パスカルの三角形」で画像検索して、これの和はここに来るのねと。両方に1を足すだけでACできた。20分以上かかってるけど、BやCより短い。思ったよりだいぶいい順位で、俺だけが解ける問題をありがとうだった。