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

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

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

『下の25個のマスに、3、4、5のどれかの数字を1つずつ書き入れます。このとき、次のルールを満たさなければなりません。
『ルール』「5」が書かれたマスの上下左右に隣り合うマスにかかれた数字の合計は必ず3の倍数でなければならない［例1、例2］

（例1）

		4
	4	5	3
		4

（例2）

5	3
3

このとき、25個の数字の和のうち最大のものを求めなさい。

（図）

』

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

while(table[?][?] ∋ false) {
　table[?1 + 1][?2] + table[?1 - 1][?2] + table[?1][?2 + 1] + table[?1][?2 - 1] == ? * 3;

　or(3) {
　　table[?1][?2] := 3;
　} or {
　　table[?1][?2] := 4;
　} or {
　　table[?1][?2] := 5;
　}
}

(table[?][?].sum)を最大化するように設定;

print(table);

解き方を考えると、2つで3の倍数になる数字の組み合わせ、3つの組み合わせ、4つの組み合わせを考えれば良いのではないか。
4は3+1で、5は3+2なので、2つの場合は、3と3か、4と5。3つの場合は、3と3と3、4と4と4、5と5と5、4と5と3。
4つの場合は、5と5と5と3、5と5と4と4、5と4と3と3、4と4と4と3、3と3と3と3、かな。

2つの場合は、4と5 > 3と3。3つの場合は、5と5と5 > 4と4と4 = 4と5と3 > 3と3と3。4つの場合は、5と5と5と3 = 5と5と4と4 > 5と4と3と3 = 4と4と4と3 > 3と3と3と3。
とりあえず一番制約が大きい端っこから展開していったら、最大っぽいものができたので、これかなと。
　

09年度トライアル問題　問題4

『（図）

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15
16	17	18	19	20
21	22	23	24	25

図のような25個のマスに、1〜25の数字が1つずつ書かれたカードを使って、以下のルールで、ビンゴゲームを行います。
ルール①：1〜25の数字が1つずつ書かれたボールが箱の中に入っており、箱から取り出したボールの番号と同じ数字のマスを開く。
ルール②：たて、横、斜めのいずれかで開いているマスが5つ並べばビンゴ。

さて、必ずビンゴになるためには、最低何個のボールを箱から取り出せば良いでしょうか。』

table := [
　[1, 2, 3, 4, 5],
　[6, 7, 8, 9, 10],
　[11, 12, 13, 14, 15],
　[16, 17, 18, 19, 20],
　[21, 22, 23, 24, 25]
];

box := [1~25]; #あーっと、どうするかな。まあいつか考えるか

while(!(table[?1][?] == false || table[?][?2] == false || list(map(lambda x: table[x][x], range(5))).every == false || list(map(lambda x: table[x][4 - x] == false, range(5))).every == false)) { #非常に汚い。どうすれば良いんだろう
　current_ball := box.pop(?3);

　table[?][?].(it == current_ball) := false;
}
~.数 == result;

resultを最大化するように設定;

print(result);

ビンゴにならない場合の最大値を求めて、それにプラス1すれば良い。
普通に考えて、縦と横を防ぐには最低5つ必要で、それで斜めも防げるので、25-5=20、がビンゴにならない最大値で、だから答えは21だろう。
　

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

『（図）

			・・・
			・・・

上の図のような（2×2009＝）4018マスの中に下のルール通りに、2008個の○を入れていきます。
ルール1：1つのマスに入れる○は1つだけ。
ルール2：○が入れてあるマスにとなりあうマスの中に○を入れてはいけない。（斜めのマスには入れられます）

このとき、○を入れるマスの選び方は何通りありますか。
ただし、回転させたり裏返すと同じものになるものも別々に1通りと数えます。』

table := [~1][~2008]; #どうするかな、本当に

for(i in range(2008)) {
　table[?1 + 1][?2], table[?1 - 1][?2], table[?1][?2 + 1], table[?1][?2 - 1] != "○"; #リストの外はNoneということにしたい。pythonだとどうするんだろう

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

print(table.種類.数);

必ず交互に置くことになるわけだが、1列分だけ空く。まず空く列だけで2009通りはある。
更に空いた列の左で、その交互が上から始まるか下から始まるかの2通り、空いた列の右でも2通り。
よって2009通りのそれぞれにおいて、2*2=4通り。2009*4=8036。
しかし、一番端の列が空く場合は2通りしか無い。よって8036-2-2=8032で、8032通りが答えになるだろう。

空いた列の左右それぞれにおいて拘束し合っていて、空いた列が2009通りあって、というのは、何か法則性というか、普遍性がある気がする。
　

09年度ファイナル問題　問題6

『下の16個のマスに16個のオセロのコマが、すべて白が上向きとなるように（黒が下向き）ならべてあります。このオセロのコマに次の操作を行います。
　操作：たて1列の4個のコマ　または　よこ1列の4個のコマ　を4個ともひっくりかえす。
この操作を何度か行うと、白と黒のいろいろな並び方ができますが、それは全部で何通りありますか。最初の「すべて白」もふくめて答えなさい。

（図）

白	白	白	白
白	白	白	白
白	白	白	白
白	白	白	白

』

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

for(i in range(?)) {
　or(1) {
　　for(cell in table[?1]) {
　　　if(cell == "白) {
　　　　cell := "黒";
　　　} else {
　　　　cell := "白";
　　　}
　　}
　} or {
　　for(cell in table[?][?2]) {
　　　if(cell == "白) {
　　　　cell := "黒";
　　　} else {
　　　　cell := "白";
　　　}
　　}
　}
}

print(table.種類.数);

同じ列や行で2回ひっくり返すと、その列や行の影響は最初に戻る。よって、それぞれの列や行はひっくり返したか・返していないかの2通りでしか無い。
それで単純に考えれば2^8なんだが、頭の中でああでもないこうでもないと試行錯誤して分かったが、それでできあがる盤面はそれぞれ2通りの作り方がある。
例えば全盤面白は、何もしないか、全部でひっくり返すか。1列と1行でできる盤面は、他の3列と3行で再現できる。2列と2行も、他の2列と2行で再現できる。別に順番が変わっても、列や行同士は影響を与え合わないので、自由に変えることができる。
どうしてそうなるかは分からないが、まあだからおそらく、2^7=128通りだろう。答えを見たら正解だった。
　

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

『3×3のオセロの盤のすべてのマスにオセロの駒を置いた後に、図のようにオセロのルールでひっくり返る駒がどこにもないような置き方は、図の場合もふくめて全部で何通りありますか。
ただし、回転したり裏返して重なるものも、それぞれ1通りとしてかぞえるものとします。

（図）

白	白	黒
白	黒	黒
黒	黒	黒

』

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

table[?][?] := カブり無しで全部に : ? : カブり有り := "白", "黒";

every(x, y) {
　table[x] != ["白", "黒", "白"];
　table[x] != ["黒", "白", "黒"];
　table[?][y] != ["白", "黒", "白"];
　table[?][y] != ["黒", "白", "黒"];
}

all_table := every.table;

for(table1 in all_table) {
　for(table2 in all_table) {
　　if(table1 is table2) { continue; }

　　if(table1 == table2) {
　　　all_table.remove(table1);

　　　break;
　　}
　　,
　　if(table1 == table2.reverse || table1 == list(map(lambda y: table2[y].reverse, range(3))) || table1 == list(map(lambda y: table2[y].reverse, range(3))).reverse) {
　　　all_table.remove(table2);
　　}
　}
}

print(len(all_table));

こんな感じで良いかな。

まず全体の数は、2^9だけあるだろう。そこからどれだけ引けばよいかということだが。

あー、いや、俺これやったことあるな。つまり、左から黒が、あるいは白がどれだけ張り出すか、で単純化することができる。例えば黒を考えると、（上が一番大きくてどんどん減っていく場合は、）1つ下の行はその行の黒の数を超えない。そう考えれば、まず行でオセロのように挟み込まれることは無いし、列でも挟み込まれることは無くなる。
左から白が張り出すパターンと黒が張り出すパターンの2通り、そして、上が一番大きくて減っていくパターンと上が一番小さくて増えていくパターンの2通り。1パターンについて考えて、×4すれば良い。いや、問題文的に、×4せずそのままで良いのか。
0はもう一方の3なので考えないとして、一番上が1だったら1通り。2だったら、211か、222か、221。3だったら、311か、322か、321か、333か、332か、331か。
1通り+3通り+6通りで、10通り。

1行辺りで2×2×2だったのが、境界がどこかという風に単純化された。0を考えないとして、もうすでに3×3×3の問題になっている（後から答えを2倍にするとして）。
下は上以下という制約をつけることで、更に探索空間？は小さくなるのだが、もう一方で後半は、これは制約のルールから生成してしまうというようなパターンの問題でもあるのかもしれない。

んんん、いや念の為に答えを見てみると、58通りになっているな。確かに少なくとも、333は黒なので、白の場合も必要で、俺の解答は間違っているな。まあ良いか。

これでジュニア算数オリンピックの二次元配列の問題は終わり。次は三次元配列だと綺麗なのだが、ちょっと休憩がてらグラフの問題でも挟むかな。それは1回で終わるんで。