virtualを2/20 16:30~21:30でやった
100+15+100=215pt
日程内一位タイ(5人)
結果が出せてよかった
難易度は6-11-10らしい
難易度が分からない状態で取り組む練習をした
本番のフロー
問題を印刷しながらアニメを見る
0:00 - 0pt
geanyにcppファイル7つとtxtファイル1つを作成する
テンプレートを書く
0:03 - 0pt
問題文を開く・配点の確認をして難易度をエスパーする
0:05 - 0pt
問題1(JOIOJI)を見る
配点が5-15(二乗)-80(準線形)と荒ぶっていて、区間の問題だったので、満点はバケット法とか分割統治の難易度11~12だと予想する
満点を念頭に二分探索を考えたが、嘘だったので二分探索を潰してO(N^2)にした
提出すると、WAが返ってくる
0:15 - 0pt
尺取り法がバグっておりデバッグで時間をロス
0:31 - 20pt(+20)
問題2(かかし)を見る
これも配点が5-10(二乗)-85(準線形)と荒ぶっていて、半順序の問題だったので、満点はバケット、分割統治の難易度11~12だと予想する
1問目と違って満点を考えるとすぐに闇が生まれてしまうので、最後に回すと決める
愚直に累積和を書いて提出
0:55 - 35pt(+15)
問題3(電圧)を見る
配点が10-10-35-45と平和で、小課題2と3は満点へのヒントになりそうなので、時間をかけることにする
適当に考察して、小課題2が解けた気になり、Mをそのまま出力するというひどいプログラムを提出し、WA
1:05 - 35pt(+0)
小課題2の誘導に従い、木をひとつ決めるという方針を取る
"いつかのDDCCで見た"という気持ちになる
場合分けを2回くらいして、木以外の辺について、木のパスを埋めるという問題にする
愚直に実装すると、小課題3が100*Nくらいの計算量で解けることがわかる
そして、小課題4がHL分解で解けることがわかる
ローリスクな選択として、小課題3から通すことを決め、実装、提出する
提出すると、なぜか小課題1,2だけACし、20点
2:16 - 55pt(+20)
嘘解法を疑うが、嘘が見つからない
配列のサイズを大きくしたら小課題3もACし、20点→55点
2:25 - 90pt(+35)
問題1に行くかHL分解を書くか迷ったが、確実にHL分解を書くことにする
気合いでHL分解を書き、提出するが、半分AC、半分WAとなる
3:03 - 90pt(+0)
クエリ処理を疑い、HL分解を疑い、小課題3を嘘解法で通してしまったことまで疑ったが、一番信頼していたSegtreeに初歩的なバグがあり、それが原因だった
提出し、満点を得る
4:04 - 135pt(+45)
"平方分割を爆速で実装すれば間に合う"という気持ちで問題1の満点を考え始める
実はこの問題は難易度6なので、すぐに満点解法が得られてしまう
実装するとACし、満点を得る
4:14 - 215pt(+80)
"今度こそ平方分割を爆速で実装すれば間に合う"気持ちで問題2の満点を考え始める
しかし、この問題は明らかに難しく、怪しい平面走査しか生えない
悲しい気持ちになり、残り10分になったので投了する
4:50 - 215pt(+0)
反省
今回のセットではこれ以上の点数を取るのは難しかったかもしれないが、バグ取りによる時間のロスが大きすぎる。配列のサイズに10分かけるのは論外だし、問題1で適当な実装でWAを出し15分かけたのも厳しい。何より、問題3のバグ取りに1時間かけたのが痛い。UnionFindより上級のクラスは個別でテストすることにする。簡単な小課題でもナメずに紙に設計してから実装する。
