算数オリンピックの問題 その8
メチャメチャだけど【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
01年度トライアル問題 問題6
『10種類の玉がそれぞれ100個ずつ1つの袋に入っています。この袋の中から何個かの玉を取り出し、その取り出した玉の中に、必ず3種類の同一の玉が10個以上入っているようにするためには、最小で何個取り出せばよいですか。』
bag := 追加で100 := A;
bag := 追加で100 := B;
bag := 追加で100 := C;
bag := 追加で100 := D;
bag := 追加で100 := E;
bag := 追加で100 := F;
bag := 追加で100 := G;
bag := 追加で100 := H;
bag := 追加で100 := I;
bag := 追加で100 := J;
outside := 移動でN := bag;
あらゆる可能性~{
outside.10.=.種類.数 <= 3; ?? こんなので良いだろうか。「.」はjavascriptと同じで、その次の関数あるいは制約に渡すイメージだ。つまりoutsideにおけるいろんな10個を出して、それらが全てイコールになる制約に渡して、それらから同じ内容のものを削って種類にして、最後に通り数にするというイメージだ。計算量的に滅茶苦茶だが、まあこれはそれを縮めるためにその前に書かれるものだから仕方ない。しかし何とかイコールが10個という風にした方が良いかもしれない。
};
Nを最小化するように命令;
結果におけるN;
答えとしてはおそらく、こういう問題は昔もあったけど、必ずしも入らないように最大化した後に、+1する感じではないか。
具体的には、2種類をマックスまでと、残りを9個まで、の個数+1ではないか。200+8*9+1=273。
必ずっていうのは、含まない場合が無いってことだから、その否定のために、含まない最大+1ということなのかな?
01年度トライアル問題 問題10
『百の位が同じ、異なる3けたの整数が4個あり、4個の整数の和は、これら4個のうちの3個の整数でそれぞれ割り切れます。割り切れない1個の整数を求めなさい。』
number_list := [N*100 + A, N*100 + B, N*100 + C, N*100 + D];
number_list.+ == (? * number_list[0], ? * number_list[1], ? * number_list[2], ? * number_list[3]).3; ??やや違うか。3つ選んだのと同じでは無く、同じが3回
answer := (? * number_list[0], ? * number_list[1], ? * number_list[2], ? * number_list[3]).(?1: number_list.+ != ?1 * ?);
結果におけるanswer;
これはそういえば答えを見たんだけど(しかし以下結果間違い)、確か100の位が固定されているので、割り切ると言ってもそんなに選択肢が無かったはず。例えば100、199、198、197としても、694。?〜6。100、101、102、103としたら、406。4~6。
200だと1094で?~5、更に806で4~5になってしまうので、つまり100の位は1。
足して出来上がる数は、4と5と6の公倍数である必要がある。つまり60の公倍数である必要がある。406~694で考えると、420、480、540、600、660。
4の公倍数だと100から4刻み、5だと100から5刻み、6だと102から6刻み。最小で考えて420-104-100-102=114では駄目なんだろうか。
本当の答えを見ると、まず実際には100も200も3で割り切る場合があり得る。3と4と5でも公倍数は60。
100の位が2の場合、5で割ると最低200*5以上である必要があり、また3で割った時に299*3以下である必要もある。これは矛盾なので100の位は2では無い。
100の位が1の場合、割る数は100~199までなので、最大の商は最小の商の2倍未満。よって、3と4と5か、4と5と6。
3個の商が3と4と5の時、最低でも100*5以上で、最高でも3*199以下で、60の倍数。540。540 - 540/3 - 540/4 - 540/5 = 117。これは条件を満たす。
3個の商が4と5と6の時、最低でも100*6以上で、最高でも4*199以下で、60の倍数。600、660、720、780。しかし最低の600でも、600 - 600/4 - 600/5 - 600/6 = 230。100の位が2だし、これ以降はもっと大きくなっていく。
よって答えは117。まあ普通に制約から答えを出しただけの問題かと思う。
01年度ファイナル問題 問題1
『1から30までの数字を書いた30枚のカードが上から数字の小さい順に1つの山になっています。
これらを次のルールに従ってカードを切る操作をくり返していきます。
(ルール1)カードを上半分の15枚(これをAとします)と下半分の15枚(これをBとします)の2つの山にわけます。
(ルール2)Bの1番上のカードをとり出し、テーブルの上に置きます。この上にAの1番上のカード、Bの上から2番目のカード、Aの上から2番目のカード…Bの1番下のカード、Aの一番下のカードを順に重ねて、1つの山にします。
(ルール1)、(ルール2)両方に従ってカードを移動させたときに「操作を1回終了した」とするとき、9回目の操作が終了したとき、山の一番上にあるカードの数を求めなさい。』
card := [1~30];
{
cardA := card[15~29]; ※リストなので0から始まる。かつ、重ねて行って、後ろ側が毎回Aなので。
cardB := card[0~14];
card := ;
{
card := 移動で追加 := cardB.末尾;
card := 移動で追加 := cardA.末尾;
}
~cardA == ;
}
~.数 == 9;
結果におけるcard[29];
結果から逆算すれば一つだけに着目することができる。一番上は、一つ前のAの一番下。Aの一番下は、更に一つ前のAの真ん中。Aの真ん中(つまり15の内の8)は、更に一つ前のBの真ん中と4枚、つまり12、って面倒くさいな。
どうも分からないので答えを見ると、3回までの動きを表にすると(本当は2回で良い)、1回目を基準にして1番上は、次のでは15番目に来ていて、また(本当は2回目だが)1回目を基準に15番目を見ると、その次には8番目に来ていると分かる。
つまり2回分の表さえ作ってしまえば、毎回その位置にあるものが次回にどこに行くか分かるので、9回分書き出さなくても答えが分かる。
アルゴリズムでありそうな計算量の削り方だと思ったが、毎回同じ変化の仕方だから、こういうことができるのかもしれない。分からないけど。
01年度ファイナル問題 問題3
『1とA、B、Cの4個の整数があり、A + B + C = 2001です。
また1 < A < B < Cです。
これら4個の整数の2個ずつの和は合計6個ありますが、この6個の数を大きい順に並べると、となりあう数の差はすべて同じになりました。
A、B、Cはそれぞれいくつですか。』
A + B + C == 2001;
1 < A < B < C;
integer_list := [1, A, B, C];
add_list := every.integer_list.2.+; ??理論上あり得る全て、というのをeveryとかanyとかで捉えられないか、とりあえず
add_list := add_list.小さい方から整列;
every~{
add_list[?1] + X == add_list[?1 + 1];
};
結果における(A, B, C);
これは答えを見たんだった。
1+Aが最小、B+Cが最大。また、1+B < A+B < A+C。1+Cは、A+Bとどちらが大きいか分からない。
1+A < 1+B < (A+B or 1+C) < A+C < B+C。つまりAとBの差は(俺の記述における)X。
A+Bの方が小さい場合、1とAの差がX。つまりAはX+1で、Bは2*X+1で、A+Bは3X+2。Cは4X+1ということになる。1にもAにもBにもCにも1があるので、少しずつXが増えていって辻褄は合う。
1+Cの方が小さい場合、BとCの差がX。A < B < CでXずつ大きくなっていく。1+C+X = A+B、1+2*X+A+X = A+X+A、1+2*X = A。この値でも辻褄が合ってしまう。
俺の答えでは、A=X+1、B=2*X+1、C=4*X+1。あるいは、A=2*X+1、B=3*X+1、C=4*X+1。
えーっと、忘れていたけど、A+B+C=2001なんだった。どうせどちらにしても3引くとして、7*X=1998か、9*X=1998。1998は9の倍数なので、だから後者の、A=2*X+1、B=3*X+1、C=4*X+1。