😊

AtCoder Beginner Contest ABC429 解法メモ

2025/10/26に公開

Nim

AtCoder

tech

文中で使用しているのは、たとえCodonが使えようとも、同じくPythonライクでAtCoderに最適な言語の1つNimです

ABC429

ABC429A - Too Many Requests

解法

1..Nの $i$ で、
echo if i<=M: "OK" else: "Too Many Requests"とすればよい
ACコード

ABC429B - N - 1

解法

$A$ の合計からどれか $1$ 項引いたものが $M$ になるかどうかを判定すればよく、
echo if (0..<N).toSeq.anyIt(A.sum-A[it]==M): "Yes" else: "No"とすればよい
ACコード

メモ

$A$ の合計から $M$ を引いたものが $A$ にあるかを判定してもよい
ACコード

A.toCountTableとして、ある種類の数字 $k$ とその出現個数 $v$ の組を求めておく
答えは、
ある種類から $2$ 個取り出す場合の数 $_vC_2=$ v*(v-1) div 2と、
残りの $1$ つを選ぶ場合の数 $N-v$ をかけたものを、
全種類にわたって足し合わせたものになる
すなわち、
for k,v in A.toCountTable: a+=v*(v-1) div 2*(N-v)となる
ACコード

メモ

残りの $1$ つの場合の数を、種類数 $-1$ と早とちりしてWA

ABC429D - On AtCoder Conference

解法

$M$ が大きいので、 $i$ に沿って計算するとTLEになる
ある位置をスタートし、出会った人数が $C$ 以上になって止まるまでに出会った人数 $X$ について考えると、
どこに何人立っているかを整理してしまうことで、
人のかたまりの間のどこからスタートしたところで、初めに人と出会う地点まで等しくなることに気付く
さらに、実際には、高橋君は $0+0.5～M-1+0.5$ からスタートするが、この $0.5$ をずらしても本質的な意味が変わらないことにも気付けば、
$A$ のCountTableをとってkeysでソートし、
CountTableの要素数 $n$ にわたって、前のkeysとの間隔に、そのときの $X$ をかけていって足し合わせればよいとわかる
実際には周回するが、各keysに $M$ を足したものを追加しておけば、 $C\leqq N$ ゆえ十分である
$X$ は尺取り法で、1..nの $l$ に対し、間にいる人数合計が $C$ 以上になるまで $r$ をずらしていけばよく、
$l$ が進むときに、そこにいる人数を減らしていけばよい
$l-1$ と $l$ との距離差をかけながら、足し合わせれば答えとなる
ACコード

メモ

CountTableすべきことはすぐにわかったが、入力例 $2$ のヒントがあるにもかかわらず $i$ に沿った実装を始めてしまい、時間を溶かした
keys単位で算出することにも気付くが、 $0.5$ をずらしても本質に変わりがないことに気付かず、実装できなかった
もちろん、 $A$ の長さを倍にせず、mod n等を使って処理することもできる
ACコード

ABC429E - Hit and Away

解法

すべての安全な頂点からの多始点BFSを考えれば、危険な頂点に最短、次点で到達した $2$ つの時間を合計して答えればよいとわかる
ただし、相異なる安全な頂点からの到達でなくてはならないので、実装においては、
Dequeに(現在の頂点番号,出発した頂点番号,経過時間)のタプルを持たせ、
頂点到達記録用の $d$ は各頂点ごとに配列で用意し、(出発頂点番号,到着時刻)のタプルを加えていく
訪問を許すのは、その頂点の $d$ の要素が $2$ つ未満で、すでに到着していても同じ出発頂点でない場合とすればよい
答えは、BFS終了後、 $S$ を順にみて、'D'のときに、 $d$ の $2$ つの到達時刻の和を出力していけばよい
ACコード

メモ

危険な頂点からBFSし、安全な頂点に $2$ つ達したら打ち止めと考えたがTLE
多始点BFSも考えたが、やはり危険な頂点を始点としたため、実装できなかった

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