ARC106感想戦

🦍

AtCoder Regular Contest 106 に参加しました。画像はコンテスト中に書いたメモです。

Aは、与えられた $N$ に対して、 $3^A+5^B=N$ が存在すれば求める問題。 $A, B$ の候補を全部確かめていけばOK。

でも、3を掛け続けたり、5を掛け続けたりしたときに、オーバーフローに気を付けないといけないな、と思う。で、前に見た、「オーバーフローしてないかどうかのチェックにdoubleを使う」っていうのをやってみた。が、あとで他のツイートを見て、そもそも1e18に5を掛けてもオーバーフローしないってのを見て、たしかにそうだと思った。間抜けだ。少し時間をロスした。この時点で5分。


Bは、操作をやっても総和が変わらないので、総和が等しいことが必要だとはすぐにわかったけど、それが十分なのかがわからず。

閉路がなかったら大丈夫そうだなという気はした。でも、閉路があると、操作をやっていったときに、最後の頂点でつじつまが合わなくなったりするかな?というのが自信なく。でも、閉路1個1個チェックしていくの大変そうだし、通してる人数を見ると、きっとこれで十分のはず、と未証明で「総和が一緒ならYes」で提出(提出 #17615740)。1WA。

なんでダメなんだ、やはり証明しないとダメか、と思ったけど、問題をよく見たら、Mが0のときもある、つまり、連結じゃないこともあるのか、と思って、なるほど、各連結成分での総和が一緒じゃないとダメなんだな、と思い直す。これで提出してダメならあきらめようと思って提出(提出 #17618911)。AC。AtCoderライブラリを使って、使い方を調べつつやったのもあって、この時点で23分。

今解説を見てみたら、木じゃないときは全域木を抜き出して考えればいいのか、なるほど、うーん、思いつけないのは頭が悪いな。


Cを見る。見るからにめんどくさそうだったので、Dも見る。これは形式的冪級数ってやつか?無理。仕方なくCにいく。

とりあえず、サンプルを理解する。文章は長いけど、大して難しいことはやってないな、と思って気分を落ち着かせる。

で、とりあえず、取り得る値を考える。T-A=Mの式で、少なくともTもAも1以上だから、MがNになることはないな、などというのを考える。で、そもそもA=1のときを考えると、Aで選んだ1個の区間は他の全部の区間とそれぞれ交わってるから、Tは最大でもN-1しか無理だな、というのもわかる。なので、Mは、N-2以下しかありえない。

で、T=N-1で、A=1となるときを考えると、1-1e9の区間と2-3、4-5、6-7、…の区間を考えればいいことがわかる。左でソートすると、めちゃデカ区間をいきなり選ぶからA=1、右でソートすると、めちゃデカ区間が最後で他は全部選ぶからOK。

Mが正のケースでは、先ほどの答えを利用して、T=M+1、A=1となるようにする。M個の互いに交わってない区間、めちゃデカ区間、互いにぜんぶ交わっている区間(N-M-1個)とやれば、うまくいくじゃん。天才。

M=0はT=N、A=Nとなるようにすればよくて、Mが負の場合は、上の答えを逆順にすればいっか、と安易に思ったんだけど、よく考えるとうまくいかないことにきづく。あれ、これどうすればいいんだ?と少し戸惑う。で、冷静にもう一回考える。

M=N,N-1がないことを確認、Mが正のときもとりあえず再確認、で、Mが負になる場合を考える。左端でソートしたとき、ある区間を採用したとき、次の区間が交わってたらAには絶対はいらないがTには入るかもしれない。次の区間が交わってなければAには入るがTにも入る。なるほど、負になる場合はないんだな。

解説を見たら、Tの解法はスケジューリング問題の最適解を求めるものだから、Mは負にならない、と。なるほど、それはそう。

で、ここまでの内容をコードに書いて提出(提出 #17629371)。WA。明らかに間違っていたところを直して提出しても、まだWA。なんでや。

1つだけ通らなかったので、どんなコーナーケースがあるかなと思って制約をよく見たら、N=1もあるのか。なるほど。「M=N,N-1はない」と思っていたけど、N=1のときは、M=N-1のケースがあるのか。厳しい。再提出(提出 #17631321)。AC。この時点で、72分。


とりあえず、Dも見るけど、これって形式的冪級数っていうやつ、使うんでしょ?どうせきっと無理だよ、と思いつつ、考えてみる。

あれ? これ、二項定理使って展開しただけでうまくいきそう。積の和を速く計算すればいいのか。積の和は、k乗の和が速く計算できればいいから、これ実はそんなに難しくないかも。しかし、今までのロスで、時間がない。間に合うかわからんけど書く。が、結局バグがとれず、記念に提出だけする(提出 #17636645)。

コンテスト終了後も格闘して、二項係数を計算する自分のライブラリがおかしかったこと、modのとり方がおかしい、配列の添え字がおかしい、などのバグがあって、それらをクリアしたら通った(提出 #17638835)。これは頑張れば通せてたかもしれないけど、残り30分の状態で考えてコードを書くところまで仕上げるのは無理だったので、なかなか厳しいものがある。ABCのFよりもやさしかったな。

今までの低下を補うのに何年かかるペースなんだ。。。