ABC172

相性の問題か、あまり面白くなかった。調子は良かったと思う。

A - Calc

書くだけで工夫の余地もなさそうなので不安になる。(1 + (1 + a) * a) * a のような書き方をする方針も考えたものの、普通に書いたほうが速くて確実だと判断してそのまま書いた。これだけ考えて27秒なの、ABCのAって感じだ。Aで色々考えるの好き。

B - Minor Change

編集距離の亜種に見えてビビるが、違うところを数えればよい。なぜか、一致するところを数えてNから引くような方針を選んでしまい、それなのに条件は s[i] != t[i] のままなのでサンプルが合わず、結局普通に書き直す。Bまでは考察も実装も軽かった。

C - Tsundoku

∩の形みたいのを思い浮かべ左を上に右を下にあるいはその逆にうにょうにょさせる。しゃくとり法で解ける。考察は簡単だが、実装はかなりめんどくさそう。ここでトイレに(時間を損しないためDを読んでから)。戻ってきて、ゴリゴリとしゃくとりを書く。時間はそれなり。1発ACなのはさすがの実装力ですね(?)。

D - Sum of Divisors

全然わからん。10^7というのはlogが付くとギリギリになる。しかし実行時間制限が3秒なのでそれも許されるのか?しばらく考えるとそもそも埋め込みできることにも気づく。どう解いてほしい問題なのか(という情報に頼るのはよくないと思ってはいるが)全然わからず、結局、約数がわかるタイプの篩を使いO(N*log(N))(この方法もっと計算量小さかったりするのかな)。手元で実行時間を確認できるので、一応安心して提出できる。

(解法ツイートとかを見て)約数に関するこういう感覚、最近全然だなあ。一時期普通に使えてたし今でもできるはずだが、なんかできないことが多い。

E - NEQ

なんか問題文が読めなくて、読むのに5分以上かかった。2番目の条件、あんまり意味のない「かつ」で誤読しがち。A_iは相異、B_iも相異ということで、字面のイメージとは逆に1番目の条件が厄介だった。Aは1,2,3,4,5みたいので固定して考えてもよくて、ただの順列かよと思うものの、Bで同じ位置に同じ数が来ちゃだめなので、うまくカウントできない。なんか同じ位置に来ないシャッフルとかあったよねと検索かけるがいまいち思ったものが出てこない(攪乱順列がキーワードだった)。ちょうど1個一致したときの通り数をNとMが1小さい問題に帰着できるみたいな方針を考えたが、2乗は間に合わないし高速化もできない。1番目の条件が本当に厄介で、何をやっても同じように阻まれる。

かなり経って、適当に包除とかも試してみたら当たりだった。よくわからんけど適用すると通る。これはつまらない。以前と違って包除原理を形式的に(?)使うことはできるようになったので、それはいいことだけど。昨日のyukicoderのNo.1100 Boxesみたいな魅力がない。理解してない部分を突かれて嫌な気持ちになっちゃったのかな(だとしたら完全に逆恨み)。

F - Unfair Nim

時間ないけど、設定自体は単純。Nimでググって、ニムでググるほうがいいと気づいて、必勝法を思い出す(理解はしてない)。要するにa[0]とa[1]を除いた総xorとa[0]^a[1]が等しくなればよくて、a[0]+a[1]は一定なので問題はa[0]&a[1]になる(A+B=(A^B)+(A&B)*2)。制約が10^12なので全探索はできない。さすがに短時間ではワンチャンなかった。