算数オリンピックの問題 その11
メチャメチャだけど【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、算数オリンピックについて考察していく。
グラフや幾何学の問題や、記述に関するメタ的な問題以外の今までに無い種類の問題について考察する。
04年度ファイナル問題 問題2
『図のように、縦16マス×横2004マスの長方形があり、左上のマスの中にコマが置いてあります。平太君と大介君が次のルールに従ってゲームをします。
(図は省略。説明文通り)
(ルール)
1.平太君が先手で始め、以後かわるがわるにコマを動かしていく。
2.1回の順番では、たてまたは横(斜めは不可)に何マスでもコマを動かせ、最低1マスは動かさなければならない。
3.各マスは一度しか通ったり止まったりすることができない。
4.自分の順番にコマを動かせなくなった方が負けになる。
2人とも自分が勝つために最善をつくす場合、どちらか1人の方に必ず勝てる戦略があります。必ず勝てる人は平太君、大介君のどちらか、またその戦略はどんなものか、答えなさい。』
moved_table := [~15][~2003]のリスト; ??
x_of_piece := 0;
y_of_piece := 0;
moved_table[0][0] := true;
game := {
プレイヤー1, プレイヤー2 := {
[
{
x_of_piece <= 14;
x_of_piece := x_of_piece + 1;
moved_table[x_of_piece][y_of_piece] != true;
moved_table[x_of_piece][y_of_piece] := true;
}
~.数 == ?;
,
{
x_of_piece >= 1;
x_of_piece := x_of_piece - 1;
moved_table[x_of_piece][y_of_piece] != true;
moved_table[x_of_piece][y_of_piece] := true;
}
~.数 == ?;
,
{
y_of_piece <= 2002;
y_of_piece := y_of_piece + 1;
moved_table[x_of_piece][y_of_piece] != true;
moved_table[x_of_piece][y_of_piece] := true;
}
~.数 == ?;
,
{
x_of_piece >= 1;
x_of_piece := x_of_piece - 1;
moved_table[x_of_piece][y_of_piece] != true;
moved_table[x_of_piece][y_of_piece] := true;
}
~.数 == ?;
,
相手の目的;
].1;
};
{
プレイヤー1;
プレイヤー2;
}
~;
};
別にif文では無いし、とりあえず、こう記述するのが自然なのかなと。あと、相手の目的に達したらもう終了だろう。
分からないので答えを見ると、平太くんが横方向に進めるだけ進めるが答え。そうすると最後の横1列を使い切って勝利。
05年度トライアル問題 問題8
『算数のテストに100人が参加し、第1問〜第5問の5問が出題されました。
各問題の正解者は第1問は92人、第2問は86人、第3問は61人、第4問は87人、第5問は57人でした。
このテストでは5問中3問以上正解の人を合格者としました。
合計者はもっとも少ない場合で何人ですか。』
100_people := [~99][~4]のリスト;
100_people[?][0].[?1: ?1 == true].数 == 92;
100_people[?][1].[?2: ?2 == true].数 == 86;
100_people[?][2].[?3: ?3 == true].数 == 61;
100_people[?][3].[?4: ?4 == true].数 ==87;
100_people[?][4].[?5: ?5 == true].数 == 57;
successful_examinee := 100_people[?].[?6: ?6[?].[?7: ?7 == true].数 == 3]; ??こんなんで良いんだろうか
successful_examineeを最小化するように設定;
結果におけるsuccessful_examinee;
不合格者はなるべく2問は正解させて、合格者はなるべく5問正解させる。どちらにしても結果が同じなら、なるべく多く正解分を削りたい。
まず大体当たりをつけるために、92+86+61+87+57=383を計算。
最善であれば、2問正解が100人で200。ここから5問正解が増えるたびに+3されていく。383-200=183。/3=61人。
だがしかし、5問正解させるにしても、問題5の正解者は57人だ。61-57=4人分で、4点更に+しなければならない。しかも今回は、もう61まで行っているので、2問正解を3問正解にすることしかできない。つまり、61+4=65人が答えなはずだ。正解だった。
everyとかanyとかの扱いを本当に近々研究しなければ。この記述法におけるanyとは何か。
05年度ファイナル問題 問題2
『3、5、7、11、13、17、19、23、29の9つの数字を下の9つの○へ1つずつ入れ、3つの辺上の和を等しくなるようにしたとき、最大の和と最小の和をそれぞれ求めなさい。
(図)一辺に○が4つの正三角形』
[A, B, C, D, E, F, G, H, I] := それぞれカブり無しで全部に := [3, 5, 7, 11, 13, 17, 19, 23, 29];
A + B + C + D == D + E + F + G == G + H + I + A;
記録1;
(A + B + C + D)が最大になるように設定;
結果における(A + B + C + D);
記録1~{
(A + B + C + D)が最小になるように設定;
結果における(A + B + C + D);
};
([A, B, C, D, E, F, G, H, I].+) + A + D + G、が3の倍数になる。まず3+5+7+11+13+17+19+23+29=127として、つまりA+D+Gは3の倍数。
これは答えを見たので書いてしまうと、つまりA+D+Gが最大になる場合を考えれば良い。
最善は19+23+29だが、=71。2減らす必要があるので19を17にする。しかしそれでは、それぞれを足すと40と46と52だが、残りから6と12を引いても3の倍数にならない。それでは残りの数字でイコールの辺を作ることはできない。
その次に良い場合を考えて、更に17を11にする。
えーもう面倒くさいので答えを見ると、俺はミスをしていて、127は3の倍数では無いので、A+D+Gは3で割って2あまる数である必要がある。
あとは手なり。
06年度トライアル問題 問題6
『4台の全く同じ性能の車があります。どの車もタンクいっぱいに同じ量のガソリンを入れると最大12km走行でき、また他の車に自分の車のガソリンの一部または全部を分けて移すこともできますが、ガソリンタンクが空になった車はそこで動けなくなります。
今、この4台の車をタンクいっぱいにガソリンを入れて同じ場所から同時に出発させ、途中でおたがいにうまくガソリンを補給し合いながら4台のうちの1台がなるべく長い距離を走れるようにすると、最大何km走ることができますか。』
この問題は連続的なんだよな。こういう連続的な制約についての機能が、ソルバーとかにあったはずで、それについて調べてみなければ。
今回は非連続的にやってみるが。
A := 12;
B := 12;
C := 12;
D := 12;
cars := [A, B, C, D];
result := 0;
{
for(i := 0; i < cars.数; i++){
cars[i] := cars[i] - 1;
if(cars[i] == 0){
carsからcars[i]を取り除く; ??
i := i - 1;
}
}
result := result + 1;
for(i := 0; i < cars.数; i++){
for(j := 0; j < cars.数; j++){
if(i == j){ continue;}
cars[i] := cars[i] - ?1;
cars[j] := cars[j] + ?1;
if(cars[i] == 0){
carsからcars[i]を取り除く;
i := i - 1;
break;
}
}
}
}
~cars == [];
resultが最大化するように命令;
結果におけるresult;
最後のもwhile文で書けよっていうのもあるかもしれないけど、問題さえ無ければどっちもアリということにしたい。
c言語で無く、pythonとかの、リストを使うようなのの方が良いかもしれない。とりあえず書いてみたけど、検討。でも絶対に前よりは読みやすいはず。
まあ答えは簡単で、全部のガソリンを運びながら、できるだけ車を走らせなければ良いわけだから、3km走って、他に3km分ずつ分けて、4km走って、分けて、6km走って、分けて、12km。3+4+6+12=25km、が答えだろう。
06年度トライアル問題 問題7
『サッカーのワールドカップ予選で同じ組になったA国、B国、C国、D国の4ヶ国の間で1試合ずつのリーグ戦(総当たり戦)を行ったところ、ある日までのA国、B国、C国の成績が次のようになっています。
勝ち数 | 負け数 | 引き分け数 | 得点 | 失点 | |
---|---|---|---|---|---|
A国 | 2 | 0 | 1 | 2 | 0 |
B国 | 1 | 0 | 1 | 4 | 3 |
C国 | 0 | 2 | 0 | 3 | 6 |
D国 |
この成績表のD国の空いている部分にすべて数字を入れなさい。』
teams := [~3][~4]のリスト;
for(i := 0; i < teams.数; i++){
for(j := 0; j < teams.数; j++){
if(i == j){continue;}
teams[i][3] := teams[i][3] + ?1;
teams[j][4] := teams[j][4] + ?1;
teams[j][3] := teams[j][3] + ?2;
teams[i][4] := teams[i][4] + ?2;
if(teams[i][3] == teams[j][3]){
teams[i][2] := teams[i][2] + 1;
teams[j][2] := teams[j][2] + 1;
} else if(teams[i][3] > teams[j][3]){
teams[i][0] := teams[i][0] + 1;
teams[j][1] := teams[j][1] + 1;
} else if(teams[i][3] < teams[j][3]){
teams[j][0] := teams[j][0] + 1;
teams[i][1] := teams[i][1] + 1;
}
}
}
teams[0] == [2, 0, 1, 2, 0];
teams[1] == [1, 0, 1, 4, 3];
teams[2] == [0, 2, 0, 3, 6];
結果におけるteams[3];
あー、これ、間違いだな。同じチーム同士で試合が2回行われてしまう。まあ、今回はいいか。もう夜だし。
まあでもこの問題は、難しくないんじゃないかな。勝ち数と負け数、得点と失点の差分を補いつつ、整合性が合わなかったら、それら2つセットを同時に上げていく感じで。分からないけど。