AtCoder Beginner Contest ABC414 解法メモ

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

ABC414

ABC414A - Streamer Takahashi

解法

リスナー毎に、
Xi<=L and R<=Yiであれば、答えに$1$を加えていけばよい
ACコード

ABC414B - String Too Long

解法

l.max>100 or l.sum>100であればToo Longと表示し、
そうでなければ、答えとなる文字列にci.repeat(li)を連結していけばよい
ACコード

メモ

オーバーフロー対策であるl.max>100を条件に入れずにRE

ABC414C - Palindromic in Both Bases

解法

十進法の回文となる数を列挙し、それが$A$進法でも回文となる場合足しこんでいくことを考える
$N$の桁数をみて、その半分（($N).len.ceilDiv(2)）の桁までの正の整数を列挙し、反転して繋げれば回文ができる
その際、そのまま繋げれば偶数桁の回文に、反転した後、$2$文字目以降を繋げれば、奇数桁の回文が生成できる
出来上がった後に、$N$以下かどうかのフィルターをかければよい
整数$n$を$A$進数に変換するには、変換後の各桁を表すDeque $a$に対し、
while n>0: a.addFirst(n mod A); n=n div A
とすればよく、
a.toSeq==a.toSeq.reversed
であれば、$A$進数も回文、ということになる
ACコード

メモ

あらかじめ$N$以下の回文を生成することにこだわってしまい、時間を溶かした

ABC414D - Transmission Mission

解法

家の座標$X$をHashSetに入れて重複をなくし、ソートしたものを考える
$M=1$なら、答えはすべての家を覆えばいいのでX.max-X.minとなる
次に、$M=2$なら、家の間隔が一番広いところを空けて、残りの範囲をカバーすればよいから、各家の間隔を配列$d$とすれば、
X.max-X.min-d.maxとなる
つまり、答えは、$d$を大きい方から$M-1$項除いて足し合わせた数となる
ACコード

メモ

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

ABC414E - Count A%B=C

解法

動かすときに、条件を満たす$(a,b,c)$の個数がどうなるか考えるべく、ある$b$で固定すると、
$a<b$だと$a=c$となってしまうので、それを除いた$b～N$の個数から、
$c=0$となる、$b～N$の範囲の$b$の倍数の個数を引いたものになるとわかる
しかし、$N\leqq 10^{12}$のため、$b$に沿って計算していくわけにもいかない
前半は、$b$が$1～N$と動けば、初項N、最終項1の等差数列の和なので、一気に

$$\frac{(N+1)\times N}{2}$$

と計算できるが、
後半は、$N$を$b$で割った商、N div bが同じ値である区間をまとめて計算することを考える
入力例$1$の$7$は、$4$で割った商も$5$で割った商も$6$で割った商も$7$で割った商も$1$なので、$商1\times 4個分$の$4$つ、$c=0$となる倍数がある、と計算する
実装としては商$i=1$から始めて、
$i～N$までの倍数の数N div iに、倍数の数が同じになる$i$の最後の数、N div (N div i)までの$i$の個数をかけたものを足し合わせる
$i$の最後の数$+1$を次の$i$の値にしてこれを$N$まで繰り返していけばよい（商列挙）
このようにして得た後半を前半から引けば答えとなる
ACコード

メモ

商列挙のアイディアは出ない

---

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