ganmo::cout

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

AtCoder Beginner Contest 184

久々に暖まったので

A - Determinant

問題: A - Determinant

-100 \le a,b,c,d \le 100なので,-20000 \le ad-bc \le 20000です.
16bit以上の符号付き整数を使えばオーバーフローせずに正答できます.

拙解(C++): Submission #18302841 - AtCoder Beginner Contest 184

B - Quizzes

問題: B - Quizzes

文字列Sの各文字を左から順に見ていって,oなら1点増やし,xなら1点減らした後,0点未満になっていれば増やす,というのをすれば各文字O(1)で合計O(N)になって間に合います.

拙解(C++): Submission #18308435 - AtCoder Beginner Contest 184

C

問題: C - Super Ryuma

超竜馬は少なくとも3回で任意のマスに到達できるので,r:=r_2-r_1, c:=c_2-c_1とすると,

  1.  (r,c) = 0 のとき0回(移動しない)
  2.  |r| + |c| \le 3 のとき1回(1回移動)
  3.  |r+c| = 0 \lor |r-c|=0 のとき1回(1回斜め移動)
  4.  |r| + |c| \le 6 のとき2回(2回移動)
  5.  |r+c| \le 3 \lor |r-c| \le 3 のとき2回(1回斜め移動+1回移動)
  6.  r+c \equiv 0 \pmod{2} のとき2回(2回斜め移動)
  7. 3回(2回斜め移動+1回移動)

これらの条件を上から順に適用していって当てはまったらreturnをするとACです.
私は 4. を忘れて嘘解法で通してしまいました,難しい…

拙解(C++): Submission #18316367 - AtCoder Beginner Contest 184

D

問題: D - increment of coins

{dp}_{i,j,k} :=「金貨A枚,銀貨B枚,銅貨C枚の状態からいずれかの硬貨が100枚になるまでの操作の回数」とすると,
{dp}_{i,j,k} = 0\ (i \ge 100 \lor j \ge 100 \lor k \ge 100),
{dp}_{i,j,k} = 1 + \frac{i}{i+j+k} {dp}_{i+1,j,k} + \frac{j}{i+j+k} {dp}_{i,j+1,k} + \frac{k}{i+j+k} {dp}_{i,j,k+1}
が成り立って,これらをメモ化再帰で実装して{dp}_{A,B,C}を出力するとACです.N=100として,各O(N^3)個の状態から高々3=O(1)つ遷移が出ているので,O(N^3)で間に合います.


拙解(C++): Submission #18319293 - AtCoder Beginner Contest 184

E

問題: E - Third Avenue

同じテレポーターを2回使うのは無駄なので,そのようにすると遷移がO(HW)回に減ってH,W \le 2000に間に合います.

拙解(C++): Submission #18324412 - AtCoder Beginner Contest 184

F

問題: F - Programming Contest

O(2^N)通りの取りうる和はO(N 2^N)で全列挙できますが,これはN \le 40つまり2^N \le 1,099,511,627,776に間に合いません.半分ずつ全列挙してソートしておき,片方の各和に対してもう片方から二分探索でぎりぎりTを超えない和を探すと,O(N 2^{N/2})になって間に合います.

拙解(C++): Submission #18327848 - AtCoder Beginner Contest 184