| A | B | C | D | E | F | |
| 問題文 | ■ | ■ | ■ | ■ | ■ | ■ |
| 自分の提出 | ■ | ■ | ■ | |||
| 結果 | AC | AC | WA |
全体感想
84分2完で241位でした。
おー、ついにレート下がりました。でもまだまだがんばるぞー。
160分コンテストで、長めの時間ですが、それでも解けるレベルのものを解き切るのが難しいなあ。
考察も実装も運が悪い方に転ぶとあっという間に30分60分飛ぶ感じ。いろいろ噛み合わないとこのくらいになっちゃうのは避けにくいなぁと。
でもやっぱりそれってまだまだ実力不足なんですよね。大学受験数学とかも、平均的な学生だと簡単に方針で迷走したり実装（計算）ミスしたりしまくって1完2完とぶれるゲーに見えるけれど、実力でオーバーキルしていればちょっと失敗しても十分満点付近が確保できますし。
あとは順位表を見ていて、がくっと正答者数が下がるところを解けないと最上位には行けないなと思った。制限時間ぎりぎりで3完したところで、それほど大きく成績が変わらない。難問力はこれからやり込めばまだまだ引き上げられると思うので、頑張っていきたい。
9月くらいからもうちょっと本気出します。
問題A – Triangle
三角形の頂点のうちひとつはbounding box上にある．したがってひとつは原点としてよい．
残り $2$ 点を$(a,b)$, $(c,d)$ とすると，面積が $\frac12\lvert ad-bc\rvert$ となることは流石に知っていた．高校数学の座標幾何でもある公式で，行列式と思うのも簡潔．また算数レベルの説明もあります．（1枚目 = 2枚目 = 3枚目/2）
$a,b,c,d$ をどう見つけるか．そもそも制約がなければ自明なので不等式の制約が本質的である．
$S = 10^{18} – 100$ みたいなときを考えると，$a = b = 10^9$ が唯一の選択肢であると分かる．同じような構成がどのような範囲で使えるのかを考えていると，$a = 10^9$ で全部作れることが分かった．
問題B – Do Not Duplicate
入力例4を手計算する．「ここからここはどうせ消えるから計算しなくてよい」を捨てるゲームっぽい．もう少し考えていると，十分長く続けていったときに「今先頭に書かれている数」がいずれ消えて，そこでゲームがリセットされることが分かった．
例えば，
[3 1 4 1 5 9 2 6 5 3][5
3 1 4 1 5][9 2 6 5 3 5
3 1 4 1 5 9][2 6 5 3 5
という要領である．
「第0項から初めて残り97周」→「第10項から初めて残り97周」→「第5項から初めて残り96周」
などなど．このルールを作って，あとは周期を見つけてまわしていけばよい．
実装時に何度か迷走しました．ひとつは，一度きちんと制約をチェックしたはずだったのに $K\leqq 2\cdot 10^5$ と勘違いしていた点．この場合周期を見つけなくても，1行分次の行に進めるように情報を持っていれば計算ができる．これで実装を完成させても当然TLEしますし，しかもコードの主要な部分を書き直す羽目になって本当に無駄をしてしまった．解答のダブリングも考えたが，状態が $N$ 通りしかないので，周期を見つけて周期分まとめて進む形でやれば計算量は $O(N)$ で済む．
問題C – GP 2
（$(1+x+x^2+\cdots+x^{2M})^N$ における $x^{3M}$ の係数と思ってそうなった）．
この時点でだいぶタイムロス．ここはただの二項係数だった．和が $3M$ になるのは二項係数ひとつだし，余事象も反例となる点が重複しないので二項係数である．
全部1個にならないようになっていれば帰納法が回る．と雑に考える．
