ABC200 D 解答
D - Happy Birthday! 2（1217）
問題
問題文
N 個の正整数からなる数列 A = ( A1, A2, … , AN )が与えられます。 以下の条件を全て満たす 2 つの数列 B = ( B1, B2, … , Bx ), C = ( C1, C2, … , Cy )が存在するか判定し、存在する場合はひとつ出力してください。
・1 ≤ x, y ≤ N
・1 ≤ B1 < B2 < ⋯ < Bx ≤ N
・1 ≤ C1 < C2 < ⋯ < Cy ≤ N
・B と C は、異なる数列である。
→x ≠ y のとき、または、ある整数 i ( 1 ≤ i ≤ min(x , y )) が存在して Bi ≠ Ciであるとき、B と C は異なるものとする。
・A_B1 + A_B2 + ⋯ + A_Bx を 200 で割った余りと A_C1 + A_C2 + ⋯ + A_Cy を200で割った余りが等しい。
制約
入力はすべて整数
2 ≤ N ≤ 200
1 ≤ Ai ≤ 10^9
考察
突然ですがまずは本問題の制約に注目します。
この問題では
2 ≤ N ≤ 200
という制約が与えられています。もしこの200という数字がとても小さかったら簡単に解けます。例えば 3 としましょう。
数列の全ての要素を
「選択する」「選択しない」
の2つに分ければすべての組み合わせを網羅できます。
例）
1,2,3
何も選ばない
1
2
3
1, 2
2, 3
1, 3
1, 2, 3
こんな感じで2^3 = 8通りの組み合わせがあります。このくらいでしたら、全ての数列を列挙して全部の余りを試すことができますね。
果たしてこの数字はいくつまで探索が可能なのでしょうか。
作られる数列の数は 2 ^ n ですので、だいたい 2^25 ≃3.0*10^7ぐらいが限度ですかね。このくらいでしたら全部のパターンが試せそうです。ですが、もう一度制約を見てみると
n ≦ 200
です。2^200はだいぶ大きな数になりますね。さすがに間に合わないです。
しかし、本問題の性質を考えると、全部探索する手法でも十分時間内に解くことが可能です。
そのキーワードとなるのが
鳩ノ巣原理
です。ディリクレの箱入れ原理と呼ばれることもありますね。この原理を少しだけ説明します。
この原理は名前の通り鳩に関するお話です。
あるところに鳩が4匹いました。ところで、この鳩たちの家は3つしかありません。となると、少なくとも１つの家には鳩が2匹以上泊まることになりますね。
エピソードとしてはこれだけです。言われてみればそうなのですが、すっと呑み込めない方もいるかもしれません。
もうちょっと身近な例にしましょう。
あなたは洗濯物を畳んでいます。衣類の種類は上着、ズボン、下着、靴下の4種類です。しかし、あなたのタンスには引き出しが３つしかありません。とすると、少なくとも1つの引き出しには2種類以上の衣類がはいります。
こんな感じです。ここで非常に大切なのは
すべての巣（引き出し）が埋まっているとは限らない
どの鳩が一緒の巣に入るかわからない
ということです。一番目の巣に鳩が４匹住んでいるかもしれません。一番下の引き出しに４種類の衣類が詰め込まれているかもしれません。空の場所があってもいいんです。一緒になっているのは、上着とズボンかもしれませんし、下着と靴下かもしれません。詳しくはわからないのですが、とにかく引き出しのうち少なくとも１つは2種類以上の衣類が入っているのです。
さて、問題に戻ります。本問題では200で割った余りの等しい組み合わせを求めます。等しいということで、その余りが2通りで表せればよいということになります。
これって、鳩ノ巣原理に似ていると思いませんか。200で割った余りは0~199の200通りです。鳩の巣が200個あるのと同じです。ということは、鳩が201匹いれば少なくとも一つの巣には鳩が2匹以上いることになります。繰り返しになりますが、鳩が一匹もいない巣があっても大丈夫です。
ですので、数列を201通り見てあげれば ”必ず” どれかの余りは2回以上出現します。数列を201通り以上構成するためには 2^8 = 256 の 長さ8以上の数列が条件となります。長さが 8 以上あれば必ず本問題の条件は達成できますので、どんなに N が大きくても探索を打ち切ることができます。
したがって、本問題は
構築可能な数列を全探索する
という、シンプルな手法で解くことが可能です。ただし、この手法でできるのは「鳩ノ巣原理により201通り調べれば十分」という前提があることを忘れないようにしましょう。
探索の方法はいろいろとあります。bit全探索でも良いのですが、今回はDFSにて構築してみました。再帰関数の練習にどうでしょうか。
さて実装です。
実装
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<n;++i) #define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const int mod = 200;
vector<int> a;
//各余りにおける一つ目の数列
vector<vector<int>> Ans(200);
//重複した余りの数列
vector<int> ans;
//重複した余り
int R = -1;
int n;
void dfs(vector<int> v, int rem, int pos)
{
vector<int> tmp = v;
tmp.emplace_back(pos + 1);
//次の要素を入れたときの余り
int now = (rem + a[pos]) % mod;
//もしその余りに1つ目の数列が入っていない場合
if (Ans[now].size() == 0)
{
for (auto t : tmp) Ans[now].emplace_back(t);
}
//既にその余りの数列が存在していたらループを抜ける
else
{
//2つ目の配列をansにいれる
ans = tmp;
R = now;
return;
}
//全ての要素を見終わった場合も終わる
if (pos + 1 == n) return;
//次の値を入れない場合
dfs(v, rem, pos + 1);
//次の値を入れる場合
dfs(tmp, now, pos + 1);
return;
}
int main()
{
cin >> n;
a.resize(n);
rep(i, n) cin >> a[i];
//先に余りを計算しておく
rep(i, n) a[i] %= mod;
vector<int> v;
//dfsを実行する
dfs(v, 0, 0);
//2つ目の配列が空だったらNOを出力
if (ans.size() == 0)
{
cout << "No" << endl;
}
//2つ目の配列が入っていたら
else
{
cout << "Yes" << endl;
cout << Ans[R].size() << " ";
for (auto ai : Ans[R]) cout << ai << " ";
cout << endl;
cout << ans.size() << " ";
for (auto ai : ans) cout << ai << " ";
cout << endl;
}
return 0;
}あとがき
鳩ノ巣原理の問題でした。
私がこの原理を初めて知ったのは「浜村渚の計算ノート」という小説でした。なんか不思議な本でして、数学が軽視されている世界で数学の地位向上を目指す人たちの悪事を数学が得意な中学生が解決するというお話です。
その中で「ぽっぽ・ザ・ディリクレ」という悪い奴が登場します。主人公が鳩ノ巣原理を綺麗に証明して解決するのですが、これがなかなか面白いです。この本では
「千葉市美浜区に住んでいる人の中には、同じ本数の髪の毛が生えている人同士が確実にいる」
という例を挙げています。どうやら、渚ちゃんが住んでいる美浜区の人口は14万人らしく、また日本人の平均的な髪の毛は約10万本らしいのです。ということは、14万匹の鳩に対して１0万の巣があるという状況です。これなら2匹以上入らなきゃいけない巣が確実に出てきます。
本書でも挙げられていますが、大切なのは
「誰と誰が同じ本数か」
「何本で同じなのか」
「自分と誰かが同じ本数か」
ていうのはまったくわからなく
「美浜区の誰かと美浜区の誰かが同じ髪の毛の本数なのは確実」
ということしかわからないのです。
とってもお勉強になる
「浜村渚の計算ノート ５さつめ 鳴くよウグイス、平面上」
をぜひ手に取ってみてはどうでしょうか。鳩ノ巣原理の他にも「魔法陣」「回転体」「パップス・ギュルダンの定理」などのお勉強ができます。
以下リンクから購入しても私にお金は入りませんので、安心してお買い求めください。
この記事が気に入ったらサポートをしてみませんか？