2020/01/21-02/03
日記さぼりすぎた...
Solved By kkktym
Topcoder: 0
Codeforces: 267
AtCoder: 1519
AOJ: 62
yukicoder: 10
library-checker: 0
Sum: 1858
ABC189(1/23)
79:55 5完で、レートは1866 → 1854 (-12)。くう...
D - Logical Expression
dp[i][j] := xi まで決めたときに yi = j となるような組み合わせの数、とするDPでおっけー。Nが異様に小さいのは答えがオーバーフローしないようにかな？
E - Rotate and Flip
操作列だけ保持しておいて、クエリが来たら点に対して操作すればいいやつ。操作1,2 は回転行列でいいね〜となるも、操作3,4で困る。定数項がついてしまう。この定数項についても保持しておいて、点と一緒に操作しちゃえばいいことに気づいて事なきを得た。アフィン変換か、なるほど。かなり実装めんどくさかったけどバグらせなくてよかった。
C - Mandarin Orange
O(N2) しか思いつかなくてとばしたけどしばらく考えてもO(N2)しか思いつかない。3000人以上通してるし、O(N2)が間に合うんだろうなーと思って通した...まあ、O(N2)を落としたかったらN <= 105 とかにしますよね...結局ここで順位が決まってしまった。
F - Sugoroku2
期待値DPしか思いつかない。遷移を考える。振り出しに戻るをどうにかしないといけない。え〜どうすんねんってなってたらおわった、くそう...
コンテスト後に解説AC。わからんものはとりあえず変数におく、なるほど。一次式をもって遷移していく、なるほど。初めて見るタイプの問題で面白い。
ABC190(1/30)
43:40 6完 1ペナで、レートは1854 → 1913 (+59)。やったぜ
D - Staircase Sequences
苦手なタイプだけど式変形の選択肢がほとんどないのですんなり解けた。よかった。初項a、項数mとして2N/m = 2a + m - 1なので、mは2Nの約数しか有り得なくて、両辺の偶奇のつじつまが合えばおっけー。
E - Magical Ornament
はい、ダイクストラしてbitDP。ダイクストラで間に合うか心配でBFSするか迷ったけどスピード重視でライブラリを貼るだけのダイクストラでいった。間に合ってよかった。
F - Shift and Inversions
kが1増えると先頭の要素が末尾につくだけなので、転倒数への寄与が簡単に出せる。あとは初期状態の転倒数をセグ木を使って求めて、おわり！ってやったらWAがでた。Fだし、そんな簡単なわけないか、と思って順位表を(このコンテスト中初めて)見てみると、Fがたくさん通されていて焦る。よくみるとオーバーフローしてたので直してAC。この時点ではpredictorくんはが2400パフォを示してくれていてかなり興奮したが、ペナの5分を待つ間にみるみるとパフォが落ちていき、結局60くらいパフォが落ちてしまった。とてつもなく長い5分間であった。
修論
本文を提出して、発表会も無事終わり、今まさに審査を待っているところ。あんなに修論が終わるのが待ち遠しかったのに、いざ終わってみるとやるべきことがなくなって困る。とりあえず飲酒した。
まとめ
とりあえず修論が終わってかなりハッピー。なんかレートも上がっててハッピー。
