進捗
629問 → 636問
[339] [495] [636] [355] [546] [608] [626]難易度 70% まで埋まりました。 80% などは、数ヶ月前は「難易度を見てそっ閉じ」みたいに思っていたやつですが、最高レベルになりたければその辺を殲滅していかなくてはいけませんね。
ここ数週間、AtCoderに時間をとっていたのですが、AtCoderも基本的な経験はある程度できてきたように思うので、また一旦Eulerの優先度を上げようと思います。できれば650問までがんばろう。
感想など
・[339] 戦略の境界を決め打てば計算できるのであとは適当に。結論として出てくる最適戦略は、結構意外だった。
・[495][636] 類題っぽいのにまとめて取り組む。重複を許容した順序対くらいの条件下ならものすごく簡単で、同一視の部分をやりくりするのが本質。分割に対してやりくりするよりも、群作用があって部分群ごとの対称性に属する元の個数のような認識をした方がはかどった。Mobius反転の一般化について色々と調べて学んだ。
・[355] 400人以上解いているが、なかなか解けない。$100$ の場合を手で解き切るも、いまひとつ手がかりが分からない。$N$が巨大なときの構造をいろいろ考えていると、かなり効率の良いパターンを取り続けられそうな気持ちになる。何とかグラフの典型問題に落ちた。
Forumを見ていると、「難しいのになんでこんなに正解者居るの？」な人と「易しいのになんで70%難易度なの？」な人が居た。
・[546] この問題とても好き。場合分けもないかなり短い数式から計算していくだけなのに、なかなか技術を問われる。$f_2(1000)$ を手計算しながらどういうデータの持ち方をしていけばいいか考えた。
・[608] はじめは各 $k$ を、$199$以下の素数をいくつずつ含んでいるかで場合分けをしようとしたが、これは状態数が多すぎて終わらない。$D(6,10)$ あたりを手計算しながら、素数の追加の仕方を整理した。Forumを見たらもう少し上手に解けるようだった。
・[626] これも群作用が関係しそうな数え上げ。だが495, 636とはまた別のネタ。だいたいの方針は結構前から分かっていたのだが、なぜか詰めきれていなかった。
