ABC227

ABCGの4完。危ないところだったがなんとか黄パフォ相当を確保。

A - Last Card

クソムズ。簡単なのはすぐわかるけど、入力が3個もあるので状況の把握に時間がかかる。整理すると、mod NでAからK-1回進める。Aを0-indexedに直し、K-1を足してNであまりを取り、1を足して出力。2分ちょいは悪くない(そのくらい大変)。

B - KEYENCE building

図形を真剣に見てしまったが関係なかった。まあでも見ないと不安ではある。S^2の時点で100万。ちゃんとやれば定数倍軽そうであるとはいえB問題でそこに20を掛けるのはやりたくない(冷静に考えると2*10^7だから全然大丈夫なのだが)。aを固定すれば、対応するbが存在するか、するなら何かがわかるので、その方針で。これは式変形と実装に時間がかかる。

C - ABC conjecture

かなり難しい。Aは1万通りに満たないのでそこを固定したくなる(Cを固定するのもちょっと考えた)。さて、そのときの(B, C)の範囲を図示してみると、こんな感じ(AA略)。Bを固定すればCの個数は求まる。1万の2乗くらいの計算回数には収まりそう(だと思ったが勘違いだった(実際には収まるって解説に書いてある))なのでサンプル(最大ケースがあることは確認済み)を試すと間に合うので提出。

D - Project Planning

いかにも典型、というかやったことありそうな見た目。まず貪欲に多いやつから取っていいかがわからない。二分探索は思いつくけど、だから何。全然わからないので次の問題へ。

(追記)解説を見るけどかなり難しい。よく読んでも、何もわからないと自明を行ったり来たりで安定しない。まあ実装しているうちにわかってきた。P人の部署がK個あれば明らかにP個のプロジェクトが作れるけど、このうちの一人が別の(最初のK個以外の)部署に移っても損しない。相異なる部署から選出するという条件に対して、部署が増えるほど得なんだけどそういうイメージを持ってなかった。この損しない操作は何回でも行えるので、とか今思っちゃったけど移った先の部署がP人超えたら明らかにダメだな酷い。だから、P人以下ならOKというのを証明しなくちゃいけない。解説の証明全然わからんな。大きいほうから取ると何が嬉しいのか書いてない。んー。和を取るときにPを超えるものはPまで減らしてしまう。ちょうどPのものがK個以上なら簡単。K個以下(K個以上と被ってるけど)のとき、大きいほうからK個取れば最大値がP-1以下になる。K個取れることも証明が必要で、最大値がP以下で和がP*K以上から1人以上残ってる部署がK個未満と仮定するとどこかの部署がP人を超えてしまう。K個取ったら、P-1まで削って和が(P-1)*K以上となっている。

E - Swap

これは考えがいがありそうだけど、少し考えて何もわからないのでわりとすぐ次の問題へ。

最大ケースでも作れる文字列の種類はそこまで多くない。とはいえ100万とかではなくだいぶ多いので、DPをしようにもどうしたものか。正面からswap操作を考えたとき、全く解けそうにないんだよね。

F - Treasure Hunting

これは二分探索でできそう。面白そうだ。だが瞬殺はできないので、保留。EFを交互に考える感じだったが、Eが無理そうなのでDFで考えてGへ。Gが終わったあとはDを少し見てからFに専念した。

何以上なら拾うかで二分探索。個数は、拾うたびに10^9+10とかのコストをかけて区別するか、DPで個数まで持つか。例えば5を拾ったり拾わなかったりする経路もあるので、盤面の位置も加えて二分探索するとか。色々考えて実装も最後のほうまでやったけど(解法が)まとまらなかった。これは悔しい。

(追記)二分探索ではなく全探索かあ。基準にする値をH*W通り試す(基準値より大きい、または等しくて位置が基準以降にあるものだけを拾う(基準も含む))。そうしたときにちょうどK個拾ったときの最小コストをDPで求める。DPは個数毎に最小コストを持つ必要があった(1WA)。配列を1大きく確保して配るDPすると楽。拾わない選択肢がないことを忘れていつもみたいに最小値更新してサンプル合わなかった。見たことない世界で自分にとってはかなり難しかった(楽しかった)。

G - Divisors of Binomial Coefficient

これは簡単そう。最終的にはすっきり解けたものの、自分のテリトリーを拡大する作業に時間がかかり、結局自分にとってはそれなりに難しい問題だった。ただ、DEFと違って知ってる典型だったので、時間さえかければ進むことができた。

約数の個数は、素因数分解したときに各素因数が何個あるかわかれば求まる(素因数が具体的に何かは知らなくてもいい)。まあ二項係数の公式のやつで考えるのがまずは簡単そう。分子と分母にK個の数が並び、その全てを素因数分解できればよい。10^6までの素数は列挙するとして、しかし分子のほうは大きいので 素因数分解まではできない。ここで、エラトステネスの篩を区間に対して適用するやつを思い浮かべる。10^6を超える素数がいくつあるかわかれば解けると気づいて希望が見えた。10^6までの素数で割り切れるものを除けば素数が残る。長さKの配列に、[N-K+1,N]という長さKの区間を割り当てる。計算量が心配だが、これは全ての整数に対してやってもlogが付くだけで済むので、素数なら(対象区間の整数に占める素数の割合もかなり多いのだが)なおさら大丈夫(たぶんlog(log(N))とか)。数えたいのは素数じゃなくて素因数の中のデカい素数だったので、フラグを更新するのではなく元の数を入れて割り算をやっていく(割れるだけ割るので計算量は増えるがこれも大したことはない)。10^6までの素数に関しては普通にカウントして、残ったデカい素数は種類数だけ数えておく(幅が10^6以下の区間なので10^6より大きい素数はそれぞれ高々1回しか現れない)。あとは数えて掛け算するだけ。

サンプルが通らない。分母はデクリメントなの忘れてた。でかいサンプルだけ合わないので、10^6という定数を小さくしてデバッグ。不等号の向きが逆だった。これねー、分子のほうを素数が残ってるか確認するのに a[i] > 1 と書いてあり、そこに(サンプルが通らないからって)a[i] < (int)1e6 という条件を書き足しちゃったのよね。そもそも最初の条件だけでいい上に、向きが逆。やー反射的に逆にしちゃうよね。そもそも同じ向きの不等号は必要がないから普段書かなくて手がそっちに行かないんだけど、必要だと勘違いしてしまったから。これで10分くらいロスしたのはかなり痛い。デバッグにかけた時間やミスの様子がわかるのは、覚えているわけではなく、ビルドしたソースコードを全て保存しているから。今回のビルド回数は30回だった。