AtCoder Beginner Contest ABC410 解法メモ

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

ABC410

ABC410A - G1

解法

$K\leqq Ai$となる数を答えればよいので、
A.countIt(K<=it)とすればよい
ACコード

ABC410B - Reverse Proxy

解法

$Xi=0$である場合に対応するため、各箱にいくつボールが入っているかの配列$c$を用意し、管理していけばよい
$Xi=0$である場合は、c[c.minIndex]にボールが入る
$Xi$ごとにどの箱にボールが入るか記録していけば、答えとなる
ACコード

ABC410C - Rotatable Array

解法

タイプ$3$のクエリで発生する配列要素の回転数$d$を管理すれば、実際に$A$の要素回転を処理する必要はない
クエリ$3$をd+=kとすれば、
クエリ$1$はA[(p-1+d) mod N]=xで、
クエリ$2$はA[(p-1+d) mod N]である
ACコード

ABC410D - XOR Shortest Walk

解法

各頂点での辺の重みのXORを持ちながら、頂点$1$から$N$までの全探索をしていく
訪問済みかどうかの判定を、単なる頂点番号でなく、頂点番号とその時の辺の重みのXORのペアとすればよい（頂点倍加）
頂点$N$で到達できた辺の重みのXORの中で、最小値（なければ$-1$）を答えればよい
ACコード

メモ

閉路もあり得るが、XORだから2周以上はない、というのがキーになるのではないかという考えに固執し、TLEを続けてしまった

ABC410E - Battles in a Row

解法

体力、魔力とも制約が小さいため、
dp[$i$体目目のモンスターを倒したところ][そのときの体力値]=残り得る魔力の最大値
のDPを考えれば、
体力を使った場合の
dp[i][j].max=dp[i-1][j+A]
と、魔力を使った場合の
dp[i][j].max=dp[i-1][j]-B
にわけて、更新していけばよい
$dp[i][0]<0$となった$i-1$（もしくは負にならずに最後まで倒せた場合の$N$）が答え
ACコード

メモ

DPだろうとは思いつつも、どう置けばよいかがわからない

---

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