125. AtCoder参加記録（AtCoder Regular Contest 144）
29回参加でレート 1289 です。
今回はパフォーマンス 886 です。久々に大失敗。
Aを通して、BDEFは未解答です。Cは通せず。
各問題の思考過程など。
A
11分29秒。
問題文が難しい。とりあえず を最大化することを考えてみる。
を2倍したときに繰り上がりが発生するとダメそうな雰囲気。ということは、使えるのは 4 までの数字。
を最小化したいのだから、桁数をなるべく削りたいので 4 で埋められるだけ埋めて余りは先頭にくっつける…で良いのか？
と考えて、証明できないですがそれっぽいので投げてみると通りました。もう少し早く投げればよかった。
B
解けず。
貪欲法で色々考えていましたが、どうやっても上手く行きませんでした。解を二分探索とか全く発想できなかったので、今回は解けない問題に分類されるものでした。1時間くらい使ってしまったのが非常に勿体なかったです。
C
初回提出108分52秒。解けず。
- 辞書順なので何らかの貪欲法を考える
項めまでは
で埋めていくのが最適。
- これを考えると、
であるときは解を構成できない。
はなるべく 1 にしたいので、
は
に持っていきたい。これが無理になったら
に埋めていく。こんな感じの貪欲法？
手元で考えたテストケースは通ったので投げてみましたが、半分ほど落ちて残念な結果に。解説を読むとそこそこ近いところまで考察できていたようなので、もう少し時間があれば通っていた可能性が高いです。早くBを捨てればよかった。
D, E, F
見てないです。
取捨選択が下手だな～、と悔やまれる結果でした。2ヶ月ぶりに緑パフォを取ってしまいました。ARCはいったん問題文全部見ておいた方がいいですね…。
