進捗
514問 → 537問
ゴールデンウィークも終わり、目標1日1問に戻す。500問達成時は、隅々まで簡単な問題を探してかき集めて辛うじて達成した感じだった。そろそろ厳しいかなとも思ったが、力もついてきたのか、過去に諦めた問題も毎日少しずつ思いついたりする。そうやって問題が解けると、ポーカーでオールイン勝負に勝った時の万倍達成感があるよね。
日本人登録の中では 6 位になった。そして上5人は、一気に差が開いていて、625問以上の最高レベル…。うーん、かなり厳しいけれど、しばらく目標に頑張ってみることにする。
- 5/06 [325] [253] [447] [264] [369] [572]
- 5/07 [263]
- 5/08 [292] [606]
- 5/09 [275] [536] [603] [563]
- 5/10 [408] [583] [623]
- 5/11 [353] [648] [262] [256]
- 5/12 [533] [669] [380]
感想、勉強したことなど
・複数の条件が成り立つのかをチェックする場合、成り立ちにくい方から先に並べる。単純な判定だと大した違いにはならないが、条件判定が重い場合にはかなりの違いが出る。
・グラフの最短経路の計算は、scipy.sparse.csgraphにある。アルゴリズムは分かっているし実装経験もあるけれど、なるべくnumpyやscipyの仕組みを使っていく方向に慣らしていきたい。
・全域木の個数って何か知られているのかな？と調べたらKirchhoff’s theoremというものがあるらしい。証明も含めて勉強。
・疎な正方行列の行列式を求めるメソッドが、scipy.sparse.linalgに存在しない！？$LU$分解はscipy.sparse.linalg.spluで出来たのでそれを利用した。疎行列ともだんだん仲良くなってきました。
・[447] 難易度95%を初撃破！この問題は[445], [446]と同じ種類の計算を問う問題になっている。
それなのに難易度評価が跳ね上がっているため、非常な難問という先入観があった。[445], [446]すらそれほど軽い実装という感触がしていなかったし。
実際易しいというわけではなかったが、[445], [446]と比べて飛び抜けた難しさという感じはしなかった。類題のたくさんある典型的な手法とも言えるように思う。ここ1ヶ月でそういう類題をちょうど多く経験していたため、いざ考え始めるとすんなりだった。
・[262] 異色な面白い問題。世の中的に知られている有名な何かを持ってくる問題なのだろうと思っていた。検索するも特に見つからない。全然分からないなりに、出来ることをやってみる。
まずはプロット。データサイエンスでプロット類を学んでいたのが役に立った。
等高線がplt.contourで描ける。詳しくプロットしながら調べていくと、求めるべき高さの条件や、どういう経路を辿るべきかが分かる。そこから先も簡単な立式はできなかったが近似計算は出来た。そもそも上記の等高線の記述だって、内部的に綺麗な立式を使っているというよりはたくさん点を渡しているので、そういうものなのかもしれない。
・[263] 解が見つかるまでの探索量の保証がないまま進めないといけないため、難しかった。その理由もあって、基本的な十分条件で絞るところまでは昔も考えていたが、そこから進めていなかった。具体的な自然数の場合に手計算でpracticalの判定を考えていたら、判定の計算量が十分抑えられることが分かった。
・[256] 何となく手作業でパターンが見えてくる。配置にかなり制約があることは分かってきたが、それでもなかなか考察が難しい。その割には正解者がどうも多すぎる。
というわけで検索していくと、[Tatami Tiling]というワードで情報が落ちていることが分かった。
細部まで自分で産み出すのは大変そうだったので、大体何が書いているかだけ理解して、あとは結果を利用させてもらった。
・[669] 28位。実は、頑張って午前6時出題まで起きていた。簡単に解けそうにはなかったので問題文だけ見て就寝ｗ 昼に起きて、小さい数の場合の例をノートに書いていたら規則が見えてきた。2時間くらいかかって解けた。一意性の証明が分からなかったので、提出してForumでお勉強。
こういう問題はどのようにして思いつくのだろう。見事だ。$99194853094755497$がFibonacci数だというくらいは書いておいても良かったんじゃないかと思うｗ
