ABC200参加しました。

A - Century

境界となる部分の扱いが面倒ですが、$ N+99 $とすれば、上2桁がそのまま世紀になります。上二桁は100で割れば出てきます。

B - 200th ABC-200

200を付け足す部分は、$ X \times100 + 200$で可能です。

C - Ringo's Favorite Numbers 2

modの性質を知っているかどうかが肝。普通にやると、$(i, j)$を全探索することになり、$4 \times 10^{10}$で間に合いません。

ここで、整数$a,b$をMで割った余りが等しいのなら、$a-b$はMの倍数という性質を使います。
「整数$a,b$ をMで割った余りが等しい」のなら,$a = pM + r$, $b = qM + r$と表せます。このとき、$ a-b=(p - q)M $となってMの倍数です。なお、逆も成立します。

今回は$M=200$です。

まず,Aについて、すべて200で割った余りを求め、それぞれの余りがいくつあるかを数えます。

for(int i = 0 ; i < 200 ; ++i){
  r = A[i] % 200;
  P[r]++;
}

例えば、P[1] = 3なら、入力されたAの中に、余りが1になるものが3個存在します。実際にどの数が余り1になるのかは今回はどうでもいいです。

次にそれぞれの余りの中から、順序を無視して2つ抜き出して$A_i, A_j$に当てはめます。つまり

for(int i = 0 ; i < P.Length ; ++i){
  ans += (P[i]) * (P[i-1]-1) / 2; 
}

を求めればansが答えです。

なおP[i]*P[i-1]が非常に大きな数になる可能性があるので、longにキャストするなどしてください。
最悪の例だと、Aの中身が全部一つのP[i]に集まってP[i]= $2 \times 10^{5}$ になるため、
32bit整数型だとオーバーフローするかもしれません

P[1] = 3の例だと、余り1になる数が3個ある(例えば201, 401, 601)うちの中から、順序を気にせず2個抜き出して、組を作ります。つまり(201, 401), (201, 601), (401, 601)となります。組み合わせ $_{P_i} C_2$ の計算になります。

これで$A_i, A_j$が決まりました。

解説 - AtCoder Beginner Contest 200

D - Happy Birthday! 2

これも難しいです。

DPを使った解法が非公式の説明で散見されましたが、ここは鳩ノ巣原理の解法が楽そうでした。解法を見て、自分の言葉で説明してみます。

異なる2つの数列があったとき、その数列の和を200で割った余りが等しいような状態を作ります。
鳩ノ巣原理に乗っ取ると、異なる201個の数列を用意して、それらを「数列の和%200」の値でグルーピングすると、必ず一つ以上は、あるグループには数列が2つ以上存在するため、これを答えにすればいいです。ここを詳しく見ていきます。

数列の和%200でグルーピングすると、例えば以下のような感じになります。このとき、配列Groupのインデックスが、「数列の和%200」の値です。

Group[0] = 数列A,数列B
Group[1] = 数列C
Group[2] = なし
...
Group[i] = 数列X,数列Y
...
Group[199] = なし

例えば、Group[1]の例として数列{1, 200}があります。 (出力するのは数列Aのインデックスなので、実際には、各数列は数列Aのインデックスで構成されます)

鳩ノ巣原理から、どのグループにも一つ以上数列が存在している場合、最後の数列(201個目)がどこかに割り当てられるので、どこかのグループは数列が2つ存在することになります。「異なる2つの数列があったとき、その数列の和を200で割った余りが等しい」とは、まさにこの数列が2つ存在するグループ内の数列のことなので、この数列がそのまま答えになります。

実際に解くときには、まず数列201個用意するところから始めないといけません。
まず数列Aの先頭からL個抜き取り、このL個の数列から、bit全探索で適当に抜き出して201個の数列を作ります。
201個作るためには、最低でも$L \ge 8$であれば$2^{8}$個も作れるので、十分です。
また、鳩ノ巣原理的に、$L \ge 8$であれば、必ず答えが見つかることが保証されます。
逆に、数列Aの長さが8個未満なら、入力数列Aを全部使うことになりますが、201個作れないので、答えが見つからないこともありえます。

次に、L個の数から、bit全探索で抜き出す数を決めて、数列を201個作り、和でグルーピングします。

グルーピングした結果、数列が2個以上登録されている箇所を見つけ出し、そこから登録されている数列２つを選んで、答えの数列B,Cとして出力します。

解説 - AtCoder Beginner Contest 200

まとめ

mod嫌い... 鳩の巣原理は気がつけば強力ですね。

umem0chiの日記

AtCoder ABC200

A - Century

B - 200th ABC-200

C - Ringo's Favorite Numbers 2

D - Happy Birthday! 2

まとめ