AtCoder Biginner Contest 263 参加記録
コンテストページ:LINE Verda Programming Contest(AtCoder Beginner Contest 263) - AtCoder
コンテスト中AC: A〜E
E - Sugoroku 3
期待値DPが使えます。
サイコロを振ることを操作と呼ぶことにします。
マスからマスまでにかかる操作回数の期待値をとします。
マスからは、マスに行くことができます。
とおけば、それぞれのマスにはの確率で移動します。
また、マスに辿りつくと、マスからは(平均して)回の操作でマスに行けます。からに行くのに操作を1回行うので、マスからマスを経由してマスに辿りつくには回の操作が必要になります。
以上から、以下の式が成り立ちます。
さて、この式には右辺・左辺の両方にがあるので、左辺に移行します。
この式より、が求まっているとが求められます。
同じマスに戻るような場合、一見無限回の試行が必要なように思えますが、
このように式変形すると問題なく求められる場合があります。
次に、期待値を求めていきますが、マスの移動先が少なければメモ化再帰等で愚直に求めていくことができます。 しかし、今回は移動先が多いためとなってしまうので、もう少し工夫する必要があります。
前述の式を更に整理します。
したがって、
となります。 の部分を高速に求められればよく、連続した区間の和なのでFenwick Treeによりで求められます。
以上より、を初期値として、の順にを求めていくことで、
でこの問題を解くことができます。
(累積和を用いれば計算量が落ちるかもしれません)
Submission #33834218 - LINE Verda Programming Contest(AtCoder Beginner Contest 263)
AtCoder Biginner Contest 262 参加記録
コンテストへのリンク:■
コンテスト中AC:A〜D
D - I Hate Non-integer Number
数列の部分和に関する問題なので、部分和DPを考えます。
- 数列の項目までの部分和であって、和がとなるものの個数
今回は、何個選んだかも必要なので、情報を足します。
- 数列の項目までの部分和であって、部分和を構成する要素の数が個、その和がであるものの個数
今回、数列の要素数はと少ないですが、であり、和のとりうる範囲が非常に大きく、上記のDPは使えません。
ここで、選ぶ要素数を固定し、個とします。
個の要素からなる部分和の平均が整数となるためには、がの倍数である必要があります。すなわち、以下の条件を満たせばよいです。
つまり、部分和のだけわかれば、倍数となるかを判定できます。
そこで、以下のDPが考えられます。
- 数列の項目までの部分和であって、部分和を構成する要素の数が個であり、その和をとした時にであるものの個数
このようにすれば、のとりうる範囲もとなり、個に限定されます。
計算量は、DPテーブルを埋めるためにかかり、のそれぞれについて計算する必要があるので、だと思います。
実装はコンテスト後に見直ししたもの。
Submission #33697694 - AtCoder Beginner Contest 262
AtCoder Beginner Contest 261 参加記録
コンテスト中AC:A〜F
D - Flipping and Bonus
説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。
その時々の操作後のスコアを最大化するような貪欲法は使えません。
そこで、操作回数とカウンタの最大値がであり、小さいことから、DPできないか考えます。
回目の操作終了後にカウンタがの時のスコアの最大値
このDPテーブルの大きさ(状態数)はとなり十分小さいです。
次にへの遷移を考えますが、その前にカウンタで得られるスコアについて、次のようにしておきます。
カウンタがの時のスコアをとする。なお、がに含まれていない場合は、とする。
回目終了後にカウンタがの状態であって、回目にカウンタをする操作(コイントスが表)となった場合に遷移します。この時、スコアとしてとが加算されます。
カウンタが0の場合は、回目でカウンタをにする操作をした時です。回目のカウンタの状態に関わらず遷移するので、回目のスコアの最大値となります。
の時に回、の時に各回ずつの計算が必要となるため、と更新していった時、各について、回の計算が必要となります。従って、遷移にかかる計算量はです。
(の計算の際にmax値を同時に計算していけば、定数倍軽くなると予想されます。)
よって、計算量も問題なく、DPで解けることがわかりました。
Submission #33455701 - AtCoder Beginner Contest 261
E - Many Operations
ビット演算の問題は、2進数の各桁毎に考えるのが典型です。
非負整数の2進数表記の桁目をと表すことにします。
非負整数に対して操作から操作までを実行した場合を例に考えます。
操作1,2,3はそれぞれであったします。また、求めたい値をとします。
つまり、
です。
ここで、桁目のみに着目しても以下が成り立ちます。
2進数の桁はかしかありません。
そこで、
という風に予め計算しておくと、が0か1かを判定することで、でが求められます。
各桁について同様に求めることで、を構築できます。という制約があるため、高々30回の計算で済みます。
また、はから以下の様に求められます。
これは操作3に限らず、一般のについて、の値からの値を求めることができます。
実装では、2進数表記で、00...0
、11...1
から始めて、順にとビット演算していきました。
このようにすれば、実装は少しシンプルになるのかなと思います。
詳細は実装を参照ください。
Submission #33463754 - AtCoder Beginner Contest 261
F - Sorting Color Balls
隣合う要素を入れ替えてソートするのはバブルソートです。バブルソートの最小交換回数は反転数に等しいです。そこで、反転数を軸にこの問題を考えます。
まず、色がない場合を考えます。
より前にあって、より大きいものは自分より後ろに来なければいけないので、必ずと入れ替えなければいけません。
よって、その数をとすると、少なくとものコストがかかります。
これがコストの下界となります。コンテスト中は具体的な証明が思い浮かばなかったのですが、バブルソートの最小交換回数と反転数が等しいことから、実際にこれを達成できるはずと考えました。
次に、この考え方に従って、色がある場合を考えます。
より前にあって、より大きいものでも、色が等しいものは交換にかかるコストがなので、無視できそうです。
そこで、より前にあって、より大きいものであり、かつ、色が異なるものの個数をとすると、少なくとものコストがかかると予想できます。
これが色を考慮した場合のコストの下界となります。具体的な証明はコンテスト中は浮かばなかったのですが、色が異なる場合と同様の操作をして、同色の分のコストを無視すれば良いだけなので、同様にこれが達成できるだろうと考えました。
結果として、この考え方は正しかったです。
おそらくこの証明は、Web解説やyoutube解説で示されているのかなと思います。
後は反転数の計算ですが、各色に対し、自分と異なる色のみの反転数を求めるのは難しいと考えました。
そこで、全体の反転数を求めた後、各色の反転数を引くことで求めました。
全体の反転数はFenwick Treeで求めました。
各色の反転数については、全色分のFenwick Treeの領域を確保するのが難しそうだったので、色ごとにを分類した後、分割統治法で求めました。
実装はコンテスト後に修正したものです。
Submission #33567025 - AtCoder Beginner Contest 261
AtCoder Biginner Contest 260 F - Find 4-cycle
コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。
頂点集合を以下の通りとします。
は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。
に属するある頂点と、に属するある頂点であって、のいずれもの両方に辺がある
そこで、
- に属する頂点が、頂点に属する2つの頂点の両方と辺を持つ
という場合に、それを
- が頂点対を持つ
という風に表現したとき、4-cycleを探すという問題は、
- から共通の頂点対を持つ2つを見つける
という問題に言い換えられます。
そこで、以下のような解法が考えられます。
について、以下を行う。
と繋がる頂点をとする。
ここから得られる全ての頂点対について、が持っているということを記録していく。ここで、既に別のが、頂点対を持っていた場合、を答えとして出力する。
これでACしましたが、問題を解いた後に上記の部分の計算量の見積もりが誤りだったと気づきました。公式解説を見たところ、鳩の巣原理によりとなることがわかりました。
これは、という組は高々個しかないので、頂点対を調べていくと、高々回で既に一度調べた頂点対が現れる、ということです。
細かい実装の話に移りますが、C++で頂点対をpair
として、map
に記録する方法だとTLEしました。
二次元配列に記録していく方法だと、ACできました。配列として持てる場合は、map
は使用しない方が良さそうです。
AtCoder Biginner Contest 260 参加記録
コンテスト中AC:A〜D
B - Better Students Are Needed!
配列を用意し、各要素は以下のようにします。
この配列は例えば、C++ならvector<pair< long long, long long >>
を使用します。
について、各要素の1つ目を第一キーに、2つ目を第二キーとして降順ソートすると、
得点の大きいものが前に来て、同じ得点ならの小さいものが前に来ます。
このように、第一キーと第二キーで昇順・降順が異なるようにソートしたい場合、一方を負にしておけば、ソート1回でこの並び方を実現できます。
後は、同じ値を2回取らないように配列に記録するなどしながら、問題文の通り、
- の前から個
- の前から個
- の前から個
を合格にしていけば良いです。
計算量はソートがボトルネックとなって、だと思います。
Submission #33302936 - AtCoder Beginner Contest 260
C - Changing Jewels
レベルの赤い宝石を個、青い宝石を個持っていたとします。
ここで、次の様に操作します。
- レベルの赤い宝石個から、レベルの赤い宝石個と、レベルの青い宝石を個得る。
- レベルの青い宝石個から、レベルの赤い宝石個と、レベルの青い宝石を個得る。
この一連の操作を1回の操作と考えると、操作1回でレベルの宝石からレベルの宝石を得ます。この操作を回すれば、レベルの宝石は全てレベルになります。
実装では、前述した2つの変数のみを持っていればよいです。操作一回での具体的な更新方法を示します。
コンテスト中は再帰で実装しましたが、普通のループで問題ありません。
テキストの公式解説のDPに近い感じですが、ボトムアップかトップダウンかという点が違うかなと思います。
再帰
Submission #33311975 - AtCoder Beginner Contest 260
ループ
Submission #33347207 - AtCoder Beginner Contest 260
D - Draw Your Cards
まず、以下が高速に実現可能なデータ構造が必要です。
- 以上で最小の整数を得る
- を削除する
- を挿入する
これは順序付き集合で実現できます。(C++なら順序付き集合set
)
次に、以下を実現する必要があります。ここで、表向きで重ねられたカードを山と呼ぶことにします。
- とそれ以上で最小の整数を同じ山にする
- が属する山にあるカードの枚数を取得する
- ターン目にが属する山のカード枚数がとなった時に、山に属するカード全てにを記録する
- が属する山が何ターン目に枚となったかを取得する
これはUnion-Findにより実現できます。
AtCoder Libraryのdsu< long long > d(N)
の使用例を示しておきます。なお、カードに書かれた整数は全て-1して、にしておくことにします。
また、連想配列を用意し、が属する山が何ターン目で枚となったかをに記録することとします(普通の配列でも可)。
d.merge(X,Y)
d.size(X)
if (d.size(X)==K) m[d.leader(X)] = i
m[d.leader(X)]
ポイントとしては、同じ山の全てにターン数を記録するのではなく、Union-Findにおける同一グループの根にだけターン数を記録します。
各整数から根を辿ることで、自分が属する山が何ターン目に枚となったかわかります。
計算量はset
の各種操作がで、Union-Findの各種操作がなので、かなと思います。
AtCodet Beginner Contest 259 参加記録
コンテスト中AC:A〜D
B - Counterclockwise Rotation
ベクトルの反時計回りの回転行列は以下の通りです。
よって、求めたい座標をとすれば、
となります。
但し、C++では角度はラジアンにしないといけないので、として、の代わりにを渡します。
実装は、ようやくベクトルの回転をライブラリ化したので、それを載せておきます。
Submission #33246511 - AtCoder Beginner Contest 259
D - Circumferences
円及びが交点を持つなら、点は間を移動できます。
このように点が行き来できるような円の関係はUnion-Findで管理できます。
Union-Findにおいて、円が同グループとなる条件は、円が交点を持つことです。
この条件ですが、Web検索して以下を見つけました。
というわけで、円の全組を全探索し、以下の条件を満たし、交点を持たない場合以外にはグループ化します。
とした時、
誤差が怖いので、全て2乗で考えました。
半径の大小関係が規定されていたので、念のための場合に判定することにしました(おそらく2乗するので必要ないです)。
グループ化した後は、点を通る円と、点を通る円がグループであるかを全探索し、1つでも同グループがあればYes、1つもなければNoとなります。
この全探索の前準備として、点を通る円を配列に記録します。
点を通る円も同様に配列に記録します。
点が円上にあるかは、に代入して、を満たせば良いです。
構造体Loop
初めに
独自で実装している構造体Loopについて書いておきます(C++です)。
AtCoderでこの構造体を使用して解ける問題が何度か出題されています。
一応、いくつかの問題でACは取れていますが、素人の実装なので、誤りがある場合があります。ご了承ください。
概要
個の元を持つ集合とその写像が以下の条件を満たすとします。
である初期値が与えられ、ここから写像を求めることを繰り返すような処理についての以下のクエリを、の前処理をしておくことで、それぞれで答えられます。
基本的にはを想定しています。
集合は構造体内では定義されていません。写像を構造体内に記述し、写像を求める中で得られた値のみを配列V
に記録していきます。
コンストラクタ
Loop<T, mapping> lp
- 写像
mapping
を定義する必要があります。
T mapping(T x) { /* xが与えられた時のf(x)の内容を書く */ }
制約
型
T
は、unordered_map
で同一かどうかの判定ができればよい集合のサイズは以下くらい(そうでないと、多くの問題で
TLE
になる可能性が高い)
build
void lp.build(T t)
クエリに答えるための前計算です。
後述するget
やcount
の呼び出し前に実行する必要があります。
初期値t
から写像を求めることを繰り返し、写像として得られた値が順番に配列V
に記録されます。同じ値に2回なった時点で処理が終了します。
計算量
get
T lp.get(long long k)
初期値t
からk
回写像を求めた後の値を返します。
計算量
count
vector<long long> lp.count(long long k)
初期値t
からk
回写像を求める時、V
の各要素から何回写像を求めたかをカウントします。
計算量
実装
表示
template<class T, T (*mapping)(T)>
struct Loop {
long long s, // ループのスタート
e, // ループの最後+1 (初めて重複した値が出現した場所)
l; // ループの長さ
vector<T> V; //非ループ部とループ部を記録
unordered_map<T,long long> mp; //値が2回現れたかを調べる
void build(T t) {
while (1) {
if (mp.count(t)) {
s = mp[t];
e = (long long) V.size();
l = e - s;
break;
}
mp[t] = (long long) V.size();
V.emplace_back(t);
t = mapping(t);
}
}
/*
build呼び出し後に使用する
写像をk回求めた時のt'を返す
*/
T get(long long k) {
if (k < s) return V[k];
k = (k - s) % l;
return V[s + k];
}
/*
build呼び出し後に使用する
k回まで写像を求めた時に各値に何回なったかをカウントする
*/
vector<long long> count(long long k) {
int size = (int) V.size();
vector<long long> res(size, 0);
for (int i = 0; i < min(s,k); i++) res[i] = 1; //非ループ部
k -= s;
if (k <= 0) return res;
long long q = k / l, r = k % l;
for (int i = s; i < e; i++) res[i] = q;
for (int i = s; i < s + r; i++) res[i]++;
return res;
}
};
アルゴリズム
前処理について
という条件を満たす場合、写像を求めることを繰り返すと、同じ値が2回出た時点で以後ループします。
同じ値となったものをとおきます。
について、
- 1回目に出現した位置を
- 2回目に出現した位置を
- 右半開区間に含まれる元の数を
とします。
また、が2回出現する直前までに出現した値を出現順で並べたものを、
とします。
写像を求めることを繰り返しても、となるのは高々1回です。この部分を非ループ部と呼ぶことにします。
非ループ部のサイズは、です。
の部分は、この後写像を求め続けるととなるためループします。これをループ部と呼ぶことにします。
ループ部のサイズは、です。
前処理にかかる計算量ですが、鳩の巣原理から高々回写像を求めると同じ値になります。このため、です。
getについて
回写像を求めた後の値が、非ループ部かループ部によって場合分けします。
非ループの場合
が成り立つ場合、最終的に非ループ部の値となり、それはです。ループ部の場合
回移動すると、となります。残り、回の移動後にループ部のどの値になるかが分かればよいです。
これは以下の問題と同じです。
- 数列を時計回りに並べ、時計回りに1つずつ進むことを考える。から回進むとどの元に到達するか。
この問題のようにまで進むとに戻る場合、をとればどこに行くかわかります。
すると、はからのオフセットとなるので、となります。
計算量はです。
countについて
非ループ部からは、1回しか写像を求めることはありません。そのため、の場合、を満たす番目が+1ずつされます。
の場合を考えます。
非ループ部は全て1となります。
ループ部について、写像を求める残り回数は、となります。
となるを求めます。、です。
これは、ループ部を周して、残り回写像を求めることに対応します。
よって、ループ部については、全て加算され、更にを満たす番目に+1されます。
以上から、の各元について、一回の計算で何回写像が求められたかがわかるので、です。
AtCoderでの過去問でLoopを使える問題
ネタバレ注意