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

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

$(r,c) = 0$ のとき0回（移動しない）
$|r| + |c| \le 3$ のとき1回（1回移動）
$|r+c| = 0 \lor |r-c|=0$ のとき1回（1回斜め移動）
$|r| + |c| \le 6$ のとき2回（2回移動）
$|r+c| \le 3 \lor |r-c| \le 3$ のとき2回（1回斜め移動＋1回移動）
$r+c \equiv 0 \pmod{2}$ のとき2回（2回斜め移動）
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

ganmo::cout

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

AtCoder Beginner Contest 184

A - Determinant

B - Quizzes

C

D

E

F