ニート歴10年からの数学日記

2008年〜2009年の高一の冬休みから無職。最長で4ヶ月ほどの中断アリ。

ジュニア算数オリンピック　二次元配列の問題　その３

【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックの二次元配列の問題について考察していく。
　

　

06年度トライアル問題　問題2

『次のそれぞれの図形を、○が1個ずつ入った形の等しい図形に分けなさい。
ただし、（例）のように、裏返したり、○の位置がことなっていてもよいものとします。解答用紙の点線にそって分けた線を太線で書き入れなさい。

（例）

　AAA　
　AAA　
○○○CC
BBBCC
BBBCC

　　AA　
　A○A　
　AB○C
B○BCC
BBCC　

（1）

　　　　　　
　○　　○　
　　　　　　
　　○　　　
　　　　　　

（2）

　　　　　　
○○　　　　
　　○　　　
　　　　　　
　　　　　　
　　　　　○
』


table1 := [
　[None, "", "", "", "", None],
　["", "○", "", "", "○", ""],
　[None, "", "", "", "", None],
　[None, "", "○", "", None, None],
　[None, None, "", None, None, None]
];
shape_list := [];

def make_shape(x, y) {
　shape_list := 追加 := (x, y);

　or(1) {
　　return;
　} or {
　　or(?) {
　　　table[x+1][y] != None;
　　　shape_list ∌ (x+1, y);

　　　make_shape(x+1, y);
　　} or {
　　　table[x-1][y] != None;
　　　shape_list ∌ (x-1, y);

　　　make_shape(x-1, y);
　　} or {
　　　table[x][y+1] != None;
　　　shape_list ∌ (x, y+1);

　　　make_shape(x, y+1);
　　} or {
　　　table[x][y-1] != None;
　　　shape_list ∌ (x, y-1);

　　　make_shape(x, y-1);
　　}
　}
}

for(i in range(5)) {
　for(j in range(6)) {
　　if(table[i][j] != None) {
　　　y := i;
　　　x := j;

　　　break;
　　}
　} else {
　　continue;
　}

　break;
}

make_shape(x, y);
result_table1 := [~4][~5];
block_list := ["A", "B", "C"];

for(block in block_list) {
　or(1) {
　　current_shape := shape_list;
　} or {
　　current_shape := list(map(lambda x, y: (y, 4 - x), shape_list));
　} or {
　　current_shape := list(map(lambda x, y: (4 - x, 5 - y), shape_list));
　} or {
　　current_shape := list(map(lambda x, y: (5 - y, x), shape_list));
　} or {
　　current_shape := list(map(lambda x, y: (y, x), shape_list)); #ああクソ裏返しても良いのかよ
　} or {
　　current_shape := list(map(lambda x, y: (x, 5 - y), shape_list));
　} or {
　　current_shape := list(map(lambda x, y: (5 - y, 4 - x), shape_list));
　} or {
　　current_shape := list(map(lambda x, y: (4 - x, y), shape_list)); #こ、これで全部か
　}

　list(map(lambda x, y: table1[?1 + y][?2 + x], current_shape)) ∌ None;
　list(map(lambda x, y: table1[?1 + y][?2 + x], current_shape)) ∋ "○";
　list(map(lambda x, y: result_table1[?1 + y][?2 + x], current_shape)) ∌ true;

　list(map(lambda x, y: result_table1[?1 + y][?2 + x], current_shape)).every := 全部に : ? : カブり有り := block;
}

for(i in range(5)) {
　for(j in range(6)) {
　　(bool(table1[i][j]) || table1[i][j] == "") == bool(result_table1[i][j]);
　}
}

print(result_table);


最低限、make_shapeの際に、count変数を外部に宣言して、shape_listの個数を「table1[?][?].(it != None).数 / 3」個にした方が良かったかな。

リストにおいて跨る形でリストを配置することができたら、もう少し違う風に記述できるような気もするが、そのリストに穴が空いていて、その内部の穴というかNoneに違うリストがパズルみたいに重ね合わせるように、という所まで考えると、計算量的にも変わらないような気もするし、不毛な考えなんだろうか。やるならとりあえず自然言語で書いてみるが、とりあえずこの考えは保留しよう。


問題1は、制約が大きい端っこというか、○に挟まれて独立しているブロックはそれぞれ決定。でそれぞれ○の真横のブロックを侵犯しようとしてもできそうに無いし、残り6ブロックは適当に考えれば良いんじゃないか。
問題2は、いろいろ考えたけど分からないなあ。


答えを見ると、とにかく失敗をおそれず手を動かして試してみるしか無いとのことで、まず制約が大きい辺を、5つ繋がりで組み合うように4つ作って、それから卍みたいな感じで（いやナチスのハーケンクロイツだな）組み合わせて、それが答え。
エッシャーみたいに構成できるならそれが一番簡単だというのもあるし、そもそも確かに辺をどう分けるかから発想すべきだった。
　

06年度トライアル問題　問題5

『1cm×2cmの長方形の紙がたくさんあります。

これらを2cm×3cmの長方形の上に、重なることもはみ出すこともすきまを作ることもなくならべると、（例）のように3通りの置き方があります。

（例）

ABC
ABC

AAC
BBC

ABB
ACC

では、1辺1cmの正方形16個でできた（図1）の図形の上への置き方は何通りありますか。

（図1）

　　　　　　
　　　　　　
　　　　　　
　　　　　　
』


table := [
　[None, None, None, None, "", ""],
　[None, None, None, None, "", ""],
　["", "", "", "", "", ""],
　["", "", "", "", "", ""]
];

block_set := ();

while(table[?][?] ∋ "") {
　or(1) {
　　table[?1][?2] == "";
　　table[?1][?2 + 1] == "";

　　table[?1][?2] := "○";
　　table[?1][?2 + 1] := "○";
　　block_set := 追加 := ([?1, ?2], [?1, ?2 + 1]);
　} or {
　　table[?1][?2] == "";
　　table[?1 + 1][?2] == "";

　　table[?1][?2] := "○";
　　table[?1 + 1][?2] := "○";
　　block_set := 追加 := ([?1, ?2], [?1 + 1, ?2]);
　}
}

print(block_set.種類.数); #何となく表記がブレているような気も


自分の思考回路としては、まず右の出っ張っている部分のつなぎ目の部分に跨る場合と、跨がらない場合に分ける。
跨る場合は、その上下の横2は決まる。左の8個は、これもその中心の4個で跨る場合と跨がらない場合に分けて、跨る場合は1通りで、跨がらない場合は紙2枚をセットとして2セットと考えて、1セット辺り横に揃えるか縦に揃えるかの2通りなので、2*2=4通り。つまり跨る場合は5通り。
跨がらない場合は、まず出っ張っている部分の1セットで2通り。問題は残りの12個だが、真ん中の列で跨る場合は、そのその横の1セットずつで4通り。真ん中の列で跨がらない場合は、問題文から3通り×3通りで9通りと考える。(4 + 9) * 2 = 26通り。
よって、5通りと26通りで31通りだろう。

まとまりであらかじめ計算しておいて、そのまとまりを適用できる場合と適用できない場合に場合分けする、という問題だったかと思う。
　

06年度ファイナル問題　問題5

『右の正方形ABCDの中の3×3のマス目に石を3個置きます。
ただし、石は1マスに1個までしか置けず、上下左右のとなり合ったマスに2個ならべて置くことはできません。
全部で何通りの置き方がありますか。

（図）
A　　　　　D

　　　
　　　
　　　
B　　　　　C』


table := [~2][~2];

for(i in range(3)) {
　table[?1][?2], table[?1][?2 + 1], table[?1][?2 - 1], table[?1 + 1][?2], table[?1 - 1][?2] != "○"; #この記述はアリか否か。またリストをオーバーした場合

　table[?1][?2] := "○";
}

print(table.種類.数);


俺だったら、大雑把に、真ん中に置く場合と置かない場合を分ける。置く場合は、残りの斜めの4つから2つ選ぶだけで、4 * 3 / 2 = 6通り。
置かない場合は、これまた大雑把に、縦横だけで構成する場合、斜めだけで構成する場合、混ぜる場合に分けて考える。
縦横だけは、お互い干渉しないので、結局は4つの内のどこを残すかで4通り。斜めだけの場合も同じ4通り。
混ぜる場合は、斜めが対角線や、縦同士や横同士で向き合うということはあり得ない。斜めで揃える場合は4通りで、残りの縦横は1つに決まる。縦横で揃える場合も4通りで、残りの斜めは1つに決まる。つまり4+4=8通り。
合わせて、6+4+4+8=22で、22通りが答え。場合分けしただけなような気がする。
　

07年度トライアル問題　問題7

『図1のような5×5の正方形を下の2つのルールで4つの部分に切り分けます。
ルール1．切るときは正方形の辺に平行に、点線にそって切ること。
ルール2．切られた4つの部分をうまく組み合わせると3×3と4×4の2つの正方形ができること。

これらのルール通りの切り分け方として考えられるものを解答欄に例にならって太い線で書き入れなさい。何通りかの切り分け方が考えられますが、例以外に3通り書ければ正解です。ただし裏返しや回転で同じになるものは1通りと考えます。

（図1）

　　　　　
　　　　　
　　　　　
　　　　　
　　　　　

（例）
ルール1

ACCCC
ACCCC
BBBCC
BBBCC
BBBDD

ルール2

BBB
BBB
BBB

CCCC
CCCC
AACC
DDCC
』


table := [~4][~4];
shape_list := [~3];

def make_shape(x, y, shape_list_num) {
　table[x][y] == false;

　shape_list[shape_list_num] := 追加 := (x, y);
　table[x][y] := true;

　or(1) {
　　or(?) { #普通に考えたら0もあり得るが
　　　make_shape(x + 1, y, shape_list_num);
　　} or {
　　　make_shape(x - 1, y, shape_list_num);
　　} or {
　　　make_shape(x, y + 1, shape_list_num);
　　} or {
　　　make_shape(x, y - 1, shape_list_num);
　　}
　} or {}
}

make_shape(0, 0, 0);
make_shape(0, 4, 1);
make_shape(4, 0, 2);
make_shape(4, 4, 3);

table[?][?] ∌ false;

result_table1 := [~2][~2];
result_table2 := [~3][~3];
shape_num := 0;

while(result_table1 ∋ false) {
　or(1) {
　　current_shape := shape_list[?1];

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (4 - y, x), shape_list[?1]));

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (4 - x, 4 - y), shape_list[?1]));

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (y, 4 - x), shape_list[?1]));

　　shape_list.pop(?1);
　}

　for(x, y in current_shape) {
　　result_table1[?2 + y][?3 + x] == false;

　　result_table1[?2 + y][?3 + x] := shape_num;
　}

　shape_num := shape_num + 1;
}

while(result_table2 ∋ false) {
　or(1) {
　　current_shape := shape_list[?1];

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (4 - y, x), shape_list[?1]));

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (4 - x, 4 - y), shape_list[?1]));

　　shape_list.pop(?1);
　} or {
　　current_shape := list(map(lambda x, y: (y, 4 - x), shape_list[?1]));

　　shape_list.pop(?1);
　}

　for(x, y in current_shape) {
　　result_table2[?2 + y][?3 + x] == false;

　　result_table2[?2 + y][?3 + x] := shape_num;
　}

　shape_num := shape_num + 1;
}

print(result_table1, result_table2);


まあちょっとこういうの良くない気もするけど。別に端っこを使うことは無いから、それを利用して計算量というより書く手間を減らした。

なんかこの記述に意味があるんだろうかとまた思ったが、この研究は俺の職業訓練にもなっていて、まあ書くたびに上達はしてると思うんで、研究として途中で折れないような作りになっているのかなと思う。もう特に研究することも無いし（いやあるけどベーシック・イングリッシュ以上という意味で）、このまま最後まで行こうかと思っている。


解説には、答えしか載ってなかった。ただ、3×3や4×4を5×5から切り取って、残りでもう一方を構成できないかという思考回路を辿っているようにも見える。完全では無いが、そちらの方が確かに簡単かもしれない。