パナソニックプログラミングコンテスト(AtCoder Beginner Contest195)に参加しました。

結果

A,B,C問題がの3問正解でパフォーマンスが699でした。B問題もC問題も解くのが遅かったのでパフォーマンスは結構低め… C問題は解き方自体は合ってたのに解答を管理する用変数の型選択をミスったのでWAを量産しちゃった。long longがオーバーフローするのは想定外だった。

A問題

剰余計算してHがMで割り切れるかどうかを判断するだけ。何回か前のABCでも似たように剰余計算してIFで分岐するっていう問題があった気がする。

B問題

B問題にしては難しい気がするけど、解けてる人数見ると普段どおりだからそんなに難しくなかったのかなあ。結局ちゃんとACしてるから良かったけど。

いろいろ試してだめだったので、最終的にはWをAとBでそれぞれ割って個数の範囲に当たりをつけてから、 $個数\times A \leq Wキロ \leq 個数\times B$ を当たりをつけた範囲の下からと上から探索して最初に式を満たす個数を求めました。答えが $x$ とすると、みかん1つあたりの平均の重さは $Wキロ/x$ になるのでこれが $A \leq Wキロ/x \leq B$ の範囲に入っていれば良い。各項を $x$ 倍すると $A\times x \leq Wキロ \leq B\times x$ になるので数式を満たす $x$ の最大と最小を求めればそれが答えになるはず。どのグラム数のみかんが何個って詳細は求められてないのでこれでなんとか解ける。

Wキログラムピッタリにするって方法を考えるのが難しかった。 $X _ {i}$ グラムのものが $N _ {i}$ 個ある時とかならもう少し楽だったと思う。Aグラム以上Bグラム以下の全通りが無限個選択できるって考えると前通りするのが大変だなあって思って。難しく考えすぎてるだけな気もするけど。

C問題

制約をみると $1 \leq N \leq 10^{15}$ なので全探索すると余裕でTLEになるはわかる。と言うことは全探索以外方法を使って探索数を減らさないといけないことになる。順番に整数 $x$ の時コンマをいくつ書くのかだと間に合わないので、3桁後、6桁後、・・・、15桁後のコンマそれぞれが何回書かれることになるのかを考えて数えて数え上げました。例えば3桁後のコンマは1,000～Nまで毎回書かれるので $N-1,000＋1$ 回書かれることになるし、6桁後のコンマは1,000,000～Nまで毎回書かれるので $N-1,000,000+1$ 回書かれることになる。こんな具合に $10^{15}$ まで順番に計算していけば答えが求められる。これが $O(1)$ で求まるってのは意外。順番に数えると $O(N)$ になることを考えるとだからだいぶ早くなる。