【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックの二次元配列の問題について考察していく。
『下の49のマスの1つに宝物がかくされています。下の4つのヒントを参考にしてそのマスをぬりつぶしなさい。
（図）
| 3 | 1 | 1 | 2 | 3 | 1 | 2 |
| 1 | 3 | 2 | 3 | 1 | 3 | 1 |
| 2 | 1 | 2 | 2 | 3 | 3 | 2 |
| 3 | 2 | 1 | 3 | 2 | 1 | 3 |
| 1 | 3 | 2 | 1 | 1 | 2 | 3 |
| 1 | 2 | 1 | 2 | 2 | 3 | 1 |
| 2 | 1 | 2 | 3 | 1 | 1 | 2 |
ヒント1．宝物が入っているマスから、下へ2つ進むと2
ヒント2．宝物が入っているマスから、上へ2つ進むと1
ヒント3．宝物が入っているマスから、左へ3つ進むと2
ヒント4．宝物が入っているマスから、右へ1つ進むと2』
table := [
[3, 1, 1, 2, 3, 1, 2],
[1, 3, 2, 3, 1, 3, 1],
[2, 1, 2, 2, 3, 3, 2],
[3, 2, 1, 3, 2, 1, 3],
[1, 3, 2, 1, 1, 2, 3],
[1, 2, 1, 2, 2, 3, 1],
[2, 1, 2, 3, 1, 1, 2]
];
table[x][y + 2] == 2;
table[x][y - 2] == 1;
table[x - 3][y] == 2;
table[x + 1][y] == 2;
print(x, y);
解答としては、そういう動きが可能なマスがそもそも9マスに絞られるので、9通りで検証すれば良い。
『ピーターと平ちゃんがちょっと変わった「4目ならべ」で遊んでいます。
たて6列、横6列の計36個のマスの中に、ピーターが黒石を、平ちゃんが白石を置きます。
ピーターが最初にいくつかの黒石を置き、次に平ちゃんが空いているマスの中にすきなだけ白石を置きます。ピーターの目的は、平ちゃんがどれだけ白石を置いても、平ちゃん「4目」を作らせないこと、つまり4つの白石が1列に並ばせないようにすることです。
（1）ピーターは最小で何個の黒石を置けばいいですか。
（2）（1）の置き方のうち、ピーターの置いた黒石が「4目」を作っているような置き方を考えられるだけ答えなさい。ただし、答えは1つとは限りません。また、答えの図のうち回転させたり、裏返したりして、すべての黒石の位置が重なるものは同じ答えとみなします。
（図）
| ○ | |||||
| ○ | |||||
| ○ | |||||
| ○ | |||||
table := [~5][~5];
table[?][?] := カブり無し : result1 : カブり有り := "●";
table[?][?].filter(it != "●") := カブり無しで全部に : ? : カブり有り := "○";
every(x, y){
!(table[x][y], table[x + 1][y], table[x + 2][y], table[x + 3][y] == "○");
!(table[x][y], table[x][y + 1], table[x][y + 2], table[x][y + 3] == "○");
!(table[x][y], table[x + 1][y + 1], table[x + 2][y + 2], table[x + 3][y + 3] == "○");
!(table[x][y], table[x + 1][y - 1], table[x + 2][y - 2], table[x + 3][y - 3] == "○");
}
result1を最小化するように命令;
print(result1);
or(1){
table[a][b], table[a + 1][b], table[a + 2][b], table[a + 3][b] == "●";
} or {
table[a][b], table[a][b + 1], table[a][b + 2], table[a][b + 3] == "●";
} or {
table[a][b], table[a + 1][b + 1], table[a + 2][b + 2], table[a + 3][b + 3] == "●";
} or {
table[a][b], table[a + 1][b - 1], table[a + 2][b - 2], table[a + 3][b - 3] == "●";
}
table_list := every.table;
for(table1 in table_list){
for(table2 in table_list){
if(table1 is table2){continue;}
if(table1 == table2){table_list.remove(table2);} #いらないか？
if(table1 == table2.reverse()){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2[y].reverse, range(5)))){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2[y].reverse, range(5))).reverse){table_list.remove(table2);}
table2_dash := [
list(map(lambda y: table2[y][0], range(5))),
list(map(lambda y: table2[y][1], range(5))),
list(map(lambda y: table2[y][2], range(5))),
list(map(lambda y: table2[y][3], range(5))),
list(map(lambda y: table2[y][4], range(5)))
];
if(table1 == table2_dash){table_list.remove(table2);}
if(table1 == table2_dash.reverse()){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2_dash[y].reverse, range(5)))){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2_dash[y].reverse, range(5))).reverse){table_list.remove(table2);}
}
}
print(table_list.数);
縦と横それぞれに3列目か4列目に置いて、最低10個。しかし斜めを許す隙間を中心で作らないようにと考えると、十字の11個を基本に考えれば良いのか。回転を考えると1通りの十字について考えれば良いだろう、というかつまり34行列目で作られる斜めのLを。末端の左右上下の2個が自由に動くと考えると、それぞれ3列目か4列目の2通りなので、2^8=256通り。短い方の2個、つまりLの折れ目側を動かして斜め4個が作れる場合が、長い方の4個をそれぞれ自由に動かせる場合だけあるので、2^4=16通りある。短い方と長い方のコンビネーションが、もう1セットを自由に動かせる場合だけあるので、2^4=16通り、そのもう片方でも16通り、しかし両方揃う場合が1通りあるので、16+16-1=31通り。長い方同士のコンビネーションも、内側と外側でそれぞれ16通りあるので32通り。
いや待て、結構被る場合があるな。まず全部で何通りあるかと言えば、短い方同士が16通り、短い方と長い方が16通りと16通り、長い方同士が16通りと16通り。で、被るのが、短い方同士が、独立で長い方同士の場合と被る。短い方と長い方のそれぞれが、長い方同士とそれぞれ被る。短い方と長い方で被る場合が、長い方同士と被る場合でもあって。これで全部かな？
短い方同士と長い方同士が2通り。短い方と長い方のそれぞれが、長い方同士と被る場合が4通りずつだが、そのうち1通りはお互いに被っているので、7通り。これで良いのかな、合わせて9通り。
256 - (16 + 16 + 16 + 16 + 16 - 9) = 185通り、が答えか。いや待て、L字を崩さないままひっくり返す場合があり得るから、あれ計算が合わないな。ああひっくり返す軸と対象になる場合が引かれないのか？まあいいや。
『同じ大きさの正方形のマス目がたて3列、横8列あります。これをたてに3マスか横に3マスの形に区切っていきます。全部で何通りの区切り方がありますか。ただし、回転したり裏返して重なるものはすべて同じもの（合わせて1通り）として数えます。
（図）
table := [~2][~7];
while(true){
or(1){
table[?][?1] == false; #これできて欲しいなあ
table[?][?1] := "A";
} or {
table[?1][?2], table[?1][?2 + 1], table[?1][?2 + 2] == false;
table[?1][?2], table[?1][?2 + 1], table[?1][?2 + 2] := "B";
} else {
break;
}
}
table[?][?] == true;
table_list := every.table;
for(table1 in table_list){
for(table2 in table_list){
if(table1 is table2){continue;}
if(table1 == table2){table_list.remove(table2);} #いらないか？
if(table1 == table2.reverse()){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2[y].reverse, range(3)))){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2[y].reverse, range(3))).reverse){table_list.remove(table2);}
table2_dash := [
list(map(lambda y: table2[y][0], range(3))),
list(map(lambda y: table2[y][1], range(3))),
list(map(lambda y: table2[y][2], range(3))),
list(map(lambda y: table2[y][3], range(3))),
list(map(lambda y: table2[y][4], range(3))),
list(map(lambda y: table2[y][5], range(3))),
list(map(lambda y: table2[y][6], range(3))),
list(map(lambda y: table2[y][7], range(3)))
];
if(table1 == table2_dash){table_list.remove(table2);}
if(table1 == table2_dash.reverse()){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2_dash[y].reverse, range(3)))){table_list.remove(table2);}
if(table1 == list(map(lambda y: table2_dash[y].reverse, range(3))).reverse){table_list.remove(table2);}
}
}
print(table_list.数);
これは簡単で、横を使う場合はそのまま3つ重ねる必要があるので、それをブロックとしてまとめて、1個使う場合と2個使う場合と全く使わない1通りを足す。1個が6通り、2個が6通り、使わないのが1通りなので、13通りだろう。
『図のように、16個のマスがあります。
各マスに1〜16の数字を1個ずつ書き入れた後、次の①〜④の作業をするとき、各問いに答えなさい。
①1個の数字を選んで○で囲み、その数字のたて、横にならぶ各3個の数字すべてに×をつける。
②残りの9個の数字の中から1個の数字を選んで○で囲み、その数字のたて、横にならぶ各2個の数字すべてに×をつける。
③残りの4個の数字の中から1個の数字を選んで○で囲み、その数字のたて、横にならぶ各1個の数字すべてに×をつける。
④最後に1個残った数字を○で囲み、○で囲まれた4個の数字の和を求める。
（図）
（問い1）（図1）のように数字を書き入れた場合、①〜④の作業でどのように数字を選んでも○で囲まれた4個の数字の和は必ず34になります。
その理由を説明しなさい。
（図1）
| 1 | 2 | 3 | 4 |
| 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 |
（問い2）（図1）のように、①〜④の作業の後に残った○で囲まれた4個の数字の和が必ず34になるような1〜16の数字の入れ方は、（図1）を除いて全部で何通りありますか。』
table := [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
];
0 <= A, B, C, D, E, F, G, H <= 3;
A != B != C != D;
E != F != G != H; #こんなんで良いよな
every(A, B, C, D, E, F, G, H,){ #なんか、一応書いたけど、問題文とは違うと思う
table[A][E] + table[B][F] + table[C][G] + table[D][H] == 34;
}
リセット;
table2 := [~3][~3];
table2[?][?] := カブり無し : 16 : カブり無し := 1~16;
0 <= A, B, C, D, E, F, G, H <= 3;
A != B != C != D;
E != F != G != H;
table[A][E] + table[B][F] + table[C][G] + table[D][H] == 34;
print(数 - 1);
問題1は、table[y][x]として、yが進むたびに4増えて、xが進むたびに1増えて、それが均等に選ばれるから。
問題2でそれを再現するなら、おそらくyの配置が4*3*2=24通り。yの1通り辺りで、xの配置が24通り、の4乗。24^5 - 1、が答えか？
単純に違った。xの配置は、縦の足される数がズレてはいけないから、こっちも24通りだ。24*24=576。更にxとyを入れ替えて考える場合があるから、*2=1152。
しかし、図1のような、右に行くほど一定数増えていって（縦で揃っていれば良いだけで、増え方自体が一定である必要は無いらしい）、下に行くほど一定数増えていく増え方は、まだあるらしい。
1と16の位置は決定している、なぜなら右に行くほど増えていって、下に行くほど増えていくから。
2の置き方は2通りだが、後からまたひっくり返すので、とりあえず右に配置する。3の置き方は、その右か、1の下か。
123と置く場合、更に次に4を置くと、5の配置が決まって、そのまま最後まで行ってしまう。だからその場合は1の下が4で、5と6も決まる。
1の下に3を置く場合、4が決まる。
そんな感じで考えていくと、更に2パターンあるらしい。1152 * 3 - 1 = 3455通りが答え。
『（図1）のように1辺1cmの正方形のマスに区切った、たて横が7cmと9cmの白い長方形1枚と、図2のように1辺1cmの正方形のマスに区切った、たて横が4cmと3cmの黒い長方形の紙3枚があります。
黒い紙3枚をたがいに重ねることなく、また白い紙の上からはみ出ることなく、マスの区切りの線にそってすべて白い紙の上に置きます。
黒い紙が置かれていない部分の図形の周りの長さの和が最も長くなるとき、その長さの和を求めなさい。
たとえば（図3）の場合は周りの長さの和は34cmになります。
（図1）
（図2）
（図3）
table := [~6][~8];
for(i in range(3)){
or(1){
list(map(lambda x, y: table[?1 + x][?2 + y], range(3), range(4))).every == false; #リスト外を参照するとIndexErrorが出るらしい、放置
list(map(lambda x, y: table[?1 + x][?2 + y], range(3), range(4))).every := true;
} or {
list(map(lambda x, y: table[?1 + x][?2 + y], range(4), range(3))).every == false;
list(map(lambda x, y: table[?1 + x][?2 + y], range(4), range(3))).every := true;
}
}
def to_posi_x(x, y, result1){ #迷路の左壁を辿るようなイメージ。しかし関数を4つ作るよりもっと良い方法があったような気もする
table[x][y] := "A";
result1 := result1 + 1;
if(x == start_x && y == start_y){
if(result1 == 1){ #初回の場合
if(table[x + 1][y] != false && table[x][y + 1] != false){ #一番左上端から出発するので、これはつまり1マスで終わりの場合
result1 := result1 + 3;
return result1;
}
} else { #初回では無い場合
if(table[x + 1][y] == "A" && table[x][y + 1] == "A"){ #一番普通のパターン、右からスタートして下からゴール
return result1;
} elif(table[x + 1][y] == true || table[x][y + 1] == true){ #つまりゴールが行き止まりの場合、行き止まった1辺をカウントしたい
result1 := result1 + 1;
return result1;
} #右から行って右から帰ってきて、しかしまだ下方向に行ってない場合はそのまま↓
}
}
if(table[x][y - 1] == false || table[x][y - 1] == "A"){
result1 := result1 - 1; #壁を周るように曲がる時に、1個分引く必要がある。凸型の曲がり角だとそうだが、凹型だと1足す必要がある
result1 := to_nega_y(x, y - 1, result1);
} elif(table[x + 1][y] == false || table[x + 1][y] == "A"){
result1 := to_posi_x(x + 1, y, result1);
} elif(table[x][y + 1] == false || table[x][y + 1] == "A"){
result1 := result1 + 1;
result1 := to_posi_y(x, y + 1, result1);
} else {
result1 := result1 + 2;
result1 := to_nega_x(x - 1, y, result1);
}
return result1;
}
def to_nega_x(x, y, result1){
table[x][y] := "A";
result1 := result1 + 1;
if(x == start_x && y == start_y){ #to_posi_x以外では初回の場合などあり得ないので、そのチェックは省略。余計だったな
if(table[x + 1][y] == "A" && table[x][y + 1] == "A"){ #一番普通のパターン、右からスタートして下からゴール
return result1;
} elif(table[x + 1][y] == true || table[x][y + 1] == true){ #つまりゴールが行き止まりの場合、行き止まった1辺をカウントしたい
result1 := result1 + 1;
return result1;
} #右から行って右から帰ってきて、しかしまだ下方向に行ってない場合はそのまま↓
}
if(table[x][y + 1] == false || table[x][y + 1] == "A"){
result1 := result1 - 1;
result1 := to_posi_y(x, y + 1, result1);
} elif(table[x - 1][y] == false || table[x - 1][y] == "A"){
result1 := to_nega_x(x - 1, y, result1);
} elif(table[x][y - 1] == false || table[x][y - 1] == "A"){
result1 := result1 + 1;
result1 := to_nega_y(x, y - 1, result1);
} else {
result1 := result1 + 2;
result1 := to_posi_x(x + 1, y, result1);
}
return result1;
}
def to_posi_y(x, y, result1){
table[x][y] := "A";
result1 := result1 + 1;
if(x == start_x && y == start_y){ #to_posi_x以外では初回の場合などあり得ないので、そのチェックは省略
if(table[x + 1][y] == "A" && table[x][y + 1] == "A"){ #一番普通のパターン、右からスタートして下からゴール
return result1;
} elif(table[x + 1][y] == true || table[x][y + 1] == true){ #つまりゴールが行き止まりの場合、行き止まった1辺をカウントしたい
result1 := result1 + 1;
return result1;
} #右から行って右から帰ってきて、しかしまだ下方向に行ってない場合はそのまま↓
}
if(table[x + 1][y] == false || table[x + 1][y] == "A"){
result1 := result1 - 1;
to_posi_x(x + 1, y, result1);
} elif(table[x][y + 1] == false || table[x][y + 1] == "A"){
result1 := to_posi_y(x, y + 1, result1);
} elif(table[x - 1][y] == false || table[x - 1][y] == "A"){
result1 := result1 + 1;
result1 := to_nega_x(x - 1, y, result1);
} else {
result1 := result1 + 2;
result1 := to_nega_y(x, y - 1, result1);
}
return result1;
}
def to_nega_y(x, y, result1){
table[x][y] := "A";
result1 := result1 + 1;
if(x == start_x && y == start_y){ #to_posi_x以外では初回の場合などあり得ないので、そのチェックは省略
if(table[x + 1][y] == "A" && table[x][y + 1] == "A"){ #一番普通のパターン、右からスタートして下からゴール
return result1;
} elif(table[x + 1][y] == true || table[x][y + 1] == true){ #つまりゴールが行き止まりの場合、行き止まった1辺をカウントしたい
result1 := result1 + 1;
return result1;
} #右から行って右から帰ってきて、しかしまだ下方向に行ってない場合はそのまま↓
}
if(table[x - 1][y] == false || table[x - 1][y] == "A"){
result1 := result1 - 1;
result1 := to_nega_x(x - 1, y, result1);
} elif(table[x][y - 1] == false || table[x][y - 1] == "A"){
result1 := to_nega_y(x, y - 1, result1);
} elif(table[x + 1][y] == false || table[x + 1][y] == "A"){
result1 := result1 + 1;
result1 := to_posi_x(x + 1, y, result1);
} else {
result1 := result1 + 2;
result1 := to_posi_y(x, y + 1, result1);
}
return result1;
}
delete_chain(x, y){
table[x][y] := true;
if(table[x + 1][y] == "A" || table[x + 1][y] == false){ delete_chain(x + 1, y);}
if(table[x - 1][y] == "A" || table[x - 1][y] == false){ delete_chain(x - 1, y);}
if(table[x][y + 1] == "A" || table[x][y + 1] == false){ delete_chain(x, y + 1);}
if(table[x][y - 1] == "A" || table[x][y - 1] == false){ delete_chain(x, y - 1);}
}
result1 := 0;
while(table[?][?] != true){
for(i in range(7)){
for(j in range(9)){
if(table[i][j] == false){
x, y := i, j;
break;
}
} else { #pythonに準拠。forが終わった後に実行される。breakで抜け出した場合は実行されない。しかもこのcontinueは外側のfor文に対応している。if文のelseみたいなものなんだろう。便利だ。
continue;
}
break;
}
start_x := x; #外で宣言した変数は内部でも参照できるらしい
start_y := y;
result1 := to_posi_x(x, y, result1);
delete_chain(x, y);
}
result1が最大になるように設定;
print(result1);
疲れた。流石に同じような関数を4つ作るよりも良い方法があったような気がする。
解答としては、長方形を追加した時の増え方を考えると、マックスは元々のフィールドと追加する長方形の縦と横を全部足した数値だが、被るたびに-2されていく。
縦縦縦、縦縦横、縦横横、横横横、に場合分けして考えてみるか。縦縦縦と、縦縦横は、それらの最善値がすぐ出る。残り二つがまあ面倒だな。
答えを見ると、普通に空白が細長くなるようにするで、52cm。
って良く読むと"A"を挿入する必要など無いではないか。
まあ良いや。思いの他、プログラミングの勉強になる研究だ、pythonに寄せて良かった。数学の研究は30代の中盤ぐらいまで続けようと思っている。