4完。
各問題
A - box
N - A + B
ですね。
B - Various distances
与えられた計算式に従って各距離を求めるだけです。
C - Cream puff
約数を昇順に列挙するだけです。だけ、っていう問題は珍しいですね・・・。
D - Takahashi Unevolved
X * A < X + B
である間はAを掛け続ければよく、これは指数関数になるので回数は大きくはならないので愚直に計算して大丈夫です。
X * A >= X + B
となったらBを足し続けるのですが、これは場合によっては愚直に計算すると計算量が間に合わなくなる可能性があるので、算数を頑張って算出します。とはいえ大した算数ではないですね。割り算するだけです。だたしぴったり割り切れるときだけ注意が必要です。
あと、X * A
がオーバーフローする可能性があるので、最初にy / x
とA
を比較して、オーバーフローするときを別で処理します。この場合Bを足すしか方法はありません。一度でも掛けたらオーバーフローする→Yより大きくなるということなので。
割と考察はすぐにできたのですが、Aを掛けた回数とBを足した回数を足し忘れている箇所が一つだけあって、10分くらいロスしました。サンプルで落ちたのでペナもらわなかったのが不幸中の幸い・・・。
E - Traveling Salesman among Aerial Cities
終了20分前くらいに、各都市は一度ずつ回ればよくて、それはbitDPで解けるらしいということに気づきましたが、実装が間に合わず・・・。これは完全に精進不足がたたりました。
F - Unbranched
チラ見しただけ。
まとめ
ベタなbitDBでいけることになかなか気づけず、気づいても間に合わずで、精進できていないことがまともに響いてしまいました。まあ仕方ない。 緑パフォにとどまりましたが、ノーペナだしレートを落とさなかったのでよしとしましょうか。