競プロ日記

順位: 827

パフォーマンス: 1421

新レーティング: 977

差分: +88

5完
配点がABCと一緒だったのと、年内に水色なっておきたいんだけどなーという気持ちがあったので、初めてABC以外に参加してみた。
最初に思ったのが、コンテスト名長いし略せないーーー。
コンテスト毎にフォルダ作ってコードを保存しているのだが、フォルダ名とかブログの記事名とかどうしようかと迷う。
フォルダ名はAOJとかではURLを参考にしているので今回もそうしたが、ブログ記事はみんな略してないしsumitrust2019だとなんのこっちゃなのでそのままで。

中身の話だと、まともな解法で初めてEを通せたのが非常に良し。
かなりすらすら解けた。

頭が回る・・・！
こんな幸せな気持ちで解けるなんて初めて・・・。
もう何も怖くない！

と思ったら単純に簡単な問題だった。

かんたん。
4つの入力のうち3つが要らないなんてことが！？
かなり怪しんだけどやっぱり要らなかったね。

ほぼまんまの問題小学生の頃解いた記憶がある。
確か税込みの値段としてありえる値段には、数列として考えると増加値に規則性があったなーとか思い出していたが、今回はそこまで考えなくても良さそう。
切り下げだから割った値と+1した値を計算すれば十分かなーと思ったら良さそうだった。
余分な計算する分には問題ないと言い聞かせて、そこまで深く考えずに解けた。

ある数以上は絶対作れそうだなーと思ったが、その数どうやって求めようかすぐに思いつかなかったのでこの方針はパス。
個数決め打てば制約的にも問題ないなとなった。
これはある値を決め打って二分探索の経験が完全に生きている。
Cにしては難しいと感じた。

桁DPかぁ！？
と思ったけど桁DPにすると状態がかなり複雑になるのでは・・・？
桁DPしなくても全探索とかもっと簡単に解ける問題もあるんだよとABC114 C 755で学んだので、別の解き方を考える。
出てくる数字は10種類しかないから、O(10^3)ならlogとかNとかついても行けそう！となったので、000~999を全探索する方針にする。
ここで直近のコンテストの経験がまた生きる。
記事には解いた部分を書いていないが、ABC146 E Rem of Sum is Numで、「ある数が出てくるインデックスを記録する」という方針を解いたばかりだったのですぐに思いついた。
別にこの問題に限った方針ではないし、過去に何度か自力で解いているので直近で解いていなければ解けていないということはないだろうが、経験は力だなぁとかなり感じた。

左の桁から考えると、異なるインデックスから取った同じ数字は分けて考える必要がないので、数字を選ぶ際は次に選べる数を多くするように、なるべく左のインデックスから選ぶべき。
1桁目は、必ず左端なので、数が数列に存在するかどうかのみで良いのでO(1)。
2桁目は、1桁目より右側でなるべく左なので、upper_boundでO(logN)。
2桁目は、2桁目より右側に存在すれば良いので、upper_boundでO(logN)。
合計でO(10^3*log^2(N))。
N=30000のとき225000くらい。
解説でO(100N)とO(3N)で解けるよ！って書いてたうちのO(100N)に近いが、そうなら普通にlog入れてくるような気もするからどうなんだろう。

問題を見た時ちょっと難しそうだったので小休憩として、「確か上位入賞者は賞金あったな。上位は今どれくらい解いてるのかな？」と順位表を見に行ったら1人全完してて笑った。
化け物かよ。

ここまで32分。
うわ場合の数だうわああああああ。
ぼーっと考えてたらちょっとひらめいた。
前から考えて、その時点であり得る色の選び方を順番に掛けて行けば良さそうだなー。
試しに実装してみたらサンプルケースも合うし、提出したらACもらえた。
か、かんたん・・・。
ほんとに500点問題なのかと思わず確認したね。
後から知ったが、矛盾する入力で答えが0となるケースもあるらしい。
ありえる色の選び方を順番にかけているので、途中で0が入ればそれは0になるから問題ない。
別の実装だったらちょっと問題になるのかなーという感じはする。
「すべての人の発言が正しい」という文章は、答えが0でも良いと捉えるより、答えが0になるような矛盾がないと捉える方が普通だと思う。

ここまで46分。
残り90分以上！？
もしかして初全完！？
・・・残念ながらそんなことはなかった。

グラフで考える、場合分けも合ってる、T1が終わった後に2人の差がちょうど0だったら+-1が生まれる、とかなり惜しいところまで考察できてたと思うんだけど数学力が足りなかった。
ワンチャン小学生の頃なら旅人算チックに解けてた可能性あるが。

まず愚直にシミュレートしたら色々思いつくかなーと実装。
なんか奇跡的に通ったらいいなーと提出したらTLE+WA。
WAは見ないことにしてやっぱりTLEかーとなる。

これ提出した時点で残り20分切ってるんだよね。
考察にかなり時間取られたとは言え、愚直に実装する部分だけで少なくとも30分以上は取られているはずなのは非常に良くない。
愚直は頭の中か紙の上だけでやろう・・・。

愚直が終わってとりあえず場合分け。

T1+T2でAとBが進む距離が同じなら無限に出会う。
T1+T2でAの方が多く進むのに、T1の時点でAの方が多く進んでいたら1回も出会わない。
n回目のT1の後に2人の差がちょうど0なら-1する必要がある。

ここから不等式書いたり色々したが、時間が残り少なくて色々ミスしてしまった。
ミスなくてもおそらく間違いだが、もっと落ち着けば解けたかなー。

後からYouTubeの解説を見てAC。
1回目のT1の後の時点をc、1回目のT2の後の時点をdと置くと、cから毎回d引かれていくというのがいまいちピンとこなかった。
進む距離がT1とT2で違うのに？というのが解決できなかったのだが、今考えてみると×2していることから、T1とT2の後のそれぞれの差を考えているわけじゃなく、T1の後の差のみを考えているんだなと気付いた。

とりあえず2人の差から考えるという部分だけ学んで、T1とT2を分けて考える方針で実装してみると見事に計算部分がほぼ同じになった。
不等式を解いている途中にも気付いたが、そもそも最初にT1+T2の時点でAがBよりも大きいと仮定しており、T1の時点の差は大きくなることはなくだんだん小さくなっていくので、T1の時点でBの方が小さければ必ず交差する。
それすなわちT2の方は考える必要がなく、×2するだけで事足りる。

まとめ

記事に考えを整理して文字に起こすと新たに理解が深まるの良いなぁ。
今回はFで2つも理解してしまった・・・。

今回初まともな5完だが、やたらと簡単だったからなぁという気持ち。
5完なら青パフォーマンスくらい欲しいところだが、今回は水色パフォーマンス。
AtCoder Problem的にもかなり簡単だったのであまり達成感がない。
もうちょっと難しい問題で5完できれば達成感とともに水色いけるかな。
4完でもそこそこの速度なら後2回くらいで水色行けると思うんだけどどうだろう。
後2回くらいコンテスト開催して年内水色行かせてくれー。