反転する盤面
鈴木 貢（国立感染症研究所）
情報関係基礎の第2問は，「情報技術に必要な『ものの考え方』とその応用能力を問う問題」として出題されています．これまでの第2問の多くは，解答者が試験で初めて接する（ことが期待されている）システムとその上の定義に対して，出題者が与えた誘導に沿って，そのシステムの性質を見出し，さらに興味ある性質を導きだす，というストーリーになっています．同じ第2問を取り上げた第10弾（小池ケイコさんの「幸いさ」の解説）では，回文がネタになっていますが，今回紹介する2020年本試験問題 第2問のネタは「反転する盤面」です．
天野さんと一緒に問題を巡る
実際に受験生が目にした問題を情報入試委員会のコレクションから取得し，確認してください．本稿では詳細を一部省略しています．この章では主人公の天野さんと一緒に問題を見ていきましょう．
定義
天野さんは，図-1のような3×3のマスの盤面であって，各マスは白か黒に塗られているものを使って「遊んで」います．
9つのマスを識別するために，左上から右下に向かって1～9の番号が付けられています．盤面を使った遊びは以下のようなルールになっています．
各々のマスは白か黒の状態を取り得る．
初期盤面ではすべてのマスは白である（すべてのマスが白の盤面を初期盤面と定義する，と考えてもよいでしょう）．
マスの1つを指定すると，そのマスと，そのマスの縦横に隣接するマスの色を反転，つまり白のマスは黒のマスに，黒のマスは白のマスに変化させます．たとえば初期盤面でマス1を指定すると，その上と左にはマスがなく反転できないので，図-2のようになります．
準備問題
定義で説明した盤面の定義に対して，まず次の2つが問われます．
問アイ：初期盤面からマス4と指定したときの盤面は？
図-3に示す盤面が正解です．
問ウ：図-3の盤面に対して，どのマスを指定すると図-4のような盤面になるか？
【マス1】が正解です（以降は，問題に対する解が文中に埋め込まれている場合は，【 と 】で囲います。）．
盤面のパターンの場合の数
操作論的に誘導したかと思うと，天野さんはトリップして，唐突にべき集合の個数を考えます．
問エオカ：盤面の塗られ方は何通りあるか？
答えは【$${2^9=512}$$】通りです．
そして，天野さんの頭に次の疑問が浮かびました．これがこの問題の最終的なテーマになります．
初期盤面から始めてうまいマス指定の列（マス列という）を見つけ出すことができて，盤面のすべての塗り方のパターンを生成できるのか？
性質の発見
元の操作論的な話に戻ります．今度は初期盤面に対して，マス列5, 6, 6を適用した結果がマス列5を適用した結果と同じということと，マス列6, 【5】, 6を適用した結果がマス列5, 6, 6 を適用した結果と同じになるということから，天野さんは次の2つの性質に気づきました．
性質1：順に指定する2つのマスが同じである場合，その結果は【指定直前の盤面と同じになる】．
性質2：順に指定する2つのマスの順序を逆にしても，その結果は【元の順序で指定した結果と同じになる】．
さらに，マス列4, 3, 8, 2, 3, 4, 2, 5, 3と同じ結果になるマス列【3, 5, 8】を計算すると，3つ目の性質に気づきました．
性質3：任意の盤面に対するマス列の結果は，そのマス列に【奇数回】含まれるすべてのマス指定をそれぞれ1回ずつ含むマス列の結果と同じになる．
以上の（数学的な）武器を手にして，さらなる考察を行いました．
単一反転マス列
天野さんは，1つのマスだけの色を反転させるマス列（単一反転マス列）を，各々のマスについて見つけ出せれば，盤面を自在にコントロールできると気付きました．そして，試行錯誤して，図-5に示す3つのマス列を見つけ出しました．
この結果を用いて，たとえばマス列5, 7, 8, 9がマス2の単一反転マス列であることをヒントにして，【マス6】の単一反転マス列はマス列1, 4, 5, 7であることが分かり，同様にして【マス4】や【マス8】のみを反転する単一反転マス列を導き出すことができました．
さらに，マス列1, 3, 6, 7, 8をヒントにして，【マス3】，【マス7】，【マス9】の単一反転マス列も導き出すことができました．
以上から，たとえば初期番目から図-6の盤面を得るのに，（マス列1, 2, 6, 7, 8とマス列2, 4, 5, 6, 8を合わせて，性質1～3を使えなくなるまで使って）マス列1, 2, 3, 4, 【5, 7】を適用すればよいことが分かりました．
考察
ここで，天野さんとともに疑問を整理しましょう．
まず，性質1～3を繰り返し適用して，マス列に並ぶ番号が小さい順になるようにしたものを基本形と呼ぶことにします．たとえばマス列2, 1, 1, 1, 2, 3もマス列5, 1, 3, 5も基本形は同じマス列1, 3になり，基本形になり得るマス列は長さ0のものも含めて512通りになります（ありゃ，問エオカの答だ！）．
もし，初期盤面に対して，異なる2つの基本形が同じ盤面を生成するとしたら，生成できない盤面が存在することになります．しかし単一反転マス列の考察によって，単一反転マス列がすべてのマスについて存在し，これらを組み合わせることで任意のパターンの盤面を生成できることが分かりました．したがって，異なる基本形は【異なる】盤面を生成することになり，天野さんの疑問に対する結論が出ました．
以上が天野さんの思考の旅路でした．めでたしめでたし．
出題に対する意見
天野さんの思考過程に沿って解答者は誘導されているので，「やればできる」問題であるのは確かですが，性質1～3が意味するところを理解してすぐに使いこなせる受験生には簡単でも，そうでない受験生には何が何だか分からないで時間が過ぎ去っていくタイプの問題であると思います．つまり，情報関係基礎の第2問の使命を十分に果たしていると考えられます．
一方で，考察で512という問エオカの答えをさらしている個所は，素直にエオカにした方がよいのはないかと思います．べき集合は計算量の見積もりにも通じる話で，教科情報の重要なポイントの1つだと思います．問エオカができなくても他の問題は解けるので，この問題のために得点分布が2コブ分布になることはないし，問題文中に答があるような作問をすると「国語じゃあるまいし」と悪口を言われます．同時に，盤面の数の場合の数の前半の問エオカを，この前に移動します．この個所の後半は，天野さんをトリップさせなくても（前半がなくても），ストーリーとしても問題としても成立すると思います．
この辺で作問者たちは逡巡したのではないかと、筆者は妄想します．オリジナルの問題文は
このとき，初期盤面から作成できる盤面の数は基本形の個数「ヌ」となり，すべての盤面の数（「エオカ」）と基本形の個数の関係から，作成することができない盤面は必ず存在することになる．（原文ママ）
となっていますが，「すべての盤面の数（「エオカ」）と基本形の個数の関係」という記述がちょっと苦しげで，受験生も戸惑うのではないでしょうか？ 「関係」と書かれて「同じ値」のことだとすぐに判断するのは難しいと思います．
問題の難易度を上げるには
この問題をスパイシーにする方法，つまり難易度を上げる方法の1つは，単一反転マス列を試験時間内で見つけ出させるようにすることだと思います．かけるスパイスにも，まったくの白紙状態で図-5を見つけさせる「激辛」や，問ウのようにマス列の一部を抜いて考えさせる「中辛」等，いろいろな調整が考えられます．
もちろん，単一反転マス列を見つけ出す問題ができなくても，「もし9つのマスの各々について単一反転マス列が見つかったら」ということを仮定して，最後の考察を行うことは可能です．
まとめと余談
第2問のミッションに向けた問題として（多少の注文はありますが）本稿で紹介した問題はよくできていて，実に魅力的なネタを提供していると思います．
実際の入試では既出ということでそのままでは使えないかもしれませんが，たとえば反転するマスを縦横から斜めにするといった小手先の変更や，正方形から正6角形や正3角形にするといった変更を行えば，良い問題が作れるかもしれません．
話の脱線を恐れずに言うと，この問題の設定は，同じ情報関係基礎の第3問（プログラミングの問題）のネタとしても使えると思います．たとえば，目的とする盤面を生成するマス列を調べたり，512通りのすべてを数え上げて生成されない盤面の有無を調べたりするプログラムを作るという問題が考えられます．
あるいは，マス列を基本形にする手順を誘導しながら答えさせる問題も可能でしょう．小さい順に並べるにはソーティングが必要なので，受験生が頻出のバブルソートをさっと頭の中から出せるか否かには興味があります．
次のC言語コードは生成されない盤面の有無を調べるプログラムで，ビット演算やビット演算の結果で配列をアクセスしていて少し難解ですが，マクロとして定義されているBAをビルトインの手続きとして抽象化し，排他的論理和の説明をすれば，出題可能だと思います．
#include <stdio.h>
#define BS(x) (1<<((x)-1))
#define BA(x) (stencil[(x)-1])
unsigned stencil[] = {
BS(1)|BS(2)|BS(4), // 1
BS(1)|BS(2)|BS(3)|BS(5), // 2
BS(2)|BS(3)|BS(5), // 3
BS(1)|BS(4)|BS(5)|BS(7), // 4
BS(2)|BS(4)|BS(5)|BS(6)|BS(8),// 5
BS(3)|BS(5)|BS(6)|BS(9), // 6
BS(4)|BS(7)|BS(8), // 7
BS(5)|BS(7)|BS(8)|BS(9), // 8
BS(6)|BS(8)|BS(9) // 9
};
char map[512];
unsigned accum(unsigned x) {
unsigned a = 0;
int i;
for (i = 1; i <= 9; i++) {
if (BS(i) & x) {
a ^= BA(i);
}
}
return a;
}
int main() {
int I;
for (i = 0; i < 512; i++) {
map[accum(i)] = 1;
}
for (i = 0; i < 512; i++) {
if (map[i] == 0) {
printf("%03x\n", i);
}
}
}（2022年9月1日受付）
（2022年10月3日note公開）
■鈴木 貢（正会員）
1995年，電気通信大学博士後期課程単位取得満期退学，博士（工学）．電気通信大学助手，島根大学准教授を経て，2021年9月より国立感染症研究所室長．特殊命令向けコンパイラ最適化，セキュリティ教育，オープンソース工学教育に興味を持つ．
情報処理学会ジュニア会員へのお誘い
小中高校生，高専生本科～専攻科1年，大学学部１～3年生の皆さんは，情報処理学会に無料で入会できます．会員になると有料記事の閲覧，情報処理を学べるさまざまなイベントにお得に参加できる等のメリットがあります．ぜひ，入会をご検討ください．入会はこちらから！