2026-04-08

Not Math Puzzle 攻略

はじめに

「Not Math Puzzle」は Baba ライクな倉庫番系パズルで、数式を動かしてゴールを目指すゲームです。私がこのゲームを知るきっかけは、下に貼った YouTube の『[さんすうの時間です【NOT Math Puzzle】]』でした。ユーモアがありつつゲームの面白さが伝わる、いい動画です。必要な知識は基本的に算数だけのはずですが、かなり難しいです。現時点で遊べるステージは一応すべてクリアした（つもり）ものの、丸1か月ほどかかりました（一部は攻略動画を見ました）。

www.youtube.com

とても面白いゲームですが、一部のステージで詰まるとそのまま放置してしまうこともあり、もったいないと感じたので攻略のヒントと答えをまとめました。公式 Discord や公式ページのコメント欄は非常に参考になりました。公式ページでは、Discord でゲームへのフィードバックや攻略に関する投稿・質問ができ、見るだけの参加も歓迎と案内されています。行き詰まったときは、そちらもあわせて参考にしてみてください。

また、完全版のステージも制作されているようなので、そちらも楽しみです。

公式ページ：NOT Math Puzzle | unityroom
公式Discord：https://discord.gg/aGrFZKHWVh

~~TODO になっているステージも更新していく予定です。~~
2026/04/14 更新：(多分)すべてのステージを追加しました。

注意

バージョンは v2+0 です。このゲームの性質上、あるステージが存在すること自体がネタバレになってしまうことがあります。ステージごとに分けてクリックで開く形式にしていますが、基本的には自力で解けないときに参考にしてもらうのがよいと思います。また、ヒントや答えの書き方の粒度にムラがあるので、ご了承ください（Discord で質問するとよいかもしれません）。

記法について

数式は左から右、または上から下に書きます。
たとえば縦向きに =1+3 と書く場合は、次のような配置です。

=
1
+
3

余白は □ で表します。

目次(すべてのステージが出るのでネタバレ注意)

はじめに
注意
記法について
Stage Select
Stage Select 別ステージへの行き方
城
城別ステージへの行き方
中核
中核別ステージへの行き方
- ステージ23'
- ステージ24'
-World
-World 別ステージへの行き方
?
X
青数字の取り方
紫記号の取り方

Stage Select

開く

ステージ1〜3

チュートリアルのため省略。

ステージ4

ヒント

右下で =1+1 を作る。純粋な倉庫番っぽいステージ。

ステージ5

チュートリアルのため省略。

ステージ6

ヒント

9-5= で4を作る。

ステージ7

ヒント1

入れない位置に数式を置いて5を置く必要があるので、まずは1個の = でたくさんのブロックを作ることを目指す。

ヒント2

0-5= で -5 を置く。

ステージ8

ヒント

答えが二桁になるように縦に数式を作る。

ステージ9

ヒント1

0を右に移動させるために、極力ブロックが増えるように数式を作りたい。

ヒント2

計算結果が負になるようにするとブロック数が稼げる。

答え

左下で =11+9 を作る。そのあと答えがマイナス3桁になるように引き算をして、余ったブロックを押し込む。

ステージ10

ヒント1

このゲームの = の仕様を利用する。今後必須になるテクニックとなる。

ヒント2

x+y=z のように = の反対側に数字があると計算結果が出てこない。z をどかすと計算結果が出てくる。

答え

3+2=1 を横向きに配置し、1 をどかして自分が押し出されるようにする。

ステージ11

ヒント1

7x7= の形を作ることは難しそうなので、別の方法を考える。

ヒント2

= は1つしか使わなくてよい。

答え

3x4+7= で 19 を作る。あとは 4 と 9 を押し込む。

ステージ12

ヒント1

ステージ名がヒント。

ヒント2

= を上に押したときに、掛け算の結果が一桁になるように数式を作る。

ヒント3

0 と数字をかけると 0 になる。

答え

横向きに =5x55 を作り、左端で =2x5 を作り、0x... の形を作る。

ステージ13

答え

2+2= で 4 を作る。
2÷4= で 0.5 を作る。

ステージ14

ヒント1

答えが循環小数のときは余白がある限りブロックが生成される。

ヒント2

1÷3= で 3 を取り出して、横向きに 1÷3= を作る。

答え

左上のくぼみに 1 を入れてから =1÷3 を作る。
真ん中の2つのくぼみに . と = を入れて 1 と 3 を取り出して 1÷3= を作る。

ステージ15

ヒント1

.1 のような式を計算に含めると 0.1 として計算される。

ヒント2

右端で ÷ を取り出すのと同時に、循環小数を作るための数字も作る。

答え

=2x2.2 で 4.4 を作る。
右端で 4x2.4= で 6 と ÷ を取り出す。
. と = を縦のくぼみに入れた後に =2÷6 を作る。

ステージ16

答え

一例として、1÷2= で 0.5 を作る。
1÷20= で 0.05 を作る。
.1x0.05= で 0.005 を作る。

ステージ17

ヒント1

0 がある空間から 0 を取り出すことはできない。

ヒント2

計算結果が生成されたときに、新たな数式ができると連鎖的にブロックが生成される。

答え

0 を真上に移動させたときに 0x111= の形になるように数式を作る。
計算結果の 0 ができたときにも 0x111= の形になるように縦に数式を作る。

ステージ18

ヒント1

いくつか別解があるが、シンプルな方法で。= の性質を使う。

ヒント2

= の反対側に数字があると計算結果が出てこないことを利用する。

答え

3÷1=1 を上のくぼみに配置する。
☆ を横から押して 1 をどかす。

ステージ20

答え

1÷0= は ∞ になる。

ステージ21

ヒント1

上のブロックで計算結果が1文字になるようにしたい。

ヒント2

∞ は何を足してもかけても ∞ になる。

答え

下のブロックで =∞+9 で ∞ を作る。
このまま右に押し込み x を取り出す。
上のブロックで ∞x9+9999= を作る。

ステージA

ヒント

93x3=279 で必要な数字が揃う。

答え

=3x3 を縦に並べる。
次に =93x3 をして 279 を作る。
これを順番を合わせて左に置く。
もう一度 =93x3 を作り、邪魔なものをどかしてから 279 を下に押し込む。

ステージB

ヒント

4x4=16 が生成できるスペース、かつ 1 を取り出せる場所を探す。

答え

右下で横向きに 4x4= を作る。順番は =, 4, x, 4 の順で置く。

ステージC

ヒント

a÷∞ は 0 になる。

答え

左に埋め込まれた 0 を使って 9÷0= を作る。
出てきた ∞ をそのまま下に移動し、縦向きに =9÷∞ を作る。

Stage Select 別ステージへの行き方

開く

ステージ16'

答え

1÷2= で 0.5 を作る。
1x0= で 0 を作る。
0÷0= で ■ を作る。

ステージ18'

答え

1÷3= を2回使って 0÷0= を作る。

ステージ20'

答え

1÷12= で 0 を作り、0÷0= を作る。

ステージ21'

ヒント

0 と ∞ を使った不定形を利用する。

答え

上のブロックで 1 を押し込み 0 を取り出す。
下のブロックで ∞ を押し込み x を取り出す。
∞x0= を作る。

城

開く

ステージ101

チュートリアルのため省略。

ステージ102

ヒント

なるべく ☆ に近い位置から + を置けるような数式を用意する。

答え

まず下の + を上に持っていく。
2-22222= で数字を作る。ゴールの + の上に 2+□ と置き、スペースの右に = を置いて左に押すと + がゴールに行く配置にできる。
あとは余ったブロックを = の右に並べて、離れた位置から + をゴールに置く。

ステージ103

ヒント

☆ が押し出されない位置で利用できる数式を活用する。

答え

☆ が動かないように右上で縦に 1-0= を作る。
1 をどかして - 0 = を取り出す。
使い終わった = で = をゴールの上に運ぶ。縦に 0-1= を作る。
生成されたブロックを上に押し込んで - 1 = を取り出す。
あとはブロックが生成されないように - を2つ運ぶ。

ステージ104

ヒント

一番上の 8 と =(虹) で 7 が取り出し続けられるような式を作る。

答え

生成されたブロックをすべて上に押し出せる位置で、横向きに =-1÷2 を作る。
一番上で 8-1=(虹) となるようにブロックを押し込む。
7 が生成されても数式にならないようにブロックを押し込む。例えば使用済み = を虹色 = の下に配置する。

ステージ105

ヒント

虹色 = は両側が数式の場合反応しない。

答え

虹色ブロックの左側で 1x1 を作る。
111 が生成されたら 1 を上にどかす。
x を移動し、右側で 1x1 を作り、左側を 0x111 にする。
1 を上にどかして 0 を生成させ、途中で上から抜け出す。

ステージ106

ヒント1

小数点・数字が並ぶと 0.◯◯ のように扱われて計算が行われる。

ヒント2

小数点の左側で 1x を置いて右から計算が始まれば、小数点が取り出せる。

答え

=(虹) の左側に 1x を置いておき、右側で =(虹)1x1 を作る。
計算が止まっているので、1 を6つ取り出す。
縦の水たまりの位置に、上に1マス空けて x11=x を置く。
上から 1 を左に押し込む。
出てきた 1x を小数点がある行の左に配置しておき、右から =(虹)1x1 を作る。

ステージ107

ヒント

掛け算の結果でちょうど ☆ が取り出せるようになる桁数を探す。

答え

11x11= で 2 を作る。
適当に桁数が大きくなるように数字を作り、◯◯x◯◯=☆ で4桁の数字になるようにして、上から = を押し込み ☆ を取り出す。

ステージ108

ヒント

なるべく計算結果が長くなるように数字を作る。= の性質を使えば8桁あれば足りる。

答え

計算は一例。
-7x2= で -14 を作る。
-72x41 で -2952 を作る。
-72x95422=1 を左のくぼみに置いておき、+ を上に押してから 1 を下にずらして右に移動する。-6870384 で8桁になる。

ステージ109

ヒント1

=(虹) を2方向から使う。

ヒント2

中央の行に =(虹) を置き、左と下に数式を成立させて同じタイミングで x の左側に数字が生成されるようにする。

答え

数式は一例。
上段の x の左に 0-□=□□x を置く。
中央の x の左に 1-0□□□□x を置く。
下段の x の左に 11□x を置く。
=(虹) を中央の 1-0 の下に置く。
=(虹) を下から 1-1- で上に押した後、下段の x の左に数字を押す。
上段と中段の間は2個ぐらいブロックを置いておく。

ステージ110

ヒント

÷ を左下に移動させ、計算式を止める。その途中で小数点を作る。

答え

右に移動し 3 の上まで = を運ぶ。
= を上から押して 1□3 を作る。
÷ を下に押し、= を右に押して 1÷3= を作る。
キャラが上に動いてちょうど 0.3 が生成されるだけのスペースを作り、上に移動する。
÷ を左下まで運び、計算を止める。

ステージ111

ヒント

= 2つで数字を増やして、順番に増える数字を =(虹) で作る。

答え

下段で 1÷1 を作り 1 で埋める。
上段で 01234 の順番に作る。
1+1= と 1÷2= で 2, 5 を作る。
それぞれ 1-1, 1÷1, 1+1, 1+2, 5-1 で作る。
+ を押し込む。

ステージD

ヒント

最短の移動で両方の演算子をどかせるように数式を組む。

答え

- をずらして最短で戻すことで 0 を多めに作る。
右の数式に +0- を縦に並べて下に押し出すことで - を取り出す。
- の下に 0 を置き、更にその下に 0-0=0 で右端の 0 が上の 0 と同じ列になるように置く。
+ の下に 0 を置く。0-0=0 の 0 をどかして右に移動し、最短で + を上にずらす。

ステージE

ヒント

計算結果が 7 になる数式を作り、=(虹) で取り出す。押し出すためのブロックもたくさん必要になる。

答え

1÷-2= でブロックを作る。すべて下に押すため使うので、取り出せる位置で生成する。
==(虹)15- を作り、他のブロックで下まで押し出す。

城別ステージへの行き方

開く

ステージ104'

ヒント

1-2=(虹) を使いまわして 0 をふたつ作る。

答え

左に1マス空きがある位置で、横向きに 1-2=(虹) を作る。
1 を上に押し込む。
右の - をどかして数式全体を右に動かし、- を上に押し込む。
数式を左に動かして 1 を押し込む。あとは 1-1=(虹) になるようにして 0 を作り、0÷0= を作る。

ステージ108'

ヒント

0÷0 を作る。= をうまく使い、2つの数式で 0 が同時に発生するような組み合わせを作る。

答え

-7x2=-14
左上で縦に 1-1 を、横に 7x2-4 を作り、= を押して両方の数式が同時に発生するようにする。
0÷0= を作る。

ステージ110'

ヒント

左下で 1÷3= で水を渡る。

答え

= を先に左下の最下段に運ぶ。水からひとつ離れた位置に置く。
÷ を = と同じ列の上に運び計算を止める。
1÷1 を保ったまま 1 2つを左の列に置き、3 を = の左に置く。
1÷1 の右の 1 を2回ずらして ÷ を 3 の左の列まで移動させる。
1□÷3= を作って水を渡る。
あとは =(虹) をうまく使いまわして 0÷0= を作る。

ステージE'

ヒント

104 とほぼ同じ。

答え

1-2=(虹) で作られた 1 を下に押し込む。
ステージ104 と同じように -, 1 を下に押し出して 0 が虹 = で出てくるようにして、0÷0= を作る。

ステージ111'

ヒント

虹 = の左側で結果が 0 になる数式を作る。

答え

1-1= を作る。
=(虹)1-0 で 1 を一つ作る。
=(虹)0-1 を作り、ブロックをどかして 0 を右側に作る。
0÷0= を作る。

ステージ(名前なし)

答え

ステージ-107 で不定形に右から入り、ステージを出る。青数字の 1 2 が作れる。

中核

開く

ステージ22

答え

右側で ==-1-99 を作り、= を反対側に運ぶ。

ステージ23

答え

水たまりの中で ==□=(虹)9-99 を作る。
1÷3= が一つできたら、- でブロックをどかして数式が反応するように押し出す。

ステージ24

答え

中央の右端で縦に 1+□= を作る。
その下で ÷ の計算が始まる位置で横向きに 1□+5= を置く。

ステージ25

ヒント

0 しかないので、長い式を使って押し出すことはできない。

答え

0x0=(虹)= を右から押して作る。= の下に移動して数式が反応しないようにする。

ステージ26

ヒント

=(虹) は反対側に数字があっても計算が発生する。同時に2つの 1÷3=(虹) を作る。

答え

=(虹)=9x□0-99 を作り、= を押し込む。

ステージ27

ヒント1

☆ がちょうど = の上に来たタイミングで、左下で =1÷3 などの数式ができるように作る。

ヒント2

= を2つ使って虹 = で生成される 4 のラインで、☆ より右側で 4 以外の数字が入るようにする。

ヒント3

4 では数式が起動せず、4 以外の数字で数式が起動するような仕組みを作る。

答え

-99x11= で -1089 を作り数字を増やす。
虹 = で 4 を大量に作られたときに、4 以外の数字が挟まるように数式を組む。
例えば、以下のような数式を 4 のラインの上に作る。これで ☆ より右側に 0 が差し込まれる。

□x8=□
□□□□-
=□□□9
9□□□=
+□□□□

次に左下で 4 では数式が発生せず、それ以外で数式が発生するような数式を組む。例えば、下のような数式を左下に作る。

□□□x
□□□9
□□□=
=1+□
□□□1
□□□1

ステージF

クリアはできているが、仕様がよく分かっていない。

答え

1+1 の上3マスを空けて、0-30==(虹)=□□□3-3 のように配置し、左側の数式を起動する。
おそらく「普通の = の判定」→「=(虹) の判定」を交互に繰り返すようになっているので、1+1 が評価されてすぐに通常 = の計算で押されている?

ステージG

これも仕様がよく分かっていない。

答え

下の形を作る。■ は使用済みの = である。

□□□1□
=1-■■
□□□0■
=1-□1=1-1

この 1 を上から押して =1-1 と =1-01 を同時に作る。
右、下、左と移動する。
おそらく、「移動」→「= の判定」→「=(虹) の判定」→「ブロック生成」の繰り返しになっているせいで 1 が二回でてしまう?

ステージ `!`

答え

+ を右端に移動させたあと -92-7= を作り、上に移動する。

中核別ステージへの行き方

開く

ステージ23'

ヒント1

水たまりの中では移動できないので、不定形は移動できる範囲で作る必要がある。

ヒント2

左の水たまりの中で横向きに 0÷0 を作る。

答え

左の水たまりの中で ÷00= を置く。
その下で ÷ の左下に = を置く（0 を生成したときに 0÷00= となるようにするため）。
下の水たまりで - を縦3、横3 の幅で埋め、その右に縦に 9-9 を置く。
虹 = で 9-9 を左に送り出す。

ステージ24'

ここの仕組みは理解できていない。詳しくは Discord 参照。

-World

開く

ステージ-6

ヒント

循環小数になる数字を右に押し出してから、適当に大きな計算で川をわたる。= の性質を使う。

答え

数字は適当でもいいと思うので一例。
1111x111= を作る。
1321x321= を作る。
川の向こう側に 311= を押し出したあと、同じ行で 42x42= を作り右に移動する。
移動したら 1÷3=1 を作り、1 を下から押し出して移動する。

ステージ-7

答え

右のくぼみに 9x9 を入れる。その左に ☆= を置いて左に押し出す。

ステージ-10

ヒント1

完成形は 99x99□= となる。これを右から押し込みゴールに移動する。

ヒント2

計算結果が生成されるだけのスペースがないとブロックが生成されないことを利用する。

ヒント3

= をそのまま配置すると右の空きスペースに入れない。そこで右の空きスペースに移動した瞬間に = が移動するような配置を作る。

答え

横向きに 99x99 を作る。
右端で上に余白ができるように縦向きに 9x9== を作る。
これを上に押し込み、右の空きスペースに入ると 9x9=81= と = が押し出されるので、これを左に押し込む。

ステージ-18

答え

答えが3桁になるように掛け算を作る。
= は右から押し込む。

ステージ-19

ヒント1

左下の割り算は一桁でなければいけない。

ヒント2

割り算の計算を始めて水たまりに押し出されてゴールするためには、 = 一つで右に移動し、もう一つの = で水の中に最速で入る必要がある。

ヒント3

最初の数式は .4x58=。

答え

.4x58= を作る。
.4 の 4 を使って縦に 4.+5=2 を置く。
水の中を 21÷ にする。
左下で 14x8=3 にする。
3 を下にずらす。

ステージ-20

ヒント

上側に一度渡ってしまうと戻ることができない。戻ってこれるような数式を先に送る必要がある。

答え

ブロック 997= を上側に送ったあと、=9x9 で自分を押し出して上側に渡る。
☆ 4つを縦向きに下に押して送り、9x9= を作って下側に戻る。

ステージ-21

ヒント

ステージの中でステージに入ったとき、ステージを出ると入ったときの向きが保存される。

ステージ-23

答え

ブロックを正方形の領域に運んでおく。
下から 0÷0= を作る。運んだブロックを間に挟んでおく。

ステージ-104

答え

左右どちらかで == を縦に並べて、縦の位置を揃える。

ステージ-107

ヒント1

最終形は、右下にキャラがいる状態で左上で答えが4ブロックになる引き算をしてゴールする。

ヒント2

左下に2キャラがいる状態にしてから、右下にキャラを送る。

答え

= をキャラで挟んで、下に渡る。渡るのは左から4列目。
下側で =-1212= を縦に並べて上に押し出す。
上側で 1-2=1 を 2= のひとつ右の列で作り、1 を左にどかして移動する。
キャラを右に押し出す。
右下で =12÷-- を作り、左に押し出す。
水に入った 2= の列の下で =1÷2 を作り、上に移動する。
1-122= などで4つのブロックを作り右に渡る。このとき使用済みの = も右に移動させる。
移動させた = を使って縦の位置をあわせる。

ステージ-108

答え

1x1 を水たまりの行の右端に置く。= を下に置いておく。
壁をうまく使って、水たまりのすぐ右にキャラクタがいる状態で = を上に押す。

ステージ-110

ヒント

右下のくぼみにキャラを閉じ込めるために数式を使う。

答え

壁をうまく使って、中央下のくぼみにキャラを入れた状態で ☆ を右に押し、上に押し出す。
0+1= でブロックを作り、使用済みの = と 0+11= で右下のくぼみにキャラを入れる。
☆ を列に差し込んで、上に移動させる。

ステージ-111

ヒント

右側の左端で ∞x0= を作る。作った不定形を運び出すために事前にブロックをいくつか置いておく必要がある。

答え

縦向きに 0x1= を作る。
∞ の下に（出てきた不定形をゴールまで運ぶ用）ブロックを置く。
左端の列の下側（生成される不定形を上に押し出す用）の左にブロックを置いておく。
= を右に運んでおく。
右側の左端の列で縦に ∞x0= を作る。

ステージ-A

ヒント1

ステージ-10 と同じように、キャラの移動後に = がうまく動くように調整して配置する。
完成形は aaxaaa= のような5桁の掛け算となる。

ヒント2

縦に 9x9= を2つ作り、掛け算の最後の桁の数字が生成されるようにする。

答え

下の形を作り、左から = を押し込む。

ステージ-C

ヒント1

初期状態ではクリアできない。

ヒント2

右にある ☆ の上から出ることができればクリアできる。

答え

1+1= を作る。左上の縦のくぼみに 1+1=2 を置く。
使い終わった = で ☆ を右に押し込み、右にある 1 を使って ☆ を左に押していき、☆ に上から入る。
ステージを出て、そのまま上から出て ☆ を左に運ぶ。1+11= で数字を増やし、☆ の右のくぼみに 1=1+12 を置く。☆ を縦から押し込み 1 をどかして左に取り出す。

ステージ-D

ヒント

気合。まず上半分をブロックで埋めて、上のキャラクタが移動できないように下の列も埋める。
あとは2人をなるべく離れた位置にして 0-0= で生成されるブロックで押し出させる。

ステージ-E

ヒント

最初に多めのブロックを作っておく。横並びの数式で = を上からずらして上のゴールに移動し、上移動ができないようにブロックを置いておく。

答え

1111+1= でブロックを作る。左上のくぼみに横向きに =1+1=1（一番左の = は使用済み）を置く。
ゴールの列で、上からブロックを7つ詰めて配置する（中身は何でもいい）。
キャラを左上と右下で対角線上に1マス空けて並ぶように調整し、左上のキャラで上から2つ目の 1 を左にずらし、止まるまで下に移動する。
ひとつ上に移動し、左にひとつ移動する。右下のキャラだけ左に動き、1列だけずれるはず。
この列がずれないように、一番下のブロックを左にひとつずらし、右に戻る。
上から2つ目のブロックを左に押して、ブロックの左側に移動して右に押す。ゴールの上に2つブロックが並ぶことになる。
= をずらす。

ステージZ,-Z

ヒント

先に進むためには -World で -Z をクリアする必要がある。
ステージ Z にある -Z に入ると、その中の -Z クリア扱いになるので先にすすめない。

答え

ステージ Z に入り、不定形に入って、-Z に入り、出てからクリアする。

-World 別ステージへの行き方

開く

ステージ-6'

クリアしても特に意味はないが、一応できるので紹介。

答え

数字は適当でもいいと思うので一例。
1111x111= を作る。
13x231= で 0 を2つ作る。
川の向こう側に 00= を押し出して 0÷0= を作る。

ステージ-19'

見つけた解法は3つで、不定形を作る場所が (1) 左側、(2) 中央の水たまり上、(3) 中央の水たまりの外 となっている。ステージZ に行くには (1), 青数字 9 を取るときは (3) でクリアする必要がある。

ヒント(1)

左側で縦に =0x∞ を作る。4 は不要になるので下に押して動かさせる。

答え(1)

8x5= を作る。
0x4= を作る。
左の 4 を下に押し込む。
1÷□=(虹)+5 を置いておき、0 を押し込み ∞ を作る。
=(虹) を使用済みの = で下に押し込み、左で =0x∞ を作る。

ヒント(2)

小数点を使うことで桁を一つ増やせる。

答え(2)

.4x8= を作る。
.4x.2= を作る。
1÷0=(虹) を作り、縦に =.0x∞ を作る。

ヒント(3)

= で2つの式を同時に作り、0 と ∞ を同時に作る。

答え(3)

左で 48x5= を作る。
1÷0=(虹) で ∞ を作っておく。
横向きに 4x5= と縦向きに =2+∞ を同時に作る。
∞ を上に押してから ∞x0= を作り、不定形に左から入る。

ステージ-107'

ヒント1

左上に残ったキャラは最後に = を取り出すときのみ使う。

ヒント2

=0÷0 を作る。下の2つの = で 0 を一回ずつ作りつつ、右・左に移動する。

ヒント3

不定形を作った後のステージに入る向きに注意。

答え

= をキャラで挟んで、下に渡る。
1-21= を作り、右に渡る。このとき 2 も一緒に右に移動させる。
右で ÷1=2-2 を作り、1 を下にずらして左に移動する。
適当にブロックを上に送って、= を取り出して =0÷0 を作る。
右からステージに入ることに注意。

?

ステージタイトル自体に意味があるものがあり、好きです。

開く

青数字 `4` の取り方

答え

2+00= でステージ4 を作る。上から入ってステージを出る。

ステージ-3

答え

2 を右端手前まで押す。
- を右端まで押す。
= を左、下まで押す。
2 を左に、交叉路まで押す。
- を 7 と一マス離して置く。
= を右端まで押す。
2-7= を作る。

ステージ0

答え

左上のスペースを左に押して 0 を取り出す。
ゴールの下にある 0x0 に反応しないように 0 を配置して 0=0x0 の状態で = を上に運ぶ。

ステージ0'

答え

左上のスペースを左に押して 0 を取り出す。
左から5列目で 00÷00-0 を作って = を下に置く。

ステージ-0

青数字 `3` の取り方

答え

左上で 0+1=(虹) を作り、下で =1+2 で青数字3 を作る。

紫記号 `-` の取り方

理屈がわかっていない。 https://discord.com/channels/1387807517983113226/1476542679696281724 を参照。

ステージ-27

答え

1199 を右下の水たまりに詰める。左で 1÷9= を作る。
右上で =9÷91 の準備をし、左側で左右の水たまりにブロックを4つ詰め、1つだけブロックを右の水たまりの横に置いておく。
=9÷91 を作り、上から先程のブロックを下に押す。

ステージ-30

行き方

(-3)0+0= を作る。

答え

上の水たまりで □+0 を作る。
縦に □=4+5+6 を作る。

ステージ10 の行き方

ヒント

-3 はこれ単体で演算として利用できる。

答え

左上で -3 を運ぶように 0 を置いておく。
3 を上に運んでおく。
横向きに (-3)+0= を作り、できた -3 を下に運ぶ。
下で 13□= を作っておき、スペースに -3 を置く。

ステージ100

答え

↑↑↑←←↓

X

たぶん未実装？

青数字の取り方

開く

0 : ステージ19 で取得。
1 : 城ステージのステージ(名前なし)で取得。
2 : 城ステージのステージ(名前なし)で取得。
3 : ステージ-0 で取得。
4 : ステージ? で取得。
9 : Stage Select でステージ-19 の不定形に左から入ってステージを出る。

紫記号の取り方

ステージ-B で今持っているものが確認できる。

開く

+ : ステージ-24 で取得。
- : ステージ-0 で取得。

2025-12-29

2025年今年見たアニメ振り返り

ちょうど1年前ぐらいにAnnict を使い始めた。 Annict は「見たアニメを記録して、共有しよう」を掲げる視聴記録サービスで、何話まで見たか・感想などを残しておける。共有機能はあまり使っていないが、何話まで見たか忘れることが多かったので記録として活用している。

せっかくログが溜まったので、今年観たものの中で印象に残っている作品を(来年の自分用に)雑に振り返る。見たものの一覧はここ： Annict

2クール作品などは除外している。ネタバレは多分ないはず。

以下、箇条書きの順番に意味はない。

全修。

アニメ監督の主人公が、好きな作品の中に転生して、気に入らない結末を全修正していく物語。アニメ技法・制作現場などがネタとして混ざってくるのが面白い。ストーリーも好きで、曇らせがありつつしっかりといいエンディングな作品だった。

沖縄で好きになった子が方言すぎてツラすぎる

方言系アニメ。この手の作品は他にもあるけど、かわいいを詰めてくる感じが強くて良かった。ファイルーズあいが演じるヒロインが意地らしくてかわいい。

空色ユーティリティ

日常系ゴルフアニメ。 Yostar Pictures 作のオリジナルアニメで、クオリティの高さを感じた。絵・テンポ・空気の作り方まで含めて、総合力が高かった。

日々は過ぎれど飯うまし

日常×飯。個人的に P.A.WORKS は、ストーリーをクリティカルにしすぎない日常枠でこそ輝くと思っていて、まさにそれ(永久のユウグレ...)。あっと原案でキャラデザも良い。主人公まこと友人くれあの距離感の縮め方が印象的で良かった。

アポカリプスホテル

ポスト・アポカリプス世界でホテルを営業するアニメ。キャラクター原案に竹本泉さんが関わっていることもあって、キャラの個性が強くて良い。ストーリーもかなり弾けていて、ところどころの倫理観の欠如があるところが面白かった。

忍者と殺し屋のふたりぐらし

こちらも倫理観がない（褒めてる）世界の、殺し屋ふたりの非日常系日常。話のノリが軽いのに、やってることはだいぶエグい。そのギャップがクセになる。あとED の演出が印象的で、回を追うごとに減っていく感じが良い。

宇宙人ムームー

家電を分解して仕組みを理解する（たぶん）教育アニメ。下ネタ要素は多少あるけど、そこを除けばNHKで流れてても違和感ない枠だった。エンディングは大分飛躍した感じはあるが、作品っぽさが出ていて好きではある良い作品。

TO BE HERO X

ヒーローが存在する世界を舞台にしたアクションアニメ。中華アニメならではの 2D・3D の切り替えが印象的だった。ストーリーは複数の思惑が混走・交錯していて理解が結構むずかしいが、続きが気になる作品。

タコピーの原罪

漫画が流行ったのは少し前だけど、これをアニメ化できるのかという驚きがまずあった。しずか役が上田麗奈さんなのが本当に強くて、ファム・ファタール的な演技が素晴らしかった。ストーリーは漫画を読んでいたので知っていたが、それでも鳥肌がたってしまうぐらい良い作品だった。

サイレント・ウィッチ沈黙の魔女の隠しごと

コミュ障な激強魔女が、学園に潜入して護衛対象を守る話。主人公モニカの声が会沢紗弥さんで、コミュ障特有のキョドり方・声の出し方がめちゃくちゃ良い（かわいい）。能力は最強、対人は最弱のため基本は面白枠なんだが、時折見せるかっこよい部分も好き。

わたしが恋人になれるわけないじゃん、ムリムリ!（※ムリじゃなかった!?）

高校デビューした陰キャがスパダリ的存在に告白されちゃって…という百合作品。作画もストーリーも良くれな子の言動も挙動不審で見ていて楽しい。ストーリーは、「れな子が悪いんだよ」に尽きると思う。アニラジでも中の人がめちゃくちゃ責められてて不憫面白い。

ばっどがーる

きらら系作品。キャラがかわいいのはもちろん、ツッコミのキレや語彙力が妙に鋭くて笑う。テンポ良く観られる。

CITY THE ANIMATION

日常アニメ。京アニ制作の安心感で、作画も動きもクオリティが高い。個人的には「日常」のほうが好きだったが、別ベクトルの面白さがあって、これはこれで好き。

銀河特急ミルキー☆サブウェイ

短編とは思えないほど小気味よいストーリー。会話の自然さが良くて、声優の芝居がキャラ同士の距離感をちゃんと作っていた。短い尺でお手軽なのも良い。

グノーシア

ゲーム原作のアニメ。人狼を繰り返しながら、ループの中でキャラの背景や行動の理由が分かっていく、ループものとはまたちょっと異なる作品。アニメオリジナル主人公のユーリがうまく馴染んでいて、原作の空気を壊さずに、アニメの流れにしてる感じが良かった。ゲームの方のイベントを忠実に再現していて、好感触。 (今後あると思われる)水そうめんイベントが楽しみ。

2019-08-10

Codechef Cook 101 Editorial

CodeChef

Codechef Cook 101 で自分が解いた部分までの解説です (Div2 の4問目、Div1の3問目まで)。

各問題にはテストケース数 $T$ の制約があるけど省略しています。

Camp Or Not

概要

競プロキャンプに向けて問題を解く。問題を解くスケジュールは $D \leq 31$ 日決まっていて、 $d _ i$ 日目に $p _ i$ 問を解く予定である ( $1 \leq i \leq D, d _ i \leq 31, p _ i \leq 100$ )。

キャンプの選抜方法の候補は $Q \leq 100$ 個あり、各候補には締め切り $dead _ i$ と必要問題数 $req _ i$ が与えられている。 $dead _ i$ 日目を含むその日までに $req _ i$ 問以上解いていれば、キャンプに行くことができる。

スケジュール通りしたときに、各候補日についてキャンプに行けるかどうかを判定せよ。

解法

制約が小さいので愚直にやってもよいし、累積和を計算してもよい。

提出コード : Solution: 25750755 | CodeChef

Yalalovichik Numbers

概要

10進数で桁数が $D$ の数 $N$ が与えられる ( $D \leq 10 ^ 5$ , $N$ の各桁は0でない)。この数を $i$ 回左に回した数を $L _ i$ とする (例えば $N=123$ のとき、 $L _ 0 = 123, L _ 1 = 231, L _ 2 = 312$ )。

このとき $L _ 0, L _ 1, \ldots L _ {D-1}$ の順で結合した数を $M=10 ^ 9+7$ で割った余りを求めよ ( $N=123$ なら 123231312 が答え)。

解法

答えは

$(L _ 0 * 10 ^ {(D-1)D} + L _ 1 * 10 ^ {(D-2)D} + \ldots + L _ {D-1} * 10 ^ {0 \cdot D}) \bmod M$

となる。10のベキの方は簡単に計算できるため $x _ i := L _ i \bmod M$ が分かれば良い。

まず $x _ 0 = N \mod M$ はそのまま計算できる。次に $x _ {i+1}$ については、 $x _ i$ の先頭の桁を $d _ i$ とすると $x _ {i+1} = (x _ i * 10 - d _ i * 10 ^ D + d _ i) \bmod M$ という関係が成り立つので、 $d _ i$ さえ分かれば $i=0,1,2,\ldots$ と順に求めることができる。

今、 $N$ を順番に左に回しているので $d _ i$ は $N$ の $i$ 桁目である。 $N$ は文字列として与えられているので $d _ i$ はすぐに求められる。

提出コード : Solution: 25751450 | CodeChef

Yalalovichik Strings

概要

文字列 $T$ のすべての部分文字列(連続)の集合と $T$ のすべての部分列(連続とは限らない)の集合が一致するとき、文字列 $T$ は Yalalovichik string であるという。

長さ $N$ の文字列 $S$ が与えられる ( $N \leq 10 ^ 6$ )。 $S$ の空でない部分文字列のうち Yalalovichik string であるものの個数を求めよ。

解法

どのような文字列が Yalalovichik string になるかを考える (以降、省略してY文字列と呼ぶ)。

まず1種類の文字が続く場合 (aaaaaa など) は明らかにY文字列になる。そして文字列が2種類の連からなるとき (aaaabb など) もY文字列になる (どのように部分列をとっても a*b* の形になるため)。

逆に文字列が3種類以上の連からなるときはY文字列になることができない。 $S$ が $S = c _ 0 \ldots c _ 0 c _ 1 \ldots c _ 1 c _ 2 \ldots$ と3つ以上の連からできているとする。このとき部分列として $c _ 0 \ldots c _ 0 c _ 2 \ldots$ を選ぶと、これは $S$ からどのように部分文字列を選んでも一致させることができないからである。

このことから $S$ の部分文字列のうち

aaa... のように1種類の文字からなる文字列
a...ab...b のように2種類の連からなる文字列

のどちらかの形をした部分文字列の総数が答えになる。重複を考慮して数えなければならないが、1 と 2 は独立に考えることができる。

(1) はアルファベット $\alpha$ ごとに $S$ 中の $\alpha$ の最長の長さ $l _ \alpha$ をもっておけば、その総数は $\sum _ {\alpha \in {a,b,\ldots,z}} l _ {\alpha}$ になる。

(2) は2種類のアルファベット $\alpha, \beta (\alpha \neq \beta)$ とそれぞれの長さだけが重要になる。そのためすべてのアルファベットの対ごとに、 $S$ 中で取りうるすべての長さの組の集合 $P _ {\alpha, \beta}$ を計算する。例えば aaabb と aabbb の2種類の部分文字列が $S$ に現れるとき、 $P _ {a,b} = \{(3,2), (2,3)\}$ となる。

$f(P _ {\alpha, \beta})$ を $\alpha, \beta$ をこの順に少なくとも1つずつ使って作れる文字列の個数としよう。上の例だと $f (P _ {a,b}) = |\{ab, abb, abbb, aab, aabb, aabbb, aaab, aaabb\}| = 8$ になる。

基本的には各 $(x,y) \in P _ {\alpha, \beta}$ について $x*y$ の和を取ればよいが、これだと重複を数えてしまうことがある　(上の例だと ab, abb, aab, aabb の4種類)。この問題は2次元平面上に点 $(x, y)$ がいくつか与えられ、各点ごとに点と原点を隅に持つ長方形を描いたときの面積の総和を求めることと等価である。これはそれぞれの点 $(x,y)$ をx座標でソートして、x座標が小さい方から順に点を見ていくことで計算できる。

異なる $\alpha, \beta$ は独立に計算できるため、求める総数は $\sum _ {\alpha,\beta \in {a,b,\ldots,z}, \alpha \neq \beta} f(P _ {\alpha, \beta})$ である。

計算量はソートの部分が一番重くて $O(N \log N)$ である (アルファベットの個数は定数個なので)。

実装は $S$ を最初にランレングス符号化しておくと簡単になる (気がする)。

提出コード : Solution: 25753643 | CodeChef

Swag Subsets

概要

長さ $N$ の数列 $A _ 1, A _ 2, \ldots, A _ N$ と $B _ 1, B _ 2, \ldots, B _ N$ が与えられる。

集合 ${1,2,\ldots,N}$ の空でない部分集合 $S$ について、その swagness $v _ s$ を以下のように定める。

$v _ S = (\max _ {p \in S}{A _ p})(\max _ {p \in S}{B _ p})$

このとき $X = \sum _ {S \subseteq \{1,2,\ldots,N\}, S \not=\emptyset}{v _ s}$ を $10 ^ 9+7$ で割った余りを求めよ。

解法

簡単のために $A _ i, B _ i$ はすべて相異なるとする。

まず B を無視した問題 $v _ s = \max _ {p \in S}{A _ p}$ の総和を求めることを考える。数列 $A$ の順序に意味はないのでソートして $A _ 1 \lt \cdots \lt A _ N$ と仮定してもよい。

このとき $v _ S = A _ N$ となる $S$ は $2 ^ {N-1}$ 個ある ( $N$ を取ればそれ以外は取っても取らなくても良いので)。同様に $v _ S = A _ {N-1}$ となる $S$ のとり方は $2 ^ {N-2}$ 通りある ( $N$ は取らず $N-1$ は取る、それ以外はどちらでもよい)。

これは $v _ S = A _ 1$ となるまで同じように考えることができるので、答えは

$X = 2 ^ 0 A _ 1 + 2 ^ 1 A _ 2 + \cdots + 2 ^ {N-1} A _ N$

である。

もとの問題も今の考え方と同じようにする。まず $A _ i, B _ i$ のペアを $A _ i$ をキーでソートして $A _ 1 \lt \cdots \lt A _ N$ にする。 $B$ についてはソートされているとは限らない。

また、 $B$ の値だけでソートした列を $B' _ 1 \lt \cdots \lt B' _ N$ とする。

$A _ N = \max _ {p \in S}{A _ p}$ となる $S$ のとり方は、 $N$ を取りそれ以外はどちらでもよいので $2 ^ {N-1}$ 通りある。また $B _ N$ をすでに選んでいるので $B _ N \leq \max _ {p \in S}{B _ p}$ が成り立つ。それらのうち

$B _ N \lt \max _ {p \in S}{B _ p}$
$B _ N = \max _ {p \in S}{B _ p}$

で場合分けする。

また $k$ を

$B' _ 1 < \cdots < B' _ {k-1} < B' _ k = B _ N < B' _ {k+1} < \cdots < B' _ N$

となる数とする。

ある集合 $S$ について(1) が成り立つ条件は $B' _ k$ よりも右側にある数に対応する添字を取るときである。 $B' _ l$ を $B' _ k$ より右にあるものとして、 $B' _ {l} = \max _ {p \in S}{B _ p}$ となる場合を考える。これは $l$ より右にあるものは取らず、 $l$ (とすでに選んでいる $N$ )を選び、それ以外はどちらでもよい取り方になるので、 $S$ の選び方は $2 ^ {l - 2}$ 通りある。

つまり任意の $k \lt l \leq N$ について $B' _ {l} = \max _ {p \in S}{B _ p}$ となる $S$ の取り方は $2 ^ {l-2}$ 通りある。よって (1)の場合の求める数は $A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N})$ である。

(2) が起きるのは $k$ より右側はすべて取らず、左側はどちらでもよい取り方になるので、 $2 ^ {k-1}$ 通りある。よって求める数は $A _ N * B' _ k * 2 ^ {k-1}$ となる。

以上から $A _ N = \max _ {p \in S}{A _ p}$ となるときの答えは (1), (2) を合わせて

$A _ N * (2 ^ {k-1} B' _ {k+1} + 2 ^ {k} B' _ {k+2} + \cdots + 2 ^ {N-2} B' _ {N}) + A _ N * B' _ k * 2 ^ {k-1}$

である。

次に $A _ {N-1} = \max _ {p \in S}{A _ p}$ となる場合を計算したい。これは $B'$ の列から $B' _ k$ を削除してから、同じ方法で計算することができる。

以上より $X$ の計算方法は分かった。あとはこれを高速に計算できるように実装する必要がある。数列 $B' _ 1, \ldots, B' _ N$ に対して、上で必要になる操作は

与えられた区間 $[l,r)$ について $2 ^ 0 B' _ l + 2 ^ 1 B' _ {l+1} + \cdots 2 ^ {r-l-1} B' _ {r-1}$ を求める (上の計算式と少し違うが、全体に $2 ^ {何か}$ を掛けて調整できるためok)
要素の削除

の2種類。しかし(2) の要素の削除を考えると面倒なので、 $B' _ i$ が0 となる部分は無視するように (1) の計算方法を下のように変える。これで(2)の処理も簡単になる。

与えられた区間 $[l,r)$ の $B' _ l, B' _ {l+1}, \ldots B' _ {r-1}$ のうち、非0 の要素を集めたものを $B'' _ 0, B'' _ 1, \ldots B'' _ k$ として $2 ^ 0 B'' _ 0 + 2 ^ 1 B'' _ {1} + \cdots + 2 ^ {k} B'' _ {k}$ を求める
$B' _ i = 0$ にする。

(1)の計算は次のように言い換えられる。要素 $e _ i = (x _ i, c _ i):= (B' _ i, B' _ i \neq 0\ ?\ 1 : 0)$ とし、その上の演算 ${\circ}$ を $e _ i \circ e _ j := (B' _ i + 2 ^ {c _ i} B' _ j, c _ i + c _ j)$ で定める。このとき(1)の計算は $e _ l \circ e _ {l+1} \circ \cdots \circ e _ {r-1}$ の第一成分と一致する。

この演算はモノイドになっている(単位元は $(0,0)$ ) のでセグメント木が使える。この演算は $2 ^ i$ を前計算することで $O(1)$ で計算できるので、(1)は $O(\log N)$ で計算することができる。

これを $B _ N, B _ {N-1}, \ldots, B _ 1$ と順番に処理していけば良いので全体の計算量は $O(N \log N)$ である。

また、 $A _ i, B _ i$ はすべて相異なるとしていたが、上の計算方法では重複した要素があっても問題なく計算できる。

提出コード : Solution: 25832307 | CodeChef

2019-04-27

CodeChef Cook100 Editorial

CodeChef

CodeChef Cook100で解いた問題の解説です(div2の4問目、div1の3問目まで)。

Truth and Dare

Contest Page | CodeChef

概要

集合 $T_r, D_r, T_s, D_s$ が与えられる。 $T_s \subseteq T_r$ かつ $D_s \subseteq D_r$ のとき "yes"と、そうでないとき"no"と答えよ。

解法

set<int> で集合を管理して愚直に部分集合になっているか調べる。制約が小さいのでvectorでも十分。

ソースコード: Solution: 24027534 | CodeChef

英語がとても読みづらい(というか未だに詳細を理解していない)。

Beautiful Garland

Contest Page | CodeChef

概要

R,Gの2種類からなる文字列s ( $2 \leq |s| \leq 10^5$ ) が与えられる。このsは先頭と最後がつながった一つの輪と考える。この輪に対して以下の操作が高々1回できる。

輪を2つの文字列s1, s2に分解する。そしてs2を前後反転させてから再度s1とつなぐ。

この輪をRとGが交互に現れるようにできるか。

解法

まずRとGの数が同じでないとどうやっても交互にはできない。

次にRとGの数が同じときを考える。この操作は同じ箇所に対して2回行うともとに戻ることがわかる。そのためこの操作でsをRとGが交互になるようにできたならば、sはRとGが交互になっている文字列から操作を1回だけして作ることができる。逆も同じ。

そのため、 sをR, Gが交互になっている文字列から操作を1回だけして作ることができるか分かれば良い。

両端が同じ文字の位置で反転させると変化しない。そうでないなら部分文字列"RR", "GG"がちょうど一回ずつ現れる形になる。

以上からsの中のR,Gの数が同じであり、かつsがすでにRとGが交互になっている or 部分文字列"RR", "GG"がちょうど一回ずつ現れるときに"yes"、そうでないなら"no"である。

ソースコード: Solution: 24027634 | CodeChef

A-B Game

Contest Page | CodeChef

概要

A, Bの二人でゲームをする。このゲームは長さ $N \leq 10^5$ の一直線上に並んだマスの上で行われる。各マスにはAのコマかBのコマが置かれているか何も置かれていないかのいずれかである。プレイヤーAはAのコマを、プレイヤーBはBのコマを動かすことができる。動かすことができるのは駒があるマスから移動する先のマスまでに何もないときに限る。つまり、すでに置かれているコマを飛び越すことはできない。

またコマごとに動かすことができる方向が事前に決まっており、マスの左端から順番に右方向、左方向、右方向、･･･である。これはゲームの間変わることはない。

マスの初期状態が文字列sとして与えられ、ゲームはAの手番から始まる。このときAが勝つかBが勝つか答えよ。

　解法

大体のゲーム問題はNimに帰着できるのでNimにならないか考える。

まずコマを動かすことができる方向が右･左と交互になり、またコマを飛び越えて動かすことはできないので、コマを左から2個ずつのペアにするとそれぞれ個別の独立したゲームが複数あるとみなすことができる (ただし奇数個あるときは別に考える必要がある)。

例えばs="A..B.A....B.BB"のときは次の3つの独立したゲームとみなせる:A..B, A...B, BB

ここで1つのペアに着目する。ペアにある空きマスの個数をLとする。個別のゲームには次の2種類のパターンがある。

両端が同じ文字のとき:　これはNimではコマを動かすことができるプレイヤーだけが自由に取り除くことができる石の山とみなせる。石の個数はLである。
両端が違うとき:　どちらのプレイヤーも自分のコマを動かすことで任意の $L' \lt L$ について空きマスが $L'$ 個である状態に持っていける。これはNimでは石の数がL個ある山と同じ性質をもち、Nimとみなせる。

これらからこのゲーム全体は次のようなゲームに言い換えられる:

プレイヤーA,Bのどちらも自由に取ることができる石山(普通のNim)、プレイヤーAだけが石を取り除ける山、プレイヤーBだけが石を取り除ける山の3種類があるNimの亜種

このゲームの戦略としては、普通のNimでゲームを行い、何もできない状態になったら自分専用の山から石を1つずつ取り除くのが最善である。

普通のNimの石山はAが勝つならばA専用の1つの石、Bが勝つならば無とみなせるので、 A,B専用の石の山の数の大小のみでゲームの勝敗を決められる。

最後にコマの数が奇数のときは右端のコマ専用の石の山とみなせばよい(この処理をしていなくて1WA)。

ソースコード: Solution: 24042766 | CodeChef

Tree Unattractiveness

Contest Page | CodeChef

概要

$N \leq 100$ 頂点からなる木Tと $\{0,1,2\}$ のうちいずれかの数字が書かれた $N$ 個のマーカーがある。これらのマーカーを各頂点にちょうど一つずつ置いていく。頂点 $v$ に置かれたマーカーの数字を $n_v$ とする。

このときあるマーカーの置き方に対してそのスコアは $\max\{|n_u - n_v| \mid 頂点u, vは木T 上で隣接している\}$ で定められる。マーカーを適当においたときに得られるスコアの最小値を求めよ。

解答

ありうるスコアは0,1,2のいずれかであり、0かどうかはすぐ分かる (すべてのマーカーか同じときに限る)。そのため1が作れるかどうかを判定すればいい。

スコアが1になるように置くためには、マーカー0と隣接するのは0か1、マーカー2と隣接するのは2か1でなければならない。また1は何と隣接しても良い。

このことから、木に置いた1のマーカーがある頂点で木を分断すると、分断されたあとの各連結成分に置かれるマーカーはすべて0か2になっていなければならない。

この性質から根を適当に決めて木dpができる。パラメータは今の頂点に何を置いたか、部分木で0,1を使った個数となる (2を何個使ったかは部分木のサイズから計算できる)。ただし愚直に"dp[頂点][置いたマーカー][0の数][1の数]=スコア1が作れる/作れない"というtrue/false としてしまうと計算量的に間に合わない。

ここから次元を減らすことを考える。上で説明したように1は何と隣接しても良いためできるだけ使わないほうが良いと直観的に分かる。そこでdp[頂点][置いたマーカー][0の数]="スコア1にするために必要な1のマーカーの個数の最小値"としても正しく計算できる。

このとき遷移は頂点 $v$ の子を $c_1, c_2, \ldots, c_n$ としたとき

$dp[v][1][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots + dp[c _ n][m' _ n][z _ n] + 1$

ただし、 $1 \leq k \leq n$ に対して $m' _ k \in \{0,1,2\}, z _ 1 + \cdots + z _ n = z$
$dp[v][0][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots + dp[c _ n][m' _ n][z _ n]$

ただし、 $1 \leq k \leq n$ に対して $m' _ k \in \{0,1\}, z _ 1 + \cdots + z _ n + 1 = z$
$dp[v][2][z] = dp[c _ 1][m' _ 1][z _ 1] + \cdots + dp[c _ n][m' _ n][z _ n]$

ただし、 $1 \leq k \leq n$ に対して $m' _ k \in \{1,2\}, z _ 1 + \cdots + z _ n = z$

このdpの計算量は一見 $O(N ^ 4)$ に見えるが、二乗の木dpの形なので(参考リンク: https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594) $O(N ^ 3)$ になる。

ソースコード: Solution: 24095010 | CodeChef

2018-07-22

AtCoderのコンテストカレンダーを作った

この前AtCoderで非公式コンテストがあったけれども、メールはないし公式のカレンダーにも載ってなかったので危うく出損ねるという事案があった。非公式だししょうがないかなぁというのもあるけどやっぱりカレンダーは欲しいので自前で作った。

GitHub - okaduki/AtCoderAllContestCalendar

AtCoderのホームページの｢予定されたコンテスト｣にある項目を取ってきて突っ込んでるだけ。いくつか問題点としては

コンテスト名をキーにしている → 後から時間などが変わったりしても反映されない
終了時間は適当に設定している → ページには開始時刻しかないため

気になったらそのうち直す。

2018-02-23

ABC020 D LCM Rush

Atcoder

問題

D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder

$1 \leq N,K \leq 10^9$ が与えられるので $\sum_{i=1}^{N}\mathrm{lcm}(i,K)$ を計算せよ。

解法

$\displaystyle \begin{align} \sum_{i=1}^{N}\mathrm{lcm}(i,K) &= \sum_{i=1}^{N}\frac{i*K}{\gcd(i,K)}\\ &= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq i \leq N\\\gcd(i,K)=g}}i\\ &= \sum_{g \mid K} \frac{K}{g} \sum_{\substack{1 \leq gi \leq N\\\gcd(gi,K)=g}}gi\\ &= K\sum_{g \mid K}\sum_{\substack{1 \leq i \leq N/g\\\gcd(i,K/g)=1}}i \end{align}$

となるので後は $K$ の約数 $g$ ごとに $N' = N/g, K' = K/g$ として

$\displaystyle \sum_{\substack{1 \leq i \leq N'\\\gcd(i,K')=1}}i$

が計算できればいい。

式変形が何をしているかと最後の総和の計算は解説 Editorial - AtCoder Beginner Contest 020 | AtCoder にあるので省略。

2017-12-24

Game Theory (HackerRank)

HackerRank

この記事は解説 Advent Calendar 2017の24日目の記事です。

adventar.org

以下のコンテストの解説です。 www.hackerrank.com

はじめに

競プロ!!Advent Calendarのこの記事 (競プロにおけるNim、Grundy数とNimK - かっさのなにか)に触発されて書きました(というか解いてないことを思い出した)。

以下ではNim, grundy数などの知識を前提としています。全く知識がない、あるいは不安な方は上の記事を読んでから解く and/or 解説を読むことを推奨します。またxorを $\oplus$ で表します。特に記述がなければ、先手(プレイヤー1)と後手(プレイヤー2)が交互に手を打つゲームとし、どちらのプレイヤーが勝つか出力する問題と思ってください。

Game of Stones

概要

Programming Problems and Competitions :: HackerRank

山に石が $N$ 個ある。プレイヤーは山から $2,3,5$ 個いずれかだけ取り除ける。取り除くことができなくなったプレイヤーの負けである。

解法

メモ化再帰。

Tower Breakers

概要

Programming Problems and Competitions :: HackerRank

それぞれに石が $M$ 個ある山が $N$ 山ある。プレイヤーは一つの山に石が $X$ 個あるとき、 $Y$ 個に減らすことができる。ただし $Y$ は $X$ を割り切れなければならない。

解法

$M=1$ のときは明らかに後手勝ち。 $M>1$ とする。 $N$ が偶数ならば後手は先手と全く同じように操作ができるから後手勝ち。 $N$ が奇数ならば先手が最初に $1$ つの山を $1$ にすれば、上と同じ戦略が取れるから先手勝ち。

A Chessboard Game

概要

Programming Problems and Competitions :: HackerRank

$15\times 15$ のチェス盤に石が $1$ つ置いてある。プレイヤーは $(x,y)$ にある石 $1$ つを $(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)$ のいずれかに移動させる。ただし盤面外に移動させることはできない。手を打つことができなったプレイヤーの負けである。

解法

メモ化再帰。

Nim Game

普通のNimなので略。

Misère Nim

概要

Programming Problems and Competitions :: HackerRank

$N$ 山のNimをする。ただし普通のNimと違うところは最後に石を取った人が負け (手が打てなくなったプレイヤーが勝ち) という点である。

解法

まずすべての山が1個の石からなるケースを考える。このときは山の数が偶数なら先手勝ち、奇数なら後手勝ちである。

それ以外のとき、 $S$ を(普通のNimと同じように)すべての山の石の個数の xorをとったものして $S = 0$ のとき、かつそのときに限り、後手勝ちであることを示す。

今、先手番で $S = 0$ とし、先手が手を打つことでこれが $S' \not= 0$ になったとする。

このとき、後手番ですべての山の石が $1$ となることは無いことが分かる。もしそうなったとすると、仮定から先手が選んだ山以外の石の数はすべて $1$ であり、先手が選んだ山はもともと $1$ 個より多くの石があったことが分かる。しかしこのような状況は $S=0$ の下では明らかに起こりえない。

これより、後手番では少なくとも $1$ つの山は $1$ 個より多い石がある。石が $1$ 個より多い山がちょうど $1$ つあるときは、その山を $0$ か $1$ に減らすことで、山の数が奇数となるようにすべての山を $1$ にすることができるので後手が勝つ。そのような山が $1$ つより多くあると、次の先手番ではすべての山が1個の石からなることはない。従って通常のNimと同じようにして $S'' = 0$ となるように後手は手を打つことができ、帰納的に後手勝ちであることがわかる。

逆に先手番で $S \not= 0$ とすると、上の後手番の議論をそのまま適用できるので先手勝ちである。

よってすべての山が $1$ 個の石である場合を例外扱いすることで、普通のNimと同じように解ける。

解説だと全部 $1$ のときだけ場合分けすればいいとしか書いてないし、それが正しそうな理由もよく分からなかった。自分は実験してなんとなく規則性を見つけて適当に投げた。実験せずに気付けるかと言われると微妙。

Nimble Game

概要

Programming Problems and Competitions :: HackerRank

$N$ 個の箱が一列に並んでいて、 $0,1,2,\dots$ と番号が付いている。各箱には石が $c_i$ 個入っており、プレイヤーは $i$ 番目の箱にある石 $1$ つを箱 $j \lt i$ に移すことができる。先に手を打つことができなくなったプレイヤーの負けである。

解法

位置 $i$ にある石はそれより小さい $j \lt i$ のどこへでも動かせる。これはNimの $1$ つの山にある石の個数が $i$ 個であるときの状況とちょうど対応している。よって $S = \displaystyle\bigoplus_{c_i \bmod 2 = 1}{i}$ が $0$ なら後手勝ちである。

Poker Nim

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $c_i$ 個石がある。プレイヤーは各ターンで $1$ つの山から $1$ 個以上の石を取り除くか、あるいは追加することができる。ただし、石を追加できる回数は各プレイヤー、各山に対して高々 $K$ 回までである(個数は任意)。最後の石を取り除いたほうが勝ちである。

解法

石を追加しないNimと全く同じ結果になる。つまり、 $S = \bigoplus_i c_i = 0$ のとき、かつそのときに限り、後手必勝となる。 $S=0$ のときは先手が石を取り除こうが追加しようが、後手は先手と同じことをすればNim和は $0$ になる。また石の追加は高々 $K$ 回までしかできず、必ず有限回で終わるので後手必勝。

$S \not= 0$ のときは適当に石を取り除いて $S = 0$ の状態に持っていけるので先手必勝である。

Tower Breakers, Revisited!

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $h_i$ 個石がある。プレイヤーは $1$ つの山にある $X$ 個の石を $Y \lt X$ まで減らすことができる。ただし $Y \geq 1$ は $X$ の約数でなければならない。最後の石を取り除いたほうが勝ちである。

解法

山が $1$ つで $x$ 個石があるとする。このときのgrundy数がどうなるか考える。 $x$ のある約数 $d$ のgrundy数を $g_d$ とすると、 $d$ の任意の約数 $d'$ にも $x$ から遷移できるので、 $x$ のgrundy数 $g_x$ は少なくとも $g_d + 1$ 以上である。これを $x$ のすべての約数にわたって考えれば $g_x = \displaystyle \max_{d \nmid x}{(g_d+1)}$ となる。

よくよく考えるとこれは $x$ の重複を含めた素因数の個数(例えば $x = 2^2\times3^1$ なら $2+1=3$ )と一致することがわかる (素因数 $p$ で $x$ を割ったものならどれでも最大になるため) ので、各 $h_i$ のこれを調べて最後にそれらのNim和をとればよい。

Tower Breakers, Again!

概要

Programming Problems and Competitions :: HackerRank

$N$ 山にそれぞれ $h_i$ 個石がある。プレイヤーは $1$ つの山にある $X$ 個の石を、 $Z$ 個の石からなる $Y$ 個の山に分けることができる。ただし $Y > 1, Y \times Z = X$ でなければならない。最後の石を取り除いたほうが勝ちである。

解法

基本的に $1$ つ前の問題と同じで重複を含めた素因数の個数がgrundy数となる。ただし $2$ を素因数にもつときは一度だけしか数えない( $2^i$ のグランディ数が $1$ となるから)。

Chessboard Game, Again!

概要

Programming Problems and Competitions :: HackerRank

$15\times 15$ のチェス盤にいくつか石が置いてある。 $1$ つのマスに石が複数置いてあっても良い。プレイヤーは $(x,y)$ にある石 $1$ つを $(x-2,y+1), (x-2,y-1), (x+1,y-2), (x-1,y-2)$ のいずれかに移動させる。ただし盤面外に移動させることはできない。手を打つことができなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。盤面が $15 \times 15$ で、ありうる遷移が高々 $4$ なので愚直に計算しても十分に間に合う。位置 $(x,y)$ から動かせる手 $(x',y')$ について $x+y > x'+y'$ が成り立つから、 $x+y$ が小さいものから順に計算することができる。

Digits Square Board

概要

Programming Problems and Competitions :: HackerRank

$N \times N$ のマスに整数 $x (1 \leq x \leq 9)$ が書かれている。プレイヤーは盤面の面積が $1$ より大きく、かつ素数でないような数字が少なくとも $1$ つ書かれているとき、盤面を水平方向か垂直方向に $2$ つに分割することができる。手を打つことができなくなったプレイヤーの負けである。

解法

素直にgrundy数を計算すれば良い。 $dp(x_1,y_1,x_2,y_2) = \text{｢元の盤面の部分長方形で左上が}(x_1,y_1)\text{で右下が}(x_2,y_2)\text{のgrundy数｣}$ でメモ化再帰する。素数でないものが部分長方形に入っているかを累積和で前計算しておけば、盤面が分割できるかどうかは $\mathcal{O}(1)$ で判定できる。上の状態が $\mathcal{O}(N^4)$ あり、各状態からの分割方法は $\mathcal{O}(N)$ あるので、全体で $\mathcal{O}(N^5)$ で計算できる。

Fun Game

概要

Programming Problems and Competitions :: HackerRank

長さ $N$ の $2$ つの数列 $A=(a_1,\dots), B=(b_1,\dots)$ がある。プレイヤー $1$ は $A$ から、プレイヤー $2$ は $B$ から交互に数字を選んでいく。ただし $a_i$ がすでに選ばれていたら $b_i$ を選ぶことができず逆も同様。なのでちょうど $N$ 回の操作でゲームは終わる。

各プレイヤーが選んだ数の総和を計算し、大きい方が勝ち、同じなら引き分けである。

解法

この手の $2$ つの数列から片方を選ぶみたいな問題は適当な評価値を決めて、大きい方から選んだりdpしたりすることが多い気がするのでそうする。

このゲームは次のようなゲームに置き換えられる。

プレイヤー $1$ は初期点として $\sum_i{a_i}$ を持っている。
数列 $C = (a_1+b_1, \dots)$ がある。
プレイヤー $1$ は $C$ から数字を一つ消すことができ、プレイヤー $2$ は選んだ数だけプレイヤー $1$ の点数を減らせる。
最後にプレイヤー $1$ の点数が正ならばプレイヤー $1$ の勝ち、 $0$ なら引き分け、負ならプレイヤー $2$ の勝ち。

なので $C$ を計算、ソートして、数字が大きいものから順番に消す、点数を減らすことを交互にすればよい。

Powers Game

概要

Programming Problems and Competitions :: HackerRank

文字列 $\heartsuit 2^1 \heartsuit 2^2 \heartsuit \dots \heartsuit 2^n$ がある。プレイヤーは交互に $\heartsuit$ を $+$ か $-$ のどちらかに $1$ つずつ書き換える。最後にすべての $\heartsuit$ が無くなったら数式を計算し、 $17$ で割りきれたら後手勝ち、そうでなければ先手勝ち。

解法

$x_i = 2^i \bmod 17$ だけを気にすればいいから、現れる数字は実質 $0 \leq x_i \lt 17$ だけとみなせる。また、 $x_i = x_j (i \not= j)$ なるものがあれば、お互いに打ち消すように手を指すことができる (片方が $+$ に書き換えたらもう片方は $-$ に変える)ので、奇数個あるものだけ着目すれば良い。

あとは $dp(i,r,B) = \text{｢プレイヤー}i\text{が今までの和が}r\text{であり、残り使える集合が}B\text{から始めるときに勝てるか｣}$ のように $B$ をbitとして使いメモ化再帰で解ける。 $n \leq 10^6$ なので $n=1$ から順番に前計算しておけば良い。

Deforestation

Programming Problems and Competitions :: HackerRank

既出。同じ問題がhttps://beta.atcoder.jp/contests/agc017/tasks/agc017_dにある。ハッケンブッシュ(Hackenbush)というゲームがあってそれの特殊な形である。

Tower Breakers - The Final Battle

概要

Programming Problems and Competitions :: HackerRank

$N$ 個の石がある。 $N=1$ となるまでプレイヤーは以下の操作を交互にする。

プレイヤー $1$ は $N = n_1 + n_2 + \dots + n_k,\; k \geq 2$ となるように自由に石を分割する。
プレイヤー $2$ はこの中から $i$ 番目の山を選び、 $N = x_i$ としてゲームを続ける。このときコイン $i^2$ 枚を得る。

プレイヤー $1$ はプレイヤー $2$ が得られるコインの枚数を最小化、プレイヤー $2$ は最大化しようとする。このとき最終的に得られるコインの枚数はいくらか。

解法

小さいケースで実験すると $N$ がある程度大きくなっても答えは大きくならないと予想ができる。

そこで $f(m) = \text{｢答えがmとなるような最大のN｣}$ とする。明らかに $f$ は単調増加になるから、 $f(m) \leq N$ となるような最大の $m$ が求める答えである。 $i$ 番目の山を選ぶとコインを $i^2$ 払うことになるから、 $f(m) = \displaystyle\sum_{m-i^2\geq 0}{f(m-i^2)}$ となる。 $m=121$ で $f(m) \gt 10^{18}$ となるから愚直に計算しても実行時間は十分間に合う。

はじめに

注意

記法について

Stage Select

ステージ1〜3

ステージ4

ステージ5

ステージ6

ステージ7

ステージ8

ステージ9

ステージ10

ステージ11

ステージ12

ステージ13

ステージ14

ステージ15

ステージ16

ステージ17

ステージ18

ステージ20

ステージ21

ステージA

ステージB

ステージC

Stage Select 別ステージへの行き方

ステージ16'

ステージ18'

ステージ20'

ステージ21'

城

ステージ101

ステージ102

ステージ103

ステージ104

ステージ105

ステージ106

ステージ107

ステージ108

ステージ109

ステージ110

ステージ111

ステージD

ステージE

城 別ステージへの行き方

ステージ104'

ステージ108'

ステージ110'

ステージE'

ステージ111'

ステージ(名前なし)

中核

ステージ22

ステージ23

ステージ24

ステージ25

ステージ26

ステージ27

ステージF

ステージG

ステージ !

中核 別ステージへの行き方

ステージ23'

ステージ24'

-World

ステージ-6

ステージ-7

ステージ-10

ステージ-18

ステージ-19

ステージ-20

ステージ-21

ステージ-23

ステージ-104

ステージ-107

ステージ-108

ステージ-110

ステージ-111

ステージ-A

ステージ-C

城別ステージへの行き方

ステージ `!`

中核別ステージへの行き方

青数字 `4` の取り方

青数字 `3` の取り方

紫記号 `-` の取り方

サイレント・ウィッチ沈黙の魔女の隠しごと

銀河特急ミルキー☆サブウェイ

　解法