2018-12-31
■ 2018年の目標振り返り
- SRM, CF レート 2700
SRMは2605 (MAX: 2646)、CFは2918 (MAX:2918)でした。 SRMに関してはHardを5-10人くらい解く回が多くて、そういう回にEasyMedしか解けないと1桁順位が取れないので2600近辺で停滞しています。
ちゃんとHardを解けるようにならないと大きく上げるのは無理だし逆にそれができれば一気に上がると思います。
CFは完全にインフレしているんですが、(バーチャルを含め)外れを引かなければかなり上位に入れることも増えてきたので形式が得意なのかもしれません。
- AtCoder レート 3200
2989 (MAX: 2989)でした、夏場までAGCでやらかし続けて恐怖症を発症してたのでしょうがないね。
直近3回は14位->45位->21位なのでだんだん自信がついてきました。
- 国内予選かアジア地区どちらかで優勝する
3位と4位です。(去年より悪くなってないか？)(ごめん) どちらも戦犯をしてしまったのでICPC練習をしていかないといけない......
- 研究室でまともな結果を残す
これも完全にごめんなさいで、あんまりコミットできなかった (来年はやるぞ)
- Deep Learning系で何かいいインターンを探してやる
PFNに行きました、パソコンに少し詳しくなりました (詳細は秘密です)
- 生活リズムをまともにして授業に出る
さすがに二十歳にもなると自分の人間性がわかってきたので今後この手の夢物語を語るのはやめます
■ Good Bye 2018
5年ぶりにGood Byeに出ました、前回は+168してるらしく相性が良いと信じたい
コンテスト開始、前から潰す派なのでAから順に見ていく
A
流石にやるだけ、制約に優しさを感じる -> pass
B
ちょっと考えて、sumを取って/nするだけでよいことがわかる、がintだと溢れるね -> pass
C
本質はgcd(x,n)だからnの約数を見ればOK、典型 -> pass
D
そのものと、跨るものを数える必要がある -> 跨るものって1....nのpermutationじゃないとダメじゃない？
-> なんで？ -> 差分が 負 -> 正(max-minが足されるので) -> ..(足される値は単調減少).. -> 0 になってるからだね -> pass
E
次数列としてvalidか判定するのはUSACOとみんプロでみた -> みんプロの解説pdfを見る
-> 追加するものが0...n各々に対してlogくらいで判定できればOK -> どこに入るか分かれば、左と右の値の変化は簡単にわかる (実装は楽ではない) -> .... -> pass
F
飛べるのはLだけだと思ってて自明すぎるだろって思う -> テストすると合わない(それはそう) -> 誤読に気づく -> うーん、よくわからないけどダンジョン(JOI)とかガソリンスタンドのアレみたいなタイプだろう -> とりあえず飛べるのはLだけと思ってやって、実際に使った分(歩きと泳ぎ)を後から飛行に変える、でうまくいくね -> 泳ぎより歩き、手前より後ろを優先するのはいいけど手前の歩きと後ろの泳ぎってどっちを優先するべきなんだ -> どう考えても手前の歩きだね -> 遅延評価segtreeを貼る、N<=10^5だし1secでも大丈夫だろう -> pass
E(見直し)
なんとびっくりにぶたんの初期化を間違っていて明らかにやばい挙動をするケースがすぐ作れたが.... -> 許せね～～～～～(リサブ) -> pass
F(見直し)
解法は正しいと信じる、実装にミスはなさそう
G
なんとあれだけ痛い目を見たのにまだ多倍長のライブラリを作っていない + I hate reactive problems -> 閉じる
H
読解が難しいがサンプルを見るとわかる -> 座標に意味はないので差分を取る -> 2*n個の山から1つ選んで石を取る問題に帰着される -> grundy数計算 -> ... -> 埋め込み??? -> 無理そう -> OEISにはない... -> パッと見値が大きくならなそう？ -> 30000まで計算してもMAXで25 -> ということは、bitsetで/64する系で攻めればまともに解ける気がする -> 動かせる数を前計算して「鋳型」みたいなbitsetをつくって、xのgrundy数がkだったらk番目のbitsetにxシフトした鋳型をorする、とかすると簡単に計算できる、計算量もsum(grundy_number)+200000^2/64だし絶対通る -> pass
System Test
全部通る
Rating
2833 -> 2918
感想と反省
Eのリサブ以外はOK。落ち着いて実装を詰めてから始める癖をつけたらバグりにくくなった気がする。
多倍長に関してはpythonマスターになるかライブラリを整備するかを早くやってください...
