Quiz
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_b
Submit
https://atcoder.jp/contests/wupc2019/submissions/4549977
解法
- まず明らかな解をつぶす
- 最初から全部0ならクリア
- 5が存在しないなら無理
- 後は5を1つ残して他全部を連結して変換する
- 全てが5以下になったら全部を連結して変換
1 2 3 4 5 6 7 8 9
コーナーケース
- HまたはWが1のとき、5が領域を分断してしまい、5以外を全部変換できない
- 5は複数ありうるので、最後まで残す5を全探索し、左右の領域それぞれの最大値から、左右の変換数が求まる
1 2 3 9 1 2 3 5 1 2 3 8 1 2 3
感想
- コンテスト中は解けず
- 途中までAC, 途中から全WAとなったので「???」となった
- 途中までランダム生成データ
- 途中からコーナーケースを意図したデータ
- が置かれていたのだろう
- 今度同じ現象を見たら、コーナーケースを疑おう
