【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックの三次元配列の問題について考察していく。
『すべて同じサイコロを図のように積み上げました。
このサイコロのA、B、Cの面と反対側の面のアルファベットをそれぞれ求めなさい。
(図 上がA・左がB・右がC、上がE・左がF・右がD、上がD・左がC、左がE・右がA、の4つ。)』
素直な繋がり方、つまり普通に隣り合ったり、真っ直ぐに4つ繋がっていて逆側と逆側が繋がったり、という繋がり方。巻き付くような繋がり方。同じブロックに巻き付く同士で素直にくっつく繋がり方。の大雑把に三種類の繋がり方がある。
最初はグラフで何とかならないかと思っていたが、数字の並び方が違う二種類のダイスの一方だけ、というのがどうも表現できなかった。おそらく二次元配列のような縦と横で制約し合う必要があるからだろう。
同じコードの繰り返しが妙に多い。もちろん、特にこれは読む必要は無い。このブログは記録を残しておくことに意味があるのであって、読まれることに意味があるのでは無い。
table := [~3][~3]; or(1) { table[?1][?2] := "A"; table[?1 + 1][?2] := "B"; table[?1][?2 + 1] := "C"; } or { table[?1][?2] := "A"; table[?1][?2 - 1] := "B"; table[?1 + 1][?2] := "C"; } or { table[?1][?2] := "A"; table[?1 - 1][?2] := "B"; table[?1][?2 - 1] := "C"; } or { table[?1][?2] := "A"; table[?1][?2 + 1] := "B"; table[?1 - 1][?2] := "C"; } or(1) { table[?3][?4] == false; table[?3 + 1][?4] == false; table[?3][?4 + 1] == false; table[?3][?4] := "E"; table[?3 + 1][?4] := "F"; table[?3][?4 + 1] := "D"; } or { table[?3][?4] == false; table[?3][?4 - 1] == false; table[?3 + 1][?4] == false; table[?3][?4] := "E"; table[?3][?4 - 1] := "F"; table[?3 + 1][?4] := "D"; } or { table[?3][?4] == false; table[?3 - 1][?4] == false; table[?3][?4 - 1] == false; table[?3][?4] := "E"; table[?3 - 1][?4] := "F"; table[?3][?4 - 1] := "D"; } or { table[?3][?4] == false; table[?3][?4 + 1] == false; table[?3 - 1][?4] == false; table[?3][?4] := "E"; table[?3][?4 + 1] := "F"; table[?3 - 1][?4] := "D"; } or(1) { table[?5][?6] == "D"; table[?5 + 1][?6] == "C"; } or { table[?5][?6] == "D"; table[?5 - 1][?6] == "C"; } or { table[?5][?6] == "D"; table[?5][?6 + 1] == "C"; } or { table[?5][?6] == "D"; table[?5][?6 - 1] == "C"; } or(1) { table[?7][?8] == "E"; table[?7 + 1][?8] == "A"; } or { table[?7][?8] == "E"; table[?7 - 1][?8] == "A"; } or { table[?7][?8] == "E"; table[?7][?8 + 1] == "A"; } or { table[?7][?8] == "E"; table[?7][?8 - 1] == "A"; } dice := [ "A": [], "B": [], "C": [], "D": [], "E": [], "F": [] ]; #Wを見つけた場合、端を繋げる。特殊な一例の場合はWからはみ出した1個にも繋げる。Wのパターンでくっついた先で反応するからで、本当はもっと普遍的に書くべき for(i in range(4)) { for(j in range(4)) { if(table[i][j], table[i][j + 1], table[i - 1][j + 1], table[i + 1][j], table[i + 1][j - 1] != false) { dice[table[i - 1][j + 1]].append(table[i + 1][j - 1]); dice[table[i + 1][j - 1]].append(table[i - 1][j + 1]); if(table[i + 2][j - 1] != false) { dice[table[i + 2][j - 1]].append(table[i - 1][j + 1]); dice[table[i - 1][j + 1]].append(table[i + 2][j - 1]); } if(table[i - 1][j + 2] != false) { dice[table[i - 1][j + 2]].append(table[i + 1][j - 1]); dice[table[i + 1][j - 1]].append(table[i - 1][j + 2]); } } if(table[i][j], table[i + 1][j], table[i + 1][j + 1], table[i][j - 1], table[i - 1][j - 1] != false) { dice[table[i + 1][j + 1]].append(table[i - 1][j - 1]); dice[table[i - 1][j - 1]].append(table[i + 1][j + 1]); if(table[i + 2][j + 1] != false) { dice[table[i + 2][j + 1]].append(table[i - 1][j - 1]); dice[table[i - 1][j - 1]].append(table[i + 2][j + 1]); } if(table[i - 1][j - 2] != false) { dice[table[i - 1][j - 2]].append(table[i + 1][j + 1]); dice[table[i + 1][j + 1]].append(table[i - 1][j - 2]); } } if(table[i][j], table[i][j - 1], table[i + 1][j - 1], table[i - 1][j], table[i - 1][j + 1] != false) { dice[table[i + 1][j - 1]].append(table[i - 1][j + 1]); dice[table[i - 1][j + 1]].append(table[i + 1][j - 1]); if(table[i + 1][j - 2] != false) { dice[table[i + 1][j - 2]].append(table[i - 1][j + 1]); dice[table[i - 1][j + 1]].append(table[i + 1][j - 2]); } if(table[i - 2][j + 1] != false) { dice[table[i - 2][j + 1]].append(table[i + 1][j - 1]); dice[table[i + 1][j - 1]].append(table[i - 2][j + 1]); } } if(table[i][j], table[i - 1][j], table[i - 1][j - 1], table[i][j + 1], table[i + 1][j + 1] != false) { dice[table[i - 1][j - 1]].append(table[i + 1][j + 1]); dice[table[i + 1][j + 1]].append(table[i - 1][j - 1]); if(table[i - 2][j - 1] != false) { dice[table[i - 2][j - 1]].append(table[i + 1][j + 1]); dice[table[i + 1][j + 1]].append(table[i - 2][j - 1]); } if(table[i + 1][j + 2] != false) { dice[table[i + 1][j + 2]].append(table[i - 1][j - 1]); dice[table[i - 1][j - 1]].append(table[i + 1][j + 2]); } } } } #まあ良くないコードだということは分かる #普通に隣接するものを追加する for(i in range(4)) { for(j in range(4)) { if(table[i + 1][j] != false) { dice[table[i][j]].append(table[i + 1][j]); } if(table[i - 1][j] != false) { dice[table[i][j]].append(table[i - 1][j]); } if(table[i][j + 1] != false) { dice[table[i][j]].append(table[i][j + 1]); } if(table[i][j - 1] != false) { dice[table[i][j]].append(table[i][j - 1]); } } } #縦とか横に4つ繋がっている場合、その端と端をそれぞれに追加する every(y) { #あれこれってfor文で良くないか? if(table[y][?] != false) { dice[table[y][0]].append(table[y][3]); dice[table[y][3]].append(table[y][0]); } } every(x) { if(table[?][x] != false) { dice[table[0][x]].append(table[3][x]); dice[table[3][x]].append(table[0][x]); } } def right_turn(to_y, to_x) { #巻き付きを判定する際に補助的に使う if(to_y == 0 && to_x == 1) { to_y := 1; to_x := 0; } elif(to_y == 1 && to_x == 0) { to_y := 0; to_x := -1; } elif(to_y == 0 && to_x == -1) { to_y := -1; to_x := 0; } elif(to_y == -1 && to_x == 0) { to_y := 0; to_x := 1; } return to_y, to_x; } def left_turn(to_y, to_x) { if(to_y == 0 && to_x == 1) { to_y := -1; to_x := 0; } elif(to_y == -1 && to_x == 0) { to_y := 0; to_x := -1; } elif(to_y == 0 && to_x == -1) { to_y := 1; to_x := 0; } elif(to_y == 1 && to_x == 0) { to_y := 0; to_x := 1; } return to_y, to_x; } def left_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link) { #引数が多いが、他に方法が思いつかなかった while(table[twine_y][twine_x]) { #蔦のように巻き付く側のブロック twine_dice := table[twine_y][twine_x]; if(table[axis_y + to_y][axis_x + to_x] == false) { dice[axis_link].append(twine_dice); #「axis_link」は、再帰先のためにそう名付けた。巻きついた後にその先っぽを軸にまた巻き付くことがあるが、その先っぽは離れた場所にあるので dice[twine_dice].append(axis_link); } else { false; #普通の文での制約みたいに、or文とかで分岐した流れ全体を消してしまう } to_y, to_x := left_turn(to_y, to_x); twine_y := twine_y + grow_y; twine_x := twine_x + grow_x; } if(table[axis_y + to_y][axis_x + to_x]) { twine_y_2nd := axis_y + to_y; twine_x_2nd := axis_x + to_x; grow_y_2nd := to_y; grow_x_2nd := to_x; to_y_2nd := to_y; to_x_2nd := to_x; link_axis_2nd := table[twine_y - grow_y][twine_x - grow_x]; to_y, to_x := right_turn(to_y, to_x); axis_y_2nd := axis_y + to_y; axis_x_2nd := axis_x + to_x; right_turn_twine(axis_y_2nd, axis_y_2nd, to_y_2nd, to_x_2nd, twine_y_2nd, twine_x_2nd, grow_y_2nd, grow_x_2nd, link_axis_2nd); } } def right_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link) { while(table[twine_y][twine_x]) { twine_dice := table[twine_y][twine_x]; if(table[axis_y + to_y][axis_x + to_x] == false) { dice[axis_link].append(twine_dice); dice[twine_dice].append(axis_link); } else { false; } to_y, to_x := right_turn(to_y, to_x); twine_y := twine_y + grow_y; twine_x := twine_x + grow_x; } if(table[axis_y + to_y][axis_x + to_x]) { twine_y_2nd := axis_y + to_y; twine_x_2nd := axis_x + to_x; grow_y_2nd := to_y; grow_x_2nd := to_x; to_y_2nd := to_y; to_x_2nd := to_x; link_axis_2nd := table[twine_y - grow_y][twine_x - grow_x]; to_y, to_x := left_turn(to_y, to_x); axis_y_2nd := axis_y + to_y; axis_x_2nd := axis_x + to_x; left_turn_twine(axis_y_2nd, axis_y_2nd, to_y_2nd, to_x_2nd, twine_y_2nd, twine_x_2nd, grow_y_2nd, grow_x_2nd, link_axis_2nd); } } for(i in range(4)) { for(j in range(4)) { if(table[i][j], table[i + 1][j], table[i][j + 1] != false) { if(table[i + 2][j] && table[i][j + 2]) { false; } #このor文や変数などでの分岐全体が消滅。普通の文でのA==Bのような。 dice[table[i + 1][j]].append(table[i][j + 1]); dice[table[i][j + 1]].append(table[i + 1][j]); if(table[i + 2][j]) { axis_y := i; axis_x := j + 1; to_y := 0; #軸に巻き付く際の判定に使う。1 or 0 or -1 or 0 to_x := 1; twine_y := i + 2; twine_x := j; grow_y := 1; grow_x := 0; axis_link := table[axis_y][axis_x]; #再帰先との整合性でこのように名付けてある。巻きついた後にその先っぽにまた巻き付くことがあるが、その時にその先っぽは離れた場所にあるので left_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } elif(table[i][j + 2]) { axis_y := i + 1; axis_x := j; to_y := 1; to_x := 0; twine_y := i; twine_x := j + 2; grow_y := 0; grow_x := 1; axis_link := table[axis_y][axis_x]; right_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } } if(table[i][j], table[i + 1][j], table[i][j - 1] != false) { if(table[i + 2][j] && table[i][j - 2]) { false; } dice[table[i + 1][j]].append(table[i][j - 1]); dice[table[i][j - 1]].append(table[i + 1][j]); if(table[i + 2][j]) { axis_y := i; axis_x := j - 1; to_y := 0; to_x := -1; twine_y := i + 2; twine_x := j; grow_y := 1; grow_x := 0; axis_link := table[axis_y][axis_x]; left_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } elif(table[i][j - 2]) { axis_y := i + 1; axis_x := j; to_y := 1; to_x := 0; twine_y := i; twine_x := j - 2; grow_y := 0; grow_x := -1; axis_link := table[axis_y][axis_x]; right_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } } if(table[i][j], table[i - 1][j], table[i][j - 1] != false) { if(table[i - 2][j] && table[i][j - 2]) { false; } dice[table[i - 1][j]].append(table[i][j - 1]); dice[table[i][j - 1]].append(table[i - 1][j]); if(table[i - 2][j]) { axis_y := i; axis_x := j - 1; to_y := 0; to_x := -1; twine_y := i - 2; twine_x := j; grow_y := -1; grow_x := 0; axis_link := table[axis_y][axis_x]; left_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } elif(table[i][j - 2]) { axis_y := i - 1; axis_x := j; to_y := -1; to_x := 0; twine_y := i; twine_x := j - 2; grow_y := 0; grow_x := -1; axis_link := table[axis_y][axis_x]; right_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } } if(table[i][j], table[i - 1][j], table[i][j + 1] != false) { if(table[i - 2][j] && table[i][j + 2]) { false; } dice[table[i - 1][j]].append(table[i][j + 1]); dice[table[i][j + 1]].append(table[i - 1][j]); if(table[i - 2][j]) { axis_y := i; axis_x := j + 1; to_y := 0; to_x := 1; twine_y := i - 2; twine_x := j; grow_y := -1; grow_x := 0; axis_link := table[axis_y][axis_x]; left_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } elif(table[i][j + 2]) { axis_y := i - 1; axis_x := j; to_y := -1; to_x := 0; twine_y := i; twine_x := j + 2; grow_y := 0; grow_x := 1; axis_link := table[axis_y][axis_x]; right_turn_twine(axis_y, axis_x, to_y, to_x, twine_y, twine_x, grow_y, grow_x, axis_link); } } } } for(v in values(dice)) { v := v.種類; v.数 == 4; } print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["A"])); print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["B"])); print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["C"])); print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["D"])); print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["E"])); print(["A", "B", "C", "D", "E", "F"].(it ∉ dice["F"]));
まあプログラマーだったらもっと綺麗に書くんだろうが、こんなものだろう。答えなんか知らない。
引数が多いから、それ無しでやる方法を考えるか、オブジェクト指向みたいなので管理するかか?よく分からないが。
プログラマーならタイプミスを嫌って、重複するお互いに追加するコードも別に関数を作ったかもしれない。
テトリスみたいなテーブルに回転するテーブルを入れるみたいなコードを書けば、前半も大きく削減できるか。まあやらないが。
でもやっぱり引数で、このままの方法でも、"上"とか"下"とかで直感的に管理すべきだったかもしれない。growとtoは上手くやれば統合できる。
『1辺が1cmの黒い立方体の面どうしをつなげて立体を作りました。この立体は前後左右上下どの方角から見ても1辺が3cmの黒い正方形に見えます。この立方体にはもっとも少ない場合で何個の1辺が1cmの黒い立方体が使われていますか。
(図は省略)』
table := [~2][~2][~2]; table[?][?][?] := result := "黒"; every(y, x) { #並列にできるものは並列で記述した方が良いのではないか。まあいつか撤廃するかもしれない table[y][x][0] || table[y][x][1] || table[y][x][2]; } every(y, z) { table[y][0][z] || table[y][1][z] || table[y][2][z]; } every(x, z) { table[0][x][z] || table[1][x][z] || table[2][x][z]; } def delete_chain(y, x, z) { table[y][x][z] := false; if(table[y + 1][x][z]) {delete_chain(y + 1, x, z);} if(table[y - 1][x][z]) {delete_chain(y - 1, x, z);} if(table[y][x + 1][z]) {delete_chain(y, x + 1, z);} if(table[y][x - 1][z]) {delete_chain(y, x - 1, z);} if(table[y][x][z + 1]) {delete_chain(y, x, z + 1);} if(table[y][x][z - 1]) {delete_chain(y, x, z - 1);} } for(y in range(3)) { for(x in range(3)) { for(z in range(3)) { if(table[y][x][z] != false) { delete_chain(y, x, z); break; } else { continue; #このcontinueはxのループに対応している } break; } else { continue; } break; } #この記述法はpythonだから良いのであって、特に並列するフローの記法とは相性が悪いかもしれない。他の言語はどうしてるんだろう table[?][?][?] == false; resultを最小化するように設定; print(result);
こういう擬似言語を導入して、数学の本質を明らかにするっていうのは、意義のあることだと思うんだよな。方法として有用かはともかく、やっぱり意味はあると思う。
答えを考えると、まず6方向から9面必要だから、6*9=54面必要。しかしブロックはひと繋がりである必要があって、もの凄く単純に一直線のひと繋がりを考えてみると、ちょうど13個繋がった時に、2+13*4=54面になる。
それで、一筆書きである必要があると思って色々考えてみて無理で、答えを見ると、一筆書きである必要は無かったみたいだ。
俺は2つの段が3つと1つの場合を想定して考えていたが、解答では単純に上と下の段でそれぞれにおいて2個2個で、それを真ん中で繋ぐという感じだった。2つの段で卍型みたいにして、残りの1段で斜めに配置しても良い。
『すべての面が真っ白の1辺が1cmの立方体が27個あります。
これらを組み合わせて1辺が3cmの立方体を作り、表面を青色にぬった後にバラバラにしてからもういちど1辺が3cmの立方体を作り、今度は表面を赤色にぬります。次にやはりバラバラにしてからもう一度1辺が3cmの立方体を作り今度は表面を黄色にぬりました。
最後にできた立方体をバラバラにしたとき、27個の立方体はどれもすべての面に色がぬられていました。
さて、赤・青・黄が2面ずつぬられている立方体は何個ありますか。』
table := [~2][~2][~2]; table[?][?][?] := カブり無しで全部に : ? : カブり有り := []; every(y, x) { table[y][x][0].append("青"); table[y][x][2].append("青"); } every(y, z) { table[y][0][z].append("青"); table[y][2][z].append("青"); } every(x, z) { table[0][x][z].append("青"); table[2][x][z].append("青"); } table[?][?][?] := カブり無しで全部に : ? : カブり無しで全部 := table[?][?][?]; every(y, x) { table[y][x][0].append("赤"); table[y][x][2].append("赤"); } every(y, z) { table[y][0][z].append("赤"); table[y][2][z].append("赤"); } every(x, z) { table[0][x][z].append("赤"); table[2][x][z].append("赤"); } table[?][?][?] := カブり無しで全部に : ? : カブり無しで全部 := table[?][?][?]; every(y, x) { table[y][x][0].append("黄"); table[y][x][2].append("黄"); } every(y, z) { table[y][0][z].append("黄"); table[y][2][z].append("黄"); } every(x, z) { table[0][x][z].append("黄"); table[2][x][z].append("黄"); } every(y, x, z) { table[y][x][z].数 <= 6; } result := table[?][?][?].(it ∋ "青", "青", "赤", "赤", "黄", "黄").数; #それぞれイコールだったりするように、それぞれ含むで良いよな、多分 print(result);
答えを考えると、まず27個全部で6面塗るには、27*6=162面塗る必要がある。大きな立方体に塗る時は、1面辺り9個を6面だから、9*6、更にそれを3回だから、9*6*3=162。つまり1つの塗りも無駄にはできないということ。
塗りの種類は、真ん中の1個の1面、辺の2面、角の3面がある。真ん中の1面の場合、他のどこかで角を使わないと、例えば1,2,2とかだと追いつかない。更に1と3を済ますと、残りは2しか無くなる。つまり真ん中の数の分は、制約として決まってしまうので、問題のサイズが小さくなる。
大きな立方体一つ辺りに、面が6個、辺が12個、角が8個。つまり辺が6個、角が2個、を3回。どうやら真ん中も考える必要があるので、それぞれの角を2個と真ん中の3回を組み合わせて。つまり問題に答えるなら、辺が6個を3回に該当するのが答えで、6個分ではないか。解答は確認しない。
『同じ大きさのサイコロ39個をつなぎ合わせて図のような立体を作りました。
(図は、申し訳ないが省略させてもらう 漢字の「日」の、それぞれ横の縦棒が、立体的に漢字の「中」の中軸になっているような)
できた立体は前後左右上下どの方向から見ても、見えるすべての面の目の数の和(※これをNとします)は6方向とも等しくなっていました。
最大の場合のNと、最小の場合のNをそれぞれ求めなさい。
ただし、サイコロの向かい合う面の和は7になっていることとし、図のA、Bどちらのタイプのサイコロも自由に組み合わせて使えるものとします。
(図 A:正面が1・上が3・右が2 B:正面が1・上が2・右が3)』
table := [ [ [,,,,], [,,,,], ["D", "D", "D", "D", "D"], [,,,,], [,,,,] ] , [ ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"] ] , [ ["D",,,, "D"], [,,,,], ["D", "D", "D", "D", "D"], [,,,,], ["D",,,, "D"] ] , [ ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"], ["D",,,, "D"] ] , [ [,,,,], [,,,,], ["D", "D", "D", "D", "D"], [,,,,], [,,,,] ] ]; for(y in range(5)) { for(x in range(5)) { for(z in range(5)) { if(table[y][x][z] == "D") { dice := []; dice := カブり無しで全部に : ? : カブり無しで全部 := 1, 2, 3, 4, 5, 6; dice[0] + dice[5], dice[1] + dice[4], dice[2] + dice[3] == 7; #[0],[1],[2]に入れた後に、7からそれを引いて残りの対を生成した方が良いか? table[y][x][z] := dice; #ん?これってどういう判定になるんだろう。違うループでdiceが書き換わったらこれも書き換わる? } } } } every(y, x).(table[y][x].@(最小)).sum() == N; #False + False == 0 しかし、「table[y][x].(it != False).@(最小)」じゃないと最小にFalseが引っかかるか?でもそうするとNoneになる? every(y, x).(table[y][x].@(最大)).sum() == N; #何か書き方に問題がある気がする。「every(y, x)~(対象の式)」という風に書いた方が良いか every(y, z).(list(map(lambda x: table[y][x][z], range(5))).@(最小)).sum() == N; every(y, z).(list(map(lambda x: table[y][x][z], range(5))).@(最大)).sum() == N; every(x, z).(list(map(lambda y: table[y][x][z], range(5))).@(最小)).sum() == N; every(x, z).(list(map(lambda y: table[y][x][z], range(5))).@(最大)).sum() == N; 記録1; Nを最小化するように設定; print(N); 記録1~ { Nを最大化するように設定; print(N); }
解き方としては、露出の仕方での最小値をそれぞれ考えて、後から辻褄を合わせる感じかな。2面とか角だったら、1と2とか1と2と3とかできて、コの字だったら、対の7と1で8だし。一番多い角の4面だと、1と2と3と4かな。
一番制約が大きそうな中の字だと、1が3個、2の辺が6個、3の角が4個、4の角が2個。15~35。
いや、最小値で全部を足し合わせて、それから6で割れば良いんじゃないかな。まあ面倒なのでもう考えないけど。最大値は、多分、面の数*7-最小値、ではないか。