ARC103 反省
CとDの部分点の1.5完. とれるところは全部とれたと思う. けど立ち回りがよくなかった.
C問題
問題
解法
偶数添字と奇数添字でグループ分けできる. それぞれで最も数が多い数字にするのが最善であるが, その数字が同じだったときの処理が面倒(最後のサンプルで気づいた).
具体的には, 数字の数が最も多い数字を記録しておき, プリオリティーキューに偶数番目と奇数番目の数字の数を別々のものにいれておき, 数字が一致してしまったときに, どっちかのキューの2番めに大きいものと交換して差が小さくなる方を選ぶと最善.
感想
コンテスト中はコーナーケースあるのでは？とか考えてちょっと提出をためらってしまいました. 実装も面倒で面倒な問題です.
D問題
部分点のみで, 後で満点は解き直します.
解法
部分点解法のみ.
まず, がんばって問題文を読解します.
各について,
を考えます. この値が異なるものが存在したとき, どうやっても答えを構築することはできません.
なぜならば, をどのように設定してどのように足しあわせても, 各
の和の偶奇は不変で, 偶数グループまたは奇数グループについて, 移動しえない場所が存在してしまいます.
上の条件を満たしていると考えると, すべてのについて,
としたとき, 部分点の制約ならば十分小さい
で構築が可能であることがわかります.
具体的には,
のとき,
として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
のとき,
として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
これを実装して300点です.
600点はまた今度...
感想
和の偶奇とかいうの, 結構当てずっぽだったんですけどヒットしたみたいでよかったです.
総評
Cを遅解きしたあと順位表を見てみると, 誰もDをやっていなかったのでEを見たんですが, 結局は解法は生えずに結構な時間を費やしてしまったので, 結果論ではありますがDをもっと速く考えていればレートは伸びたかなーと思います.
コンテスト中は自分の身の丈にあった問題を考察していきたい.
rating 1089->1134
