小池ケイコさんの「幸いさ」の解説
谷 聖一 （日本大学 文理学部 情報科学科）
連載「教科『情報』の入学試験問題って？」第10弾です．前回までの入試問題解説に関してはこちら（https://note.com/ipsj/m/m1ca81b5d1e66）をご覧ください．
「小池ケイコさんは，なぜか回文が大好きで毎日回文のことばかりを考えている。」
好きなことばかりを考えていられて，幸いさは最大さ！ 上の文は，大学入学共通テスト（以下，共通テスト）の2022年度本試験「情報関係基礎」第2問（以下，2022年度本試験第2問）の書き出しです．
小池さんは常々世の中には回文ではない文字列も存在することを残念に思っていた。しかし，幸いなことに長さ1の文字列は回文なので，どんな文字列も回文を連結して作れることに気付いた。その際，連結する回文の数が少ない方がより幸せに感じられたため，ある文字列を作成するために連結する最も少ない回文の数でその文字列の長さを割った値を，その文字列の幸いさと呼ぶことにした。
ここから物語は始まります．「これが『情報』の問題？」と思われた方も，「フムフム，まさしく『情報』の問題だ！」と思われた方もいるでしょう．問1では，「回文」の定義や「幸いさ」の定義を理解できているか確認し（問いを通して，定義の理解を促し），問2・問3と続きます．このノートでは，これらの問を解説し，高等学校の教科「情報」で身に付けるべきどのような能力を測ろうとしているのかを考えてみたいと思います．まず，共通テスト「情報関係基礎」と第2問の位置付けの説明から始めましょう．
「情報関係基礎」第2問
この春に高校に入学する生徒から新しい学習指導要領で学びます．情報科は，これまでは「社会と情報」と「情報の科学」の2科目から1科目を選択必履修でしたが，共通必履修の「情報Ⅰ」と選択の「情報Ⅱ」の2科目が新設されます．すべての高校生が必履修の「情報Ⅰ」で，「情報社会の問題解決」「コミュニケーションと情報デザイン」「コンピュータとプログラミング」「情報通信ネットワークとデータの利用」について学習することになります．この学習指導要領で学ぶ生徒が臨む2025年度大学入試からは，共通テストで出題される教科に「情報」が追加されることが検討されています．2021年9月の「『令和7年度大学入学者選抜に係る大学入学共通テスト実施大綱の予告（補遺）』について（通知）」では，教科「情報」の出題科目は「情報Ⅰ」で，試験時間は60分とされています．
共通テストは，2020年度大学入試を最後に廃止された大学入試センター試験（以下，センター試験）の後を受け，2021年度大学入試より実施されています．センター試験と共通テストを通じて，教科として「情報」は出題されていませんが，教科「数学」の出題科目グループ②に「数学Ⅱ・数学B」などと並んで「情報関係基礎」が設置されています．その出題範囲は，「専門教育を主とする農業，工業，商業，水産，家庭，看護，情報及び福祉の8教科に設定されている情報に関する基礎的科目」と定められており，第1問と第2問が必答問題で，第3問と第4問が選択問題となっています．
後ほど説明しますが，第2問は「情報技術に必要な『ものの考え方』とその応用能力を問う問題」として出題されています．この「ものの考え方」には，情報の表現・モデル化・抽象化・アルゴリズム的な思考などが含まれるのでしょう．小池ケイコさんが定義した「幸いさ」は数理モデルと言えます．では，問2・問3を見ていきましょう．解法にも触れながら解説しますので，ネタバレを避けたい方は，読み進む前に問題に取り組んでください．
問2
図-1 は，問2の導入部分です．小池さんは「幸いさ」を多くの人に親しんでもらうため「幸いさ」を「機械的に計算する」ことを考えます．脇道にそれますが，「機械的に計算する」というのは，文脈から「計算の手順を明確にし，手順通りに行えば，特別な工夫をしなくても正しく計算できるようにする」ということ，つまり，アルゴリズムを設計する・自動化することと言えるでしょう．「幸いさ」は一意に値が定まるように問1で適切に定義されていますが，その計算手順は与えられていません．話を戻します．それで，まず，問2の問題文中の図1のような表を用いて「文字列に現れるすべての回文」を求めようとします．実際には，文字列中のすべての部分文字列に対して回文（○）かそうでないか（✗）を判定し，$${x}$$文字目から$${y}$$文字目の判定結果を表の$${x}$$列$${y}$$行のマス目に記録します．
問2 の図-1に続く部分で，小池さんは表を完成させる手間を減らす方法を考えます．
$${x}$$文字目から$${y}$$文字目が回文でなければ，$${(x-1)}$$文字目から$${(y+1)}$$文字目は回文にはならない（表で考えると「✗のマス目の左下のマス目は✗」）
$${x}$$文字目から$${y}$$文字目が回文ならば，$${(x-1)}$$文字目から$${(y+1)}$$文字目が回文かどうかは，$${(x-1)}$$文字目と$${(y+1)}$$文字目が一致しているかだけで判定できる
小池さんは，上の性質を利用し，また，処理する順番（図-2）を工夫することで，次の手順を考えました．
長さ1の部分文字列はすべて回文なので，対応するマス目を○にする
長さ2の部分文字列各々に対して，回文かどうか判定し，対応するマス目を○か✗にする
処理する部分列の長さ$${L}$$を 3, 4, … と元の文字列の長さまで増やしながら次を繰り返す：
長さ$${L}$$の部分列各々に対して
右上のマス目が✗の場合：対応するマス目を✗にする
右上のマス目が○の場合：今考えている部分文字列の両端を比較して，同じなら○を，異なれば✗を，対応するマス目に記録する
すべてのマス目で対応する部分文字列が回文かどうかを素朴に判定するのに比べて，この手順の手間はかなり軽減されています．
問3
問3では，問2などの方法で文字列に現れるすべての回文が求まったあと，それらを利用して与えられた文字列を作るために連結する最も少ない回文の数（最小回文数）を効率良く求める方法を考察します．図-3 は，問3の前半部分です．まず，列挙した回文を問3の問題文中の図2のように矢印で表します．矢印が結ぶ丸印の番号は，最小回文数を求める文字列の文字間に対応しています．$${i}$$と$${j}$$を結ぶ矢印は，$${(i+1)}$$番目から$${j}$$番目の部分文字列が回文であることを表しています．つまり，左端の丸印から右端の丸印まで途切れずにつながった矢印の列は，連結すれば与えられた文字列となる回文の列に対応しています．問3では，左端の丸印からある丸印までをつなく矢印の最小本数を最短距離と呼んでいます．最小回文数を求めるには，左端の丸印から右端の丸印までの最短距離を求めればよいわけですね．
では，どうすれば最短距離を効率良く求めることができるでしょうか．$${j}$$の丸印に$${d}$$本の矢印が入っているとします．これら$${d}$$ 本の矢印の元の丸印の番号を$${i_1, i_2, \dots, i_d}$$とします． $${j}$$ の丸印に来る直前は，$${i_1, i_2, \dots, i_d}$$のいずれかの丸印にいるので，左端の丸印から$${j}$$の丸印までの最短距離は，{直前が$${i_1}$$だった場合の距離，直前が$${i_2}$$だった場合の距離，$${\cdots}$$，直前が$${i_d}$$だった場合の距離}の中の最小値となります．
$$
\min_{k=1}^d\{左端の丸印からi_kの丸印までの最短距離 + 1 \}
$$
上の式の中の $${+1}$$ は，$${i_k}$$の丸印から$${j}$$の丸印を結ぶ矢印の分です．この式を活用して番号が小さい順に最短距離を求めることにすれば，最短距離を求めるのに必要な値はすでに求まっているので，すべての丸印に対して左端の丸印からの最短距離を簡単に求めることができますね（図-4）．
測ろうとしている「情報」の能力
情報と情報技術についての科学的な探究の過程を重視する。問題の作成に当たっては，専門教育を主とする「農業，工業，商業，水産，家庭，看護，情報及び福祉」に設定されている情報に関する基礎科目を出題範囲としていることを踏まえ，情報及び情報技術の基本的な知識と，考え方，基本的なアルゴリズムの理解とそれを実現する方策，プログラミングやアプリケーションソフトウェアを活用したデータの処理や分析，問題解決の方法の理解を問う問題などを含めて検討する。
出題教科・科目の問題作成の方針
センター試験でも共通テストでも，実施後しばらくすると「問題評価・分析委員会報告書」が公表されます．その中の「問題作成部会の見解」によると，2015年度から2021年度までの「情報関係基礎」は，基本的に次の4つの大問で構成されています．
コンピュータ・情報に関する基本的な知識と理解を問う問題（必答）
情報技術に必要な「ものの考え方」とその応用能力を問う問題（必答）
プログラミングの基礎能力に関する問題（選択）
情報の統合的な処理手法の理解や問題解決能力と論理的思考力について合わせて問うことを目的に，アプリケーションソフトウェアの利活用に関する問題（選択）
2022年度共通テストの問題評価・分析委員会報告書はまだ公開されていませんが，小池ケイコさんの2022年度本試験第2問も「情報技術に必要な『ものの考え方』とその応用能力を問う問題」として出題されたと思われます．
「情報Ⅰ」の学習指導要領では，身につけるべき知識・技能に「アルゴリズムを表現する手段，プログラミングによってコンピュータや情報通信ネットワークを活用する方法について理解し技能を身に付けること。」とあり，身につけるべき思考力・判断力・表現力に「目的に応じたアルゴリズムを考え適切な方法で表現し，プログラミングによりコンピュータや情報通信ネットワークを活用するとともに，その過程を評価し改善すること。」とあります．しかし，センター試験時代も含めて2015年度から2024年度までの「情報関係基礎」は，2012年度高校入学者から学年進行で実施された学習指導要領に基づいても出題されます．各専門学科において開設される教科だけでなく，「社会と情報」と「情報の科学」も参照されていると思われます．たとえば，「情報の科学」の内容を見ると「(2) 問題解決とコンピュータの活用 ア 問題解決の基本的な考え方 」に「問題の発見，明確化，分析及び解決の方法を習得させ，問題解決の目的や状況に応じてこれらの方法を適切に選択することの重要性を考えさせる。」とあります．「情報技術に必要な『ものの考え方』とその応用能力を問う」のは，学習指導要領のこのような項目との関連と思われます．問2・問3では，誘導の元ではありますが，問1の数理モデルを活用して「問題の発見，明確化，分析及び解決」を行ったと言えるでしょう．ただ，このモデルの妥当性は，小池ケイコさんにしか分からないのかもしれません．
参考文献
1) 情報関係基礎 アーカイブ, 情報処理学会 情報入試委員会, https://sites.google.com/a.ipsj.or.jp/ipsjjn/resources/JHK
（2022年3月23日受付）
（2022年4月15日note公開）
■谷 聖一（正会員）
日本大学文理学部 教授．（一社）情報オリンピック日本委員会 専務理事．計算論的位相幾何学・複雑ネットワーク解析などの研究，および，情報科学の普及活動に従事．IPSJ MOOC（https://sites.google.com/a.ipsj.or.jp/mooc/）「コンピュータとプログラミング」の制作に携わる．
情報処理学会ジュニア会員へのお誘い
小中高校生，高専生本科～専攻科1年，大学学部１～3年生の皆さんは，情報処理学会に無料で入会できます．会員になると有料記事の閲覧，情報処理を学べるさまざまなイベントにお得に参加できる等のメリットがあります．ぜひ，入会をご検討ください．入会はこちらから！