文章で自分の思考を説明する練習、 それによる思考の整理、 ブログの更新頻度を上げることによるブログ維持管理のモチベーション確保等を目的にAtCoderの参加記を書くことにした。
結果
できれば全完した上でみんなの役に立つ解説記事を書きたいが、今の自分の実力だとなかなか難しい。 A,B,C,Eの4完90:31で、順位は501位になった。
A - Calc
提出 #14720687 - AtCoder Beginner Contest 172
やるだけといえばやるだけ。
a+a^^2+a^^3と書くか一瞬迷った上でa+a*a+a*a*aを選択したが、どちらのほうが良かっただろうか？
割とどちらでもいい。
B - Minor Change
提出 #14725932 - AtCoder Beginner Contest 172
長さが等しいので、単に異なる場所の数をカウントするだけでいい。
zipした上でmapで各文字を比較するD言語の文字列mixinを活かしたコードになったが、普通にループを書くのとどれほど速度に違いがあるだろうか。
コードが短くなって嬉しいが、書きやすさでいうとよくわからない気がする。
C - Tsundoku
提出 #14737776 - AtCoder Beginner Contest 172
本は上から順番に読んでいかなければならないので、「机Aと机Bからそれぞれ何冊取れば合計冊数が最大になるでしょうか」という問題に言い換えられる。 普通に総当りすると$O(NM)$で、$1 \leq N, M \leq 200000 = 2\times 10^5$なので間に合わない。 机Aから取る冊数を固定すると、机Bから取れる最大の刷数は累積和による事前計算と二分探索で事前計算$O(M)$、1回あたり$O(\log(M))$で計算できる。 机Aから取る刷数を総当りして計算量は$O(N\log(M))$。
D - Sum of Divisors
解けなかった。 約数の個数を複数のKについてなんとかまとめてカウントできないか考えてみたが思いつかず、 素因数分解による約数カウントをすべてのKについて行うコードをとりあえず書いてみる。 当然間に合わないため次の問題を見てみる。
E - NEQ
提出 #14770926 - AtCoder Beginner Contest 172
別に具体的にどういう数字が書かれているかは気にしなくて良いため、とりあえず$A$が$1,2,3,4,\cdots$に固定されているとして考える。 $B$のすべての並べ方の個数は$_MP_N$である。 ここから$A_i == B_i$となるような$i$が存在する数列を除外していく。
- まず1要素以上が同じパターンは、1箇所を固定した並べ方の個数 * 固定する要素の選び方であり、${M-1}P{N-1} {}_{N}C_1$。
- 2要素以上が同じパターンは、2箇所を固定した並べ方の個数 * 固定する要素の選び方であり、${M-2}P{N-2} {}_{N}C_2$。
- i要素以上が同じパターンは、i箇所を固定した並べ方の個数 * 固定する要素の選び方であり、${M-i}P{N-i} {}_{N}C_i$。
この結果を使って、包除原理でちょうどi要素が同じパターン$(1\leq i \leq N)$をうまいこと除外する。 最後に$A$のパターン数$_MP_N$をかけて完成。 順列や組み合わせの計算を事前に$M$までの階乗を求めておいて$O(1)$で求められるようにしておくこと、 オーバーフローしないように気をつけつつ$10^9+7$で割ったあまりの範囲で計算をすること、 下手なコードを書くと計算量が変わって死ぬことに気をつけると解ける。
あらかじめ準備しておいたModIntを使おうと思ったがうまく動かなかった。 powmodとかも刷新していたが、結局ふつうの関数版を引っ張り出してきて使った。 結果かなりコードに試行錯誤の跡が残った。
memoizeは無駄に使うと逆にTLEの原因になるので注意。 あれの計算量ってどれくらいなんだろうか……
F - Unfair Nim
Eを解いた時点で残り時間がなくなってたので解いてない。 簡単そうな見た目のくせに黄色difficultyらしいのでたぶんEが一瞬で解けてても太刀打ちできなかったはず。