結果
50+65+40=155点
150位相当
経過
実施日程 2020/3/16(月) 9:00~14:00
A:二次元グリッド(難易度10.5くらい)
B:転倒数を最小化(難易度8くらい?無限人解いているがわからず)
C:グラフ・ひとつ構成(難易度12)
JOI春2017-自然公園の77点が分かったので、それを提出して正解した
□9:00 (0+0+0=0pt)
コンテスト開始
エディタの準備
Bを眺める
B-満点に対して「ARC088-E PappleSort」の解法を提出すると45点分のサブタスクだけ正解し、WAになる
□9:32 (0+45+0=45pt)
Cを眺める
C-2 成分数が1のケース、深さ優先探索
C-3 木のケース、C-2を利用する
C-1 サイクルのケース、C-3を利用する
□10:19 (0+45+40=85pt)
Aを眺める
A-1からA-3 累積maxの前処理、長方形を決め打って一回O(N)で判定、O(N^5)
枝刈りによってN=200のA-3も正解する
□11:01 (27+45+40=112pt)
累積和によってO(N^4)にすることでA-4の22点を狙うが、700*700*700の配列を作るとコンパイルが通らないため、諦める
累積和を使ったことでH=3のA-5に正解する
□11:21 (37+45+40=122pt)
Bを考える
何も分からない
転倒数を扱う問題全般がよくわからない
□11:53 (37+45+40=122pt)
C-4,C-5を考える
C-4に対して、根をN通り変えたdfs木で木のサブタスクC-3を実行させるが、WA
□12:49 (37+45+40=122pt)
Aを考える
すべてのマスの値が0か1であるA-6を考えると、A-7を含む満点解法の方針がわかる
累積和、累積maxでA-6を提出する
□13:00 (50+45+40=135pt)
A-満点を実装するため、N=8で20点が付けられているB-2を得点しておく
□13:10 (50+65+40=155pt)
A-満点のレジュメを書く
いくつもの細かな箇所で実装の工夫(データ構造)が要求されるため、何を使うか検討する
□13:28 (50+65+40=155pt)
実装を開始する
□13:45 (50+65+40=155pt)
実装が終わる
マスの値が同じものの処理ができていない
処理に足りない点があった
□14:15 (50+65+40=155pt)
出直すことにする
考察
満点級のレジュメ・実装には100分は必要。
「解けたとしたら実装に時間がかかる」というものから時間をかけて考察する。
あと、リアクティブ・マラソンのスコアとか枝刈りの計算量とかの改善への期待と、最適化・数え上げでの正当性への期待は違うもの。