AtCoder Beginner Contest ABC407 解法メモ

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

ABC407

ABC407A - Approximation

解法

A/Bを四捨五入をすればよい
ACコード

ABC407B - P(X or Y)

解法

$2$つのサイコロの出目を全列挙し、
条件を満たす度に$1/36$を足していけばよい
ACコード

ABC407C - Security 2

解法

ボタン$A$で桁を出現させ、次の桁との差が作れるようになるまでボタン$B$で数字を回していくことになる
$A$の回数は$S$の桁数そのもので、
$B$の回数は、$S$を頭からみたときに、次の桁との差、$S[i]-S[i+1]$の総和である（$A$の最後には$0$を足しておく）
ただし、$S[i]<S[i+1]$のときを考え、
(S[i]+10-S[i+1]) mod 10としておくとよい
ACコード

ABC407D - Domino Covering XOR

解法

制約から、ドミノの置き方を全列挙し、その際の残った$A[i][j]$の全xorで最大値を更新していけばよい
ドミノの配置の全列挙には、
現在のマスと、どのマスにドミノが置かれているかの配列を持ちながら再帰関数を回していけばよく、
再帰の中で、

• 今のマスと下のマスにドミノを置く
• 今のマスと右のマスにドミノを置く
• 今のマスにはドミノを置かない

に分岐させていけばよい
左上を始点に順に進め、右下まで到達したら、その都度、ドミノのない$A[i][j]$のxorをとればよい
ACコード

メモ

全列挙かとは思いつつも確信が持てず、実装が重くなりそうに感じて躊躇し、再帰関数まで考えが至らなかった

ABC407E - Most Valuable Parentheses

解法

正しい括弧列は全体でみると"("と")"が同数で、先頭からのどの部分列でも")"が"("より多くならない
先頭は必ず"("で、最後は必ず")"なので、
その間を、左から$2$個ずつ"("候補の集合に入れ、都度、一番大きい$A[i]$の箇所を"("に決定して候補から外す操作を続けることで、正しい括弧列を維持しながらスコアを最大にする貪欲法となる
この操作はHeapQueueでの実装が適している
ACコード

メモ

先頭からみると"("が先行する、というところから考え始めたが、$2$個ずつ加えて$1$個取り出すという操作までは思い浮かばない

---

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