アルゴリズムパズル 29-48 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題「の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 29 魔法陣再び

足して15になる組み合わせは(1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7), (4,5,6)で，そうすると中央の数字は5以外ありえないことがわかる(中央は縦横斜めで4種類の和が15にならないといけないので)．そこから(1,5,9)をどう配置するかとか理詰めで考えていけば解は出て，回転対称とかやれば8通りある事がわかる．

2.2. 30 棒の切断

まぁなんかわかる．どんだけ頑張ってもn回の切断では2^n個の分割しかできないので100<2^7より最低でも7回だし7回でできるので7回でできる！！！！みたいな．
一般の場合は帰納的に証明できそうという感じだった(n=1明らか，n>1，n>=a_1をみたすもので最大のa_1=2^kとa_2=n-a_1にまず切断するとa_1>a_2より～みたいな)．

2.3. 31 3つの山のトリック

3分探索

2.4. 32 シングル・エリミネーション方式のトーナメント

シングル・エリミネーション方式？僕らの知ってるトーナメント戦であってるのか……？という不安があったので図を入れるか訳注入れるかしてほしかった．
有名な問題なので(a) (b)は明らかだけれど(c)は何が言いたいのかさっぱりわからなかったし，解答を見て問題文ちゃんと書けやとなった．

2.5. 33 魔法陣と擬似魔法陣

29を解いたあとなら割とすぐわかると思う．

2.6. 34 星の上の硬貨

ちょろい．

2.7. 35 3つの水入れ

初期状態の記述を読み漏らしてたけれどこれは試行錯誤してればいつか最適解みつかるでしょ感(本の解答も全幅探索紹介してるし)．

2.8. 36 限られた多様性

nが適当な数字のときについて考えたら普通にいけるやん！となって答え見たら不覚にも奇数のこと考えてなかった．

2.9. 37 2n枚の硬貨の問題

苦戦した．最初の僕の解は，重ねた状態でNクイーン問題解けば良いなとなったがNクイーン問題が任意のn>4で解を持つことが怪しかったし答えちら見したら貪欲っぽいことやってたのでもう少し考えて同じ構成法に至った．

2.10. 38 テトロミノによる敷き詰め

まぁ考えればわかる．ここまでちゃんと解いていれば不変条件とか市松模様の色とか散々やったのでそのタイプやろなぁとなる．

2.11. 39 盤面上の一筆書き

ルネジムだ！！！！！！！！！！！！ってなった．
エメラルドでいきなり出てきたルネジムのおっさん，ほんと影が薄いですよね．
とりあえずbは良いとして，aの理由付けがうまく行かなかった．
上下左右にある3x3の領域を埋める方法は，3x3の外から入ってきて全部埋めて出る方法は限られていること，最終的な位置が決まってることには気づいたので多分無理だよな……みたいな理由付けで答えを見たらなるほどーとなりましたね……

2.12. 40 交互に並ぶ4つのナイト

チュートリアルを見てればわかる．

2.13. 41 電灯の輪

とりあえず全部つければ全部つくことには幾つかのケースで試せばわかるし，3の倍数のときはうまくやれることにも気づくでしょう．

2.14. 42 もう1つの狼と山羊とキャベツのパズル

n>1ではできないと思って答えを見たら違った．
WCHGとGHCWはわかったが，n=2の場合はその2つをくっつけることしか考えてなくて，WCHGWCHGはダメじゃん！とおもいこんで完全に間違えた．
とりあえずn=2をちゃんと理詰めでやればよかった．

2.15. 43 数の配置

上手いこと思いついたと思って喜々として証明を書いてたら違ってることに気づいた．
一応とりあえず1からnの数字を並べて，左から見てって不等号が成り立ってないところは入れ替えるというのを入れ替えがなくなるまで繰り返せば行けそうだけれどうまくいくという証明はできなくてうーん．答えみたいな方法正直思いつかんよ．

2.16. 44 より軽いか？より重いか？

解答とは少し違ってた．

n=3mのとき，|A|=ｍ, |B|=m, |C|=mとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるのでAとCを比較
・AとBを比較して違う重さ→Cはすべて本物なのでAとCを比較
n=3m+x(x∈{1,2})のとき，|A|=ｍ, |B|=m, |C|=m+xとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるので，AとBから|D|=m+xなるように硬貨を集めてCとDを比較
・AとBを比較して違う重さ→Cは本物なのでCからx枚を除いたものをDとしてAとDを比較

これでも行けるはず．

2.17. 45 ナイトの最短経路

チェスを上が来たとなるように東西南北に向けて考えると，ナイトが南南東に進むと(dx,dy)=(1,2)，東南東に進むと(dx,dy)=(2,1)なので南南東に進んだ回数をn，東南東に進んだ回数をmとして右下に到着できるn,mを求めた．

2.18. 46 3色配置

適当にやればいけるやろぐらいの解答しか思いつかなかった．答え見てすげーなーってなった．

2.19. 47 展示計画

(a)自明だったので適当にやったら1多く答えてしまった．(b)ルネジムの問題(No. 39)を見た後なのでまぁわかる．

2.20. 48 マックナゲット数

適当に足したりしてたら気づくでしょ．

3. 感想

競技プログラミングに似ている問題があるので競技プログラミングの向上が期待できそうだけれどほんと貪欲思いつかないのでアレ．
「それ貪欲で解けるよ」ってほんと何もヒントになってないからな～💢💢💢💢💢💢