進捗
537問 → 562問
625問を意識して、まだまだ頑張る。20問解けと言われるととても不可能に見えるけれど、解けそうな範囲に5～10問見えているというような状況が何とか継続している。相変わらず暇な時間はほとんどEulerを考えて、気づけばどんどん正解数が積み上がっていく。いくら1日中張り付いても、日に9問も解けるのはそろそろ最後かな。
- 5/13 [637] [362] [564]
- 5/14 [462] [412]
- 5/15 [466] [617] [308] [642] [419] [486] [519] [409] [352]
- 5/16 [574]
- 5/17 [398] [534]
- 5/18 [470] [651] [567] [568] [289]
- 5/19 [513] [532] [661]
前週に200番台を多めに考えていた。今週289番を倒して、300番まで制覇。
特別大事な意味があることではないが、やっぱり「埋まる」のは嬉しい。
感想、勉強したことなど
・対称群の表現論の復習。Young図形が$S_n$の既約表現と対応して、tableauの個数がその次元に対応する。個数はHook length formulaの形で綺麗に書ける。
・群作用の軌道の数え上げ。綺麗に出来た！と思ってForumを確認したら、Burnsideの補題として知られている結果だった。証明も含め易しい定理ですが、綺麗で実用的ですね。
・巨大な二項係数${}_n\mathrm{C}_k$の計算。$\log(n!)$をメモ化しておいて$\exp$で取り出す方法だと誤差が大きかった。$k$は小さかったので、普通に分数で順番に計算。「こちらの方が精度が良い」の知見は少しずつ増えているけれど、今実装している方法がどの程度の桁数の保証があるのかなかなか意識できないです。
・[298] 綺麗な問題。[1～300]埋めのラスボスとなりました。とはいえ、どうすればdpに出来るかをよく考えれば、それほど非自明な考察は不要。GW中には方針もはっきり見えていたし、少し計算量の多い方針で$L(3,3)$まで出せていた。やや実装難で、のんびり実装・デバッグできる時間のある日にやろうと後回しになっていました。計算量自体はかなり余裕があり。
・[308] Wikipediaの解説を見ても、即コーディング出来るほどの情報量はない。とにかく手計算して仕組みを理解する。大きい素因数は、何らかのフラグくらいの使われ方で、小さい素数の個数に主要な計算を持っていることが分かってくる。おおよその仕組みが理解できても、ミスなく実装するのがこれまた大変。naiveな実装と見比べてデバッグしながら実装。解いている人数の割に、難しかった。
日曜日はお出かけしたため、新問の速解きには不参加。
