🙌

AtCoder Beginner Contest ABC402 解法メモ

2025/05/06に公開

Nim

AtCoder

tech

文中で使用しているのは、PythonライクでAtCoderに最適な言語の1つNimです

ABC402

ABC402A - CBC

解法

S.filterIt(it.isUpperAscii).join
ACコード

ABC402B - Restaurant Queue

解法

行列に並んでいる人の食券の番号を格納するdequeを用意し、
クエリ $1$ で、 $X$ をaddLastし、
クエリ $2$ で、popFirstしたものを出力すればよい
ACコード

ABC402C - Dislike Foods

解法

各料理は、食材のうちで最も克服する日が遅いもの、すなわち、 $B$ で最も大きな配列位置の日に、食べられるようになる
初めに $B$ の入力まで読み込んだ上で、
答えとなる項数 $N$ の配列 $a$ に、
各料理が食べられるようになる日に $+1$ していく
最後に $a$ の累積和をとったものが答え
ACコード

メモ

$A$ の入力をとる際に、同時に、その食材がどの料理に使われているかの逆引きも作っておけば、 $Bi$ の順に、各料理の食材使用数を減じ、 $0$ になったら答えをカウントアップする、とすればよい
食材名を克服した日付にリネームしてしまえば、各料理の $Ai$ の最大値がその料理を食べられる日付になる

各直線の傾きは $2$ 点を選べば決まる
さらに、図を見ていくと、 $2$ 直線が平行であるということが、
(Ai+Bi) mod Nが等しくなるということだとわかる
よって、傾きの種類は $N$ 通りである
$M$ 本の直線の傾きの種類を調べ上げ、同じ傾きにならないペアの数を数えればよい
これは、余事象を求めるべく、すべてのペアの数、N*(N-1)/2から、各傾き毎に、その傾きになる直線のペア数 $n$ に対して、n*(n-1)/2を引いていけばよい
ACコード

メモ

異なる傾きになるペアを愚直に数え上げると、当然、TLEになる

ABC402E - Payment Required

解法

いわゆる期待値DPで、
dp[どの問題が正解しているかのbit][所持金]=これから得点する期待値の最大値
として、
dp[1 shl N-1][0]=0.0（全部正解していれば、これから得点する期待値は0.0）を初期値に、
dp[i][x].max
=(dp[i+1 shl j][x-C[j]]+S[j].float)*P[j].float/100.0
+dp[i][x-C[j]]*(100-P[j]).float/100.0
（（一歩先状態の期待値＋進捗分の得点）×確率、の総和）
の遷移式を、
$x$ を0..X
$i$ を0..<1 shl N
$j$ を0..<N
で回せばよい
dp[0][X]が答え
ACコード

メモ

期待値DPだろうとは思いつつ、1円あたりの得点期待値順に解けばよいのではないかと思い、再帰的に期待値が計算できないかと考えたが、WA＆TLE
期待値DPの遷移式が作れない

反復学習にはmochiがおすすめ
全問入ったdeckはこちら