ganmo::cout

競技プログラミング始めました

AtCoder Beginner Contest 144

atcoder.jp

A - 9x9 (100点)

atcoder.jp
ABが両方とも1以上9以下ならA \times B、そうでなければ-1
拙解 (C++14): Submission #8146375 - AtCoder Beginner Contest 144

B - 81 (200点)

atcoder.jp
九九表のマスは全部で9 \times 9=81個しかないので全部見ても計算機上なので間に合います。
(手計算でも小学校時代に暗記してるから同じようなもん…?)
拙解 (C++14): Submission #8147644 - AtCoder Beginner Contest 144

C - Walk on Multiplication Table (300点)

atcoder.jp
Nが書かれているマスはdNの約数とすると(d,\frac{N}{d})なので、dを全探索すればいいです。
すべてのdは試し割りでO(\sqrt{N})で求められて、移動回数は(1,1)からのマンハッタン距離d+\frac{N}{d}-2なので、制約がN \le 10^{12}と大きいですがO(\sqrt{N})で間に合います。

拙解 (C++14): Submission #8151457 - AtCoder Beginner Contest 144

D - Water Bottle (400点)

atcoder.jp
数学Aです
底面が見える場合とそうでない場合に分けて考えるとatan関数などで角度が求められてO(1)です。
拙解 (C++14): Submission #8146375 - AtCoder Beginner Contest 144

E - Gluttony (500点)

atcoder.jp
答えを決め打って二分探索をすればO(N\log \max_{i,j}\{A_i F_j\})となり間に合います。
まず、\{A_i\}を昇順に、\{F_i\}を降順にソートして割り当てることで成績を最小化することができます。(そうでない場合に入れ替えて成績を小さくできることから)
この成績を達成するために必要な修行回数は各要素を見ていって昇順を壊さないように目標のA_iとの差を足していけばO(N)で求められ、また答えは0以上\max_{i,j}\{A_i F_j\}以下なので、この範囲を二分探索することで計算量O(N\log \max_{i,j}\{A_i F_j\})で修行回数K以下で達成できる最小のタイムが求められます。
拙解 (C++14): Submission #8160009 - AtCoder Beginner Contest 144

F - Fork in the Road (600点)

(まだ手を付けていません)