AtCoder Beginner Contest ABC409 解法メモ

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

ABC409

ABC409A - Conflict

解法

$Ti$と$Ai$が両方'o'であればよい
ACコード

ABC409B - Citation

解法

$x$は高々$N$で、$N\leqq100$なので、
$x=N$を初期値に$1$ずつ減らしながら、
$Ai\geqq x$である要素の個数が$x$個以上であったら、その$x$を出力すればよい
ACコード

ABC409C - Equilateral Triangle

解法

入力はすべて整数なので、L mod 3!=0ならば、答えは$0$
$d$の初項に$0$を足してから累積和をとれば、点$1$からの距離を示す配列になる
各要素のmod Lをとれば、0..<Lの距離で表すことができ、そのCountTableをとれば、各位置での点の個数が出せる
そのCountTableのkeysにL div 3を$1$回足した位置、$2$回足した位置もkeysの中にあれば、各valuesをかけ合わせただけの正三角形の組み合わせがあるといえる
その総和が答え
ACコード

ABC409D - String Rotation

解法

$S$を頭から見ていき、
「$i$文字目が次の文字より大きければ$i$文字目から巡回シフトした方がよく」
その巡回シフトは、
「$i$文字目が、$i<j$なる$j$文字目より小さくなる手前（そうならなければ最後）まで行うとよい」
NimではrotatedLeft(1)が使える
ACコード

ABC409E - Pair Annihilation

解法

ある葉の$xi$は$0$でない限り、必ずそれを結ぶ辺を通る
同様に、根付き木としてみれば、ある辺から先の部分木は、中に含む$xi$の合計（プラスマイナス相殺）分、その辺を通る
DFSをしながら、その絶対値と重みとの積を数えていけばよい
具体的には、DFSの返り値を$xi$の合計値として、
親に向かう以外の辺すべてにわたって加えながら、
同時にそれらの絶対値に$wj$をかけたものを答えに加えていく
最後、帰りに自分自身の$xi$を足せばよい
ACコード

メモ

$2$点間の重みの最小値を求めることにこだわり、$425$点にもかかわらず、オイラーツアーだの、ダブリングだのと思い悩んだ
それが求められたところで、どの道、この制約では重みの最小値から貪欲に計算していくことはできないのではないか、と思ったものの、正解の解法には至らなかった

---

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