AtCoder Beginner Contest ABC413 解法メモ

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

ABC413

ABC413A - Content Too Large

解法

echo if A.sum<=M: "Yes" else: "No"
ACコード

ABC413B - cat 2

解法

HashSet $s$を用意し、
$i$、$j$両方を$0..<N$でまわしながら、
if i!=j: s.incl(S[i]&S[j])
としていけばよい
s.lenが答え
ACコード

ABC413C - Large Queue

解法

用意したDequeに、
タイプ$1$のクエリ$(c,x)$をtupleとして後ろから追加していき、
タイプ$2$のクエリがきたら、
Dequeの前からtupleを取り出しながら、
$k$を$c$減らし、出力すべき答えに$c\times x$を足していけばよい
$c>k$となる際は、答えに$k\times x$を足した上で、
Dequeの頭に$(c-k,x)$を戻しておく必要がある
ACコード

ABC413D - Make Geometric Sequence

解法

$A→B$の並べ替えとは、各要素の絶対値をとってソートすることである
つまり、B=A.sortedByIt(it.abs)でよい
import rationalsとすれば有理数が扱えるので、
A[it+1]//A[it]がすべて同じならYesである
ただし、上記の$B$の定義では、公比が$-1$のとき全項同値になってしまいソートが機能しないので判定が動作しない
$A$の絶対値が全項同じで、正負半々（$Aiが正の項数\times 2-Nの絶対値が1以下$）であれば、それもYesである
ACコード

メモ

公比$-1$の取り扱いに気付かない
rationalsやsortByItがすぐに浮かばず、遠回りした

ABC413E - Reverse 2^i

解法

問題文の操作とは、
全体を半分にした前後の入れ替え、その半分の前後半々分の前後入れ替え、…$4$個ブロック内の前後$2$個ブロックの入れ替え、$2$個ブロック内の前後入れ替えが可能ということである
辞書順最小にするには、最小値を一番左に置くことに徹すればよく、
全体幅から初めて、前後どちらに最小値があるかみて、前半ならそのまま、後半なら反転を行っていけばよい
実装には再帰関数が最適で、
入力数列の最小値の位置によって、そのままか反転を行い、前半と後半に分けて、再び再帰関数を呼べばよく、数列の長さが$1$なら終了とすればよい
ACコード

メモ

セグメント木で最小値を検出、と思い込んで、再帰処理は浮かばなかった

---

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