/ 最近 .rdf 追記 編集 設定 本棚

脳log[20210718] AtCoder Regular Contest 123/C 問題 1, 2, 3 - Decomposition (+ B + A)



2021年07月18日 (日)

最終更新: 2021-07-19T22:56+0900

[AtCoder]AtCoder Regular Contest 123C 問題 1, 2, 3 - Decomposition (+ B + A)

悔しいなあ。手も足も出ない方がまだあきらめがつく。

 提出 #24373137 (WA×20 / RE×12 / AC×2)

1時間かけてコンテスト終了直前に投げた。サンプルすら通っていないけど、5つあるケースの最後の1つの答えが違っているのに気がついていなかった。ダメダメである。

RuntimeError の原因は Array#compact が false を取り除いてくれていないのに気付かずそのまま min メソッドを呼んだこと。

Wrong Answer の原因は比較して小さい方を選ぶべきところで、勝手に優先順位を付けて先に値が得られた方を選んでいたこと。それともう1か所(b+(d-1)%10 の %10 が完全に余計)。

プログラムの型は Send More Money と同じ>20210412p01。桁を見て、キャリー(ボロー)を伝えて、最後まで矛盾なく桁が確定できるかどうか。それを k を増やして条件を緩和しながら最小値を探った。

答えの上限が5だと見抜いていたところは偉いと思うんだ。なぜ5かといえば、項数が1ならある桁に関して作れる数字が 1..3。2なら 2..6、3なら 3..9、4なら 4..12、5なら 5..15 ということで、最初に 10 種類の数字が作れるのが5項の和。0..4 の数字を作ろうとすると繰り上がりが不可避なのが制限だけど、それは隣の桁で吸収できる。6以上に項数を増やしてもできることは増えない。

 提出 #24375535 (AC)

ほとんど違いませんよ。でも A から F まで6問ある中の3問しか相手にしていないのに、時間内に完成させられないんだなあ。

実行時間から判断するにだいぶ無駄が多いみたいだけど、制約に苦しめられてたったひとつの解法、たったひとつの記述を探らないでいいってすばらしい。

 B 問題 Increasing Triples

ただの貪欲。提出まで 15 分>提出 #24363550

 A 問題 Arithmetic Sequence

AC まで 2 WA、33 分。どういうこと? 10 分時点で9割5分は完成していた>提出 #24355415。デバッグ出力を消し忘れてるのと、入力を勝手にソートしてるのがいけない。列(Sequence)は順序付き!(知らないわけではない。括弧と波括弧に使い分けがありそう? それは知らない)

AC>提出 #24361099。ほとんど違いませんよ(2回目)。