Hatena::Grouptopcoder

Hiro180の日記

 | 

2018-12-31

Good Bye 2018 10:10

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マスターになるかライブラリを整備するかを早くやってください...

 |