【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックの二次元配列の問題について考察していく。
『下の図で、スタートからゴールまでサイコロを転がしていきます。スタートの位置では1の目を上にして、そのあとは一度も1の目が上にならないようにゴールする転がし方を解答欄に点線にそってかきいれなさい。
ただし、同じ所を2度通ったり、遠まわりをしてはいけません。また、1マスはサイコロ1つ分の大きさです。
（図）
| スタート | ||||
| ゴール |
board_X := 0; #今回からpythonのコメントアウトを採用することにした。
board_Y := 0;
dice1 := [1, 2, 6, 5].循環リストに;
dice2 := [1, 3, 6, 4].循環リストに;
dice3 := [2, 3, 5, 4].循環リストに;
dice_direction := 0;
result := [];
or(1){
board_X := board_X + 1;
current_board := board_X; #pythonにおいては値渡しで無く参照渡しらしいんで、それに準拠
result[0] := "X";
} or {
board_Y := board_Y + 1;
current_board := board_Y;
result[0] := "Y";
}
or(1){
current_dice := dice1;
dice_direction := dice_direction + 1;
} or {
current_dice := dice2;
dice_direction := dice_direction + 1;
}
i := 1;
while(board_X < 5 || board_Y < 5){ #都合が悪い所はpythonに準拠しない
or(1){
current_board < 5;
current_board := current_board + 1;
dice_direction := dice_direction + 1;
current_dice[dice_direction] != 1;
} or {
(board_X, board_Y).filter(it != current_board) < 5;
current_board := (board_X, board_Y).filter(it != current_board);
current_board := current_board + 1;
next_dice := (dice1, dice2, dice3).filter(it ∋ current_dice[dice_direction]).filter(it != current_dice); #別の問題で要素名を取得したいなら、「current_dice[dice_direction]」はマズいのではないか
dice_direction := next_dice.index(current_dice[dice_direction]);
current_dice := next_dice;
dice_direction := dice_direction + 1;
current_dice[dice_direction] != 1;
}
if(current_board == board_X){ #これって、参照で==なのか、値で==なのか。いや間違っている気がするな
result[i] := "X";
} else {
result[i] := "Y";
}
i := i + 1;
}
print(result); #resultがいっぱい表示されないか。また、しかし「every.1.result」でも同じようにいっぱい表示されるのでは
解答も何も、生成して駄目だったら他の方法を試す、で良いんじゃないか。
『次のようなルールの遊びをします。
［ルール］
さて、この遊びがもっともはやく終了したとき（つかったピースの個数が最小のとき）盤上には何個のピースがおかれていますか。
（図1）
（図2） ※項目名の色付きで対応
board := [~5][~5];
count := 0;
while(true){
or(1){
board[?1][?2] != true;
board[?1 + 1][?2] != true;
board[?1][?2 + 1] != true;
board[?1][?2] := true;
board[?1 + 1][?2] := true;
board[?1][?2 + 1] := true;
count := count + 1;
} or {
board[?1][?2] != true;
board[?1 + 1][?2] != true;
board[?1][?2 - 1] != true;
board[?1][?2] := true;
board[?1 + 1][?2] := true;
board[?1][?2 - 1] := true;
count := count + 1;
} or {
board[?1][?2] != true;
board[?1 - 1][?2] != true;
board[?1][?2 + 1] != true;
board[?1][?2] := true;
board[?1 - 1][?2] := true;
board[?1][?2 + 1] := true;
count := count + 1;
} or {
board[?1][?2] != true;
board[?1 - 1][?2] != true;
board[?1][?2 - 1] != true;
board[?1][?2] := true;
board[?1 - 1][?2] := true;
board[?1][?2 - 1] := true;
count := count + 1;
} else {
break; #いや、流石にどうだろう
}
}
countを最小化するように命令;
print(count);
可能な限り実行する、というのをどうすれば良かったのか。まあelseの後にまたorを続けて、orが駄目だったら別のorというのも便利なのかもしれないけど。
よく分からないけど、try文で、実行できなかったらbreakみたいなのか。分からん。
解き方としては、制約が大きい端っこから、まずピッタリくっつけるように置いて、それよりは隅を囲うように置くのが上位互換で、とりあえずそれで四隅。次に制約が大きい辺にくっつけるように置いて、それよりはくっつけないように置いたほうが上位互換なので、四辺でそうする。
真ん中の段の左右のピースの出っ張りを内側に持ってくると、真ん中を省くことができるし、左右の辺を置かなくて済むという意味では上位互換、では無いんだが上位互換的なんじゃないか。またそうなると、上の段でも同じことをやると真ん中を省けるし、下の段でも同じで、不完全な推論だとは思うが、俺の考えでは6個なんじゃないかと。
四隅は他の置き方をするよりは2マスで邪魔をしたいし、その制約プラス1では達成され無さそうなので、6個なのではないかと。
『同じ大きさの小正方形をたて3個横5個の計15個を重なりもすき間もなく並べて（図1）のような長方形を作りました。この長方形を小正方形5個ずつの「ひとつながり」3つに、しかもその3つともが異なる形になるように切り分けたいと思います。
（図1）
この場合、「ひとつながり」とは小正方形の少なくとも1辺を共有しているものとし、たとえば（図2）の○の図は「ひとつながり」ですが、頂点だけで接している×の図は「ひとつながり」とはいえません。
（図2）
○
また、「3つともが異なる形になるように切り分ける」とは、（図3）の○の図のような場合のことで、（図3）の×の図のような場合は当てはまりません。
（図3）
○
| 1 | 1 | 1 | 2 | 2 |
| 1 | 2 | 2 | 2 | 3 |
| 1 | 3 | 3 | 3 | 3 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 2 | 2 | 2 | 3 |
| 2 | 3 | 3 | 3 | 3 |
（図3）の○の図以外で、「3つともが異なる形になるように切り取り線を実線を用いて、解答用紙の図にあるだけ書き入れなさい。
ただし、裏返したり、回転させると重なるものはすべて同じものとします。解答用紙のすべての図を使うとは限りません。』
table := [~4][~2];
5pieces_chain(x, y, count, alphabet){
if(count >= 5){ break;}
count := count + 1;
table[x][y] := alphabet;
or(1){
or(?){
table[x + 1][y] == false;
5pieces_chain(x + 1, y, count, alphabet);
} or {
table[x - 1][y] == false;
5pieces_chain(x - 1, y, count, alphabet);
} or {
table[x][y + 1] == false;
5pieces_chain(x, y + 1, count, alphabet);
} or {
table[x][y - 1] == false;
5pieces_chain(x, y - 1, count, alphabet);
} #そう記述せざるを得ないわけだが、しかし上から順番に実行してくれないとカウントが困る
} or {}
}
count := 0;
5pieces_chain(0, 0, count, "A");
count := 0;
for(i in range(5)){
for(j in range(3)){
if(count >= 5){ break;}
if(table[i][j] == true){ continue;}
5pieces_chain(i, j, count, "B");
}
}
count == 5;
count := 0;
for(i in range(5)){
for(j in range(3)){
if(count >= 5){ break;}
if(table[i][j] == true){ continue;}
5pieces_chain(i, j, count, "C");
}
}
count == 5;
table[?][?] ∌ false; #何か違和感がある。というのも、今までこう書いたら全ての?に当てはまる値をeveryで参照していたが、機能の説明ではそう書かなかった
A_position_list := [ ];
for(i in range(5)){
for(j in range(3)){
if(table[i][j] == "A"){ A_position_list.append([i, j]) }
}
}
for(i in range(1, 5)){
A_position_list[i][0] := A_position_list[i][0] - A_position_list[0][0];
A_position_list[i][1] := A_position_list[i][1] - A_position_list[0][1];
}
A_position_list[0][0] := 0;
A_position_list[0][1] := 0;
B_position_list := [ ];
for(i in range(5)){
for(j in range(3)){
if(table[i][j] == "B"){ B_position_list.append([i, j]) }
}
}
for(i in range(1, 5)){
B_position_list[i][0] := B_position_list[i][0] - B_position_list[0][0];
B_position_list[i][1] := B_position_list[i][1] - B_position_list[0][1];
}
B_position_list[0][0] := 0;
B_position_list[0][1] := 0;
C_position_list := [ ];
for(i in range(5)){
for(j in range(3)){
if(table[i][j] == "C"){ C_position_list.append([i, j]) }
}
}
for(i in range(1, 5)){
C_position_list[i][0] := C_position_list[i][0] - C_position_list[0][0];
C_position_list[i][1] := C_position_list[i][1] - C_position_list[0][1];
}
C_position_list[0][0] := 0;
C_position_list[0][1] := 0;
not_match_check(list1, list2){
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?1 + list2[0][0], ?2 + list2[0][1]], [?1 + list2[1][0], ?2 + list2[1][1]], [?1 + list2[2][0], ?2 + list2[2][1]], [?1 + list2[3][0], ?2 + list2[3][1]], [?1 + list2[4][0], ?2 + list2[4][1]]); #もっと良い書き方がないか、切実に
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?3 - list2[0][0], ?4 - list2[0][1]], [?3 - list2[1][0], ?4 - list2[1][1]], [?3 - list2[2][0], ?4 - list2[2][1]], [?3 - list2[3][0], ?4 - list2[3][1]], [?3 - list2[4][0], ?4 - list2[4][1]]); #座標を反転させた場合。以下考察の末に
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?5 - list2[0][1], ?6 + list2[0][0]], [?5 - list2[1][1], ?6 + list2[1][0]], [?5 - list2[2][1], ?6 + list2[2][0]], [?5 - list2[3][1], ?6 + list2[3][0]], [?5 - list2[4][1], ?6 + list2[4][0]]);
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?7 + list2[0][1], ?8 - list2[0][0]], [?7 + list2[1][1], ?8 - list2[1][0]], [?7 + list2[2][1], ?8 - list2[2][0]], [?7 + list2[3][1], ?8 - list2[3][0]], [?7 + list2[4][1], ?8 - list2[4][0]]); #あと、一つだけと違えば良いという場合との区別はどう付ければよいのだろうか
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?9 + list2[0][1], ?10 + list2[0][0]], [?9 + list2[1][1], ?10 + list2[1][0]], [?9 + list2[2][1], ?10 + list2[2][0]], [?9 + list2[3][1], ?10 + list2[3][0]], [?9 + list2[4][1], ?10 + list2[4][0]]); #気付いたのだけど、回転だけじゃなく裏返しの場合も必要だった
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?11 - list2[0][1], ?12 - list2[0][0]], [?11 - list2[1][1], ?12 - list2[1][0]], [?11 - list2[2][1], ?12 - list2[2][0]], [?11 - list2[3][1], ?12 - list2[3][0]], [?11 - list2[4][1], ?12 - list2[4][0]]);
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?13 - list2[0][0], ?14 + list2[0][1]], [?13 - list2[1][0], ?14 + list2[1][1]], [?13 - list2[2][0], ?14 + list2[2][1]], [?13 - list2[3][0], ?14 + list2[3][1]], [?13 - list2[4][0], ?14 + list2[4][1]]);
(list1[0], list1[1], list1[2], list1[3], list1[4]) != ([?15 + list2[0][0], ?16 - list2[0][1]], [?15 + list2[1][0], ?16 - list2[1][1]], [?15 + list2[2][0], ?16 - list2[2][1]], [?15 + list2[3][0], ?16 - list2[3][1]], [?15 + list2[4][0], ?16 - list2[4][1]]);
}
not_match_check(A_position_list, B_position_list);
not_match_check(A_position_list, C_position_list);
not_match_check(B_position_list, C_position_list);
print(table);
まあ、初心者と思って許してほしい。pythonのリストの処理の方法について調べておかないとな。あとeveryについても考察を深めないと。
解き方としては、5つブロックのピースの形は結構決まっているので、それを手がかりにしたら良いのではないか。
例えばWの形をしたブロックは、隅には置けないし、真ん中に置くにしても残りブロックが5にならない。そういう感じで。
『5cm×5cmの方眼があります。この上に2cm×2cmの透明なシートを10枚、方眼のワクにそって置きました。シートは5cm×5cmのワクをはみだしておいてはいけません。また、全く同じ場所に2枚以上重ねておくことがないようにしました。
図の○のマスはシートが奇数枚重なっている場所、×のマスはシートが偶数枚重なっているか、またはシートが無いマスです。
何も書いていないマスはシートがあるのかないのか、何枚重なっているのかわかりません。何も書いていないマスに○か×を書き入れてマスをうめなさい。
（図）
| ○ | ○ | ○ | ○ | |
| × | × | ○ | ||
| × | × | ○ | × | |
| × | ||||
| × | ○ | × | × |
table := [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]
];
add_2_table(X, Y, table){
table[X][Y] := table[X][Y] + 1;
table[X + 1][Y] := table[X + 1][Y] + 1;
table[X][Y + 1] := table[X][Y + 1] + 1;
table[X + 1][Y + 1] := table[X + 1][Y + 1] + 1;
}
add_list := [[A, B], [C, D], [E, F], [G, H], [H, I], [J, K], [L, M], [N, O], [P, Q], [R, S]];
add_list.not_equal;
for(list1 in add_list){
add_2_table(list1[0], list1[1], table);
}
table[0][0], table[0][1], table[0][2], table[0][4], table[1][4], table[2][2], table[4][2] == 2 * ? + 1;
table[1][2], table[1][3], table[2][0], table[2][1], table[2][3], table[3][3], table[4][0], table[4][3], table[4][4] == 2 * ?;
result_table := [~4][~4];
for(i in range(5)){
for(j in range(5)){
if(table[i][j] == 2 * ? + 1){ result_table[i][j] := "○" }
if(table[i][j] == 2 * ?){ result_table[i][j] := "×" }
}
}
print(result_table);
解き方としては、シートの置き方は全部で16通りあって、6通り否定すれば良い。制約が大きい端っこに注目する。
まず右下端と左下端は置かれていない。そうすると、右端の一つ左隣りも置かれていない。これで3つ。ちなみにその隣は置かれている。
右上端と左上端は置かれている。そうすると、左上端の一つ隣は置かれていない。これで4つ目。ちなみのその隣は置かれている。右上端の一つ下も置かれていない。これで5つ目。
そうすると、右上端の斜め一つ下が、3シート分決まっていて×なのが×と表示されているので、残り1シートも何もしない。これで6シート。実際に書いてみて、これが答えだった。