shining segtree

競技プログラミングとかについて書きます。

ICPC国内予選2017参加記

ICPC国内予選2017に参加したので記録。

 

苦渋の選択で昨年までのチームメイトに別れを告げ、後輩とチームを組む。組んでくださいと後輩にお願いをした。昨年までのチームメイトは競プロからすっかり離れてしまっていたためである。

minami と oshibori と TIke(私) で aotenjou として出ました。

 

 結果は3完。

またアジア地区大会に行けなかった。悔しいなぁ。

 

前日まで の流れ

コンテスト1ヶ月前辺りに一気にDPの勉強をした。簡単なbitDPなら比較的するっとかけるようになったのでとても成果があったと思う。

2週間ほどまえから突然フローを学び始めたが、 minami にフロー全然出なくないですか、と言われ『そうなんだ〜』となる。そしてなぜか精進が途切れる。(←??????)

 

国内予選前日にインターンの面接があり、SAN値減少。1d100。出目が良くて23くらいの減少で済んだ。

その日の夜から配属が決定した研究室の懇親会。

懇親会の自己紹介タイムで競プロ布教をした結果ダダスベリ。SANチェックです。1d100。発狂。

 

当日朝、早起きしすぎて10時頃寝こけてしまって危うくプラクティスセッションに遅れかけたが、絶妙なタイミングで宅配便が来て見事起床。ありがとう佐川急便、ありがとうお中元(?)

 

当日

minami が A を見ながら oshibori と TIke で B を見る。

B読み終えて考察をする。" " で囲まれた中身だけ別にして残りを一つの文字列にして比較する方針を oshibori に伝えたくらいで minami が A AC。めっちゃはやーい。oshibori が B を minami に伝える。TIke は C を見る。Bも一瞬でAC。

Cで何故か愚直解の可能性を完全に捨てて考察をする私。引っ張られる minami 。絵に書いた戦犯プレイの結果コンテスト終了1時間前までかけてO(kn^2m logn)くらいの解法を編み出しバグらせる。kは張る池の深さ。池が張れる横の区間をsetかなんかに入れて始点と終点が一致するか、しなければその下が池を張る区間とかぶっていないかを考える感じ。なんとなくsnackdownを思い出した。

バグ取りが終わりACを取った時には残り8分。

隙間で oshibori がDの考察を進めてくれていたので n が小さい時は半分全列挙して大きくなったら0-1ナップサックで解く解法が生える。半分全列挙まで紙コーディングができていたので残りの8分でそれを写してコンテスト終了。

ICPC国内予選2017はあっけなく終わった。

 

総括

制約を見よう。大切なコンテストは、冷静に取り組もう。

精進をしよう。

 

競プロやめたくなるような体験だったけど不思議とそういう気持ちにはならないのでやっぱり競プロ好きなんだなぁと再確認した。

必至でやってないから好きのままでいられてるだけかもしれないけど!