日記 10/16–10/31

10/16

射影幾何

講義のための予習
Projective Plane の双対について

群論

準同型・同型、剰余群の復習

競プロ

ARC151 に参加
悔しいことに黄 diff が解けず。対象とする桁が異なる操作を入れ替えられることに気づかなかった
もっと練習して実力を取り戻そう

10/17

競プロ

ARC151-D を upsolve した
これ解けなかったのかなり悔しいな…

射影幾何

数研で講義担当

組合せゲーム理論

LS / RS の性質の復習、証明と Number Avoidance などの証明
難しい…

10/18

競プロ

自作 CLI に若干の不便さを感じていたので、機能を追加した
やっぱり Rust は書きやすいし clap が便利すぎる

10/19

競プロ

今週末 PG Battle があるので、ABC の過去問で練習

10/20

組合せゲーム理論

来週担当なので少しだけ予習。章末問題をちょっとだけ見ていたが、あまり面白いのがなかった

競プロ

昨日と同じく ABC の過去問を何問か

10/21

競プロ

黄、橙 diff を少し
ARC-E でまだ解けていない Random IS を考えてみたが、解けず
赤 diff はどれくらい時間を費やしたあとに解説を見るべきかかなり迷う

10/22

競プロ

PG Battle に参加
かつおぶし全完できてうれしい
チームメイトも頑張ってくれた

組合せゲーム理論

7 章を流し読み。今までとは打って変わって、順序を全く気にしない不偏ゲームの世界
ところで Grundy's game というのが出てきたのだが、簡単なルールなのに Grundy 数の公式が見つかっていないのは意外

その他

今週は ABC274 の tester をしていた
Nim Product を使って Rolling Hash みたいなことをする問題が出たのだが、結局 Nim Product 自体はあまり理解できないまま通してしまったので、また時間のあるときに勉強しよう

10/23

組合せゲーム理論

だらだらと講義資料作成をしていたらなんか一日が終わってた(?)

10/24

組合せゲーム理論

講義担当。毎回、準備した資料にどこかしら穴が見つかるのなんとかしたい

その他

数学研究部の追い出し会に参加した。追い出す側が今年で最後だということに驚き

10/25

競プロ

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_f
https://atcoder.jp/contests/jsc2019-qual/submissions/35959281

「総和が R 以下」から「総和が L-1 以下」を引けば答えが求められる。以降では L に関する条件を無視する。

大きい方から M, M + 1 番目が異なるものを数えることにする。M 番目の値 k を固定して全て調べる。

「大きい方から M 個は k 以上、それ以外は k 未満」から「大きい方から M 個は k+1 以上、それ以外は k 未満」を引いた値が知りたい。 それぞれ  (1-x^k)^{N-M} (\frac{1}{1 - x})^{N+1} x^{R-kM} の係数と  x^{R -(k+1)M} の係数が分かればよい。

 (1-x^k)^{N-M} の二項展開の部分を全探索しても計算回数は  \frac{R}{k} で抑えられるので、 k を全て試すと  O(R \log R) である。

https://atcoder.jp/contests/abc219/tasks/abc219_h
https://atcoder.jp/contests/abc219/submissions/35963479

火を止めるロウソクとその順序を固定したとき、訪れる時刻を  T_1, \dots, T_k として、火を止めるロウソクの最初の長さの総和から  sum T_i を引いた値が得られる。

 \sum T_i は、i-1 番目の地点から i 番目の地点への移動距離を  D_i として、 \sum i \times D_i に等しい

これは逆から考えると簡潔で、移動距離に「今までに火を止めることに決めたロウソクの個数」を掛けた値を引いていくことになる。

逆から考えると、地点  l \lt m \lt r に対し  m \rightarrow r \rightarrow l のような移動はあり得ないので、区間 DP に落とし込める。

更新に  O(N) にかかりそうに見えるが、JOI の Dangerous Skating のような辺の張り方を思い出すと、定数個の遷移でできる。

10/26

競プロ

https://atcoder.jp/contests/abc232/tasks/abc232_h
https://atcoder.jp/contests/abc232/submissions/35978167

上手に実装する問題

https://atcoder.jp/contests/abc247/tasks/abc247_h
https://atcoder.jp/contests/abc247/submissions/35980142

典型

10/27

競プロ

新しいライブラリをすっきりさせた。手元環境も整えてかなり便利になった

https://kodamad.github.io/kod-library/

解いたもの↓

https://atcoder.jp/contests/abc254/submissions/35998383
https://atcoder.jp/contests/abc245/submissions/36000373

教訓 : 109 程度以上の数が現れる数え上げで割り算をする場合、0 除算が発生しないように気を付ける

10/29

競プロ

少し前の ARC でコンテスト中に解けなかったものに再チャレンジした

解法はすぐに浮かんだが、細かい部分を詰める力が落ちており、AC にはかなり時間をかけてしまった。反省

https://atcoder.jp/contests/arc148/tasks/arc148_e

↓かなり遠回りな実装になってしまい、解説を見て実装例の簡潔さにびっくりした。思いついたものをそのまま実装するとこうなった

https://atcoder.jp/contests/arc148/submissions/36069953

その他

PG Battle で優勝した。時間差でどこかに負けているものだと思っていたのでとても嬉しい
チームメイトがミスしたのを気にしている様子だったので尚更勝ててよかった
四連覇目指します

スプラトゥーンとプロセカと原神で一瞬で一日が溶けるので気をつけましょう

10/30

競プロ

(赤になったので) 初めて 5h チーム戦に参加した。正直全然活躍できなかったが、とても楽しかったし、モチベが生まれた。JOI の練習にもなりそう

10/31

組合せゲーム理論

7 章の最後の方を一旦飛ばして 8 章に突入。LS / RS の adorned バージョンや、ゲームの極限みたいなもの、ゲームの cooling など、いろいろと新しい概念が多すぎてついていけなかった。要復習
同じ記号を別の意味で使い出すのをやめて欲しい