📝

AtCoder Beginner Contest ABC411 解法メモ

に公開
Nim
AtCoder
tech

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

ABC411

ABC411A - Required Length

解法

echo if P.len>=L: "Yes" else: "No"
ACコード

ABC411B - Distance Table

解法

Dの頭に0を加えてから累積和をとっておけば、
iを0..<N-1で回して
(i+1..<N).toSeq.mapIt(D[it]-D[i]).join(" ")
を出力すればよい
ACコード

ABC411C - Black Intervals

解法

答えとなる黒が連続する区間の個数aは、
左右が白でAiも白ならa+=1、Aiが黒ならa-=1
左右が黒でAiも黒ならa+=1、Aiが白ならa-=1
左右が違うなら、aは増減なし
つまり、
左右が一緒の時に限り、
Aiとも一緒ならa+=1、さもなくばa-=1をすればよい
実装では白の番兵を両端に立てておく（初めにN+2の配列を作っておく）とよい
ACコード

メモ

番兵を立てずに、すべての場合分けを細かく書き起こしてしまった

ABC411D - Conflict 2

解法

クエリを先読みしてから、逆に処理することで、参照元を追跡することを考える
最後の参照元はサーバー（PC0）なので、そこから、
クエリ1：もし、今の参照元がpなら、参照元を0に変更
クエリ2：もし、今の参照元がpなら、答えの「頭に」sを追加
クエリ3：もし、今の参照元が0なら、参照元をpに変更
していけばよい
ACコード

メモ

逆順に処理するところまでは浮かばない

ABC411E - E [max]

解法

期待値であるから、
出た目の最高値\timesそうなる確率の総和を求めることになるが、簡単のため、
出た目の最高値\times（最高値以下の目が出る確率-その一つ下の大きさの目以下が出る確率）の総和を求めることを考える
ある大きさ以下の目が出る確率は、
その目以下の面数/6の全サイコロの総乗で計算できる
それを求めるために、目の小さい順に、どのサイコロで出るかを整理し、足し合わせていく
具体的には、(目の数,サイコロ番号)をHeapQueueに入れて順に取り出しながら、各サイコロのその目以下の面数を把握していく
目の最大値が変わるごとに全サイコロの確率の総乗を計算することは時間的にできないが、
ある目以下の面数が出る確率から次に大きい目以下の面数が出る確率は、あるサイコロの面数の前後比になることを利用すれば、
目の最大値が変化するのは高々6\times N回程度なので、計算することが可能となる
ただし、ある大きさ以下の目が出る確率というのは、大きい数しかないサイコロが混ざっていれば、0になる
つまり、最大値が全サイコロの最小値を超えてこなければ、答えの期待値には寄与しない
まだ面の数がないサイコロの個数として初期値Nを持ち、各サイコロの面数が0でなくなるタイミングで1ずつ減らして管理し、0になってから期待値に足し合わせていけばよい
ACコード

メモ

差で確率を計算する手法が浮かばなかった

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

Discussion