情報科学的思考を測る問題 ─ビーバーチャレンジの問題を例として─
石塚丈晴（大阪電気通信大学）
大学入試センターより令和7年度（2025年度）「情報」に対する試作問題が公開されています．この問題を眺めてみますと単に知識を直接問う問題はほとんどなく，与えられた文章や図表などを読み解き，これまでに学んだ知識を使って問題を解決していく力を測ることに重点が置かれていることが分かります．
これらの能力は「21世紀型の能力」とか「21世紀型の学力」と呼ばれており，世界的な学力調査として有名な「PISA」の名前を取って，「PISA型学力」などとも呼ばれているものです．
「ビーバーチャレンジ」は本会でも何度か紹介されておりますので詳細は割愛しますが，元々「情報科学コンテスト」と呼ばれていた問題解決にチャレンジする世界的なCBT（Computer Based Testing）で，日本では情報オリンピック日本委員会が主催して毎年実施されています．筆者はビーバーチャレンジの国際会議であるBebras Task Workshopに2013年に初めて参加しましたが，Bebras Task Workshopで徹底されていることは，単なる知識を問う問題はNGということで，まさに「21世紀型の学力」を測る問題とすることが求められています．
問１
この問題は2018年に小学校5年生～高校1年生を対象として出題されました．
問題タイトル： 水もれ
問題文：
同じ通りに面した16軒の家につながっている水道管のどこかで水もれがおきています．水道局の係の人が，どこで水もれがおきているか検査をします．
検査に協力するため，16軒の家はすべて水を使っていません（止めています）．
水もれしている場所を探すため係の人は，2軒の家の間にあるバルブを閉めて，パイプのメーターが動いているかどうか（水が流れているかどうか）調べます．
たとえば，8の家と9の家の間のバルブを閉めてもまだメーターが動いていたら，1から8の間のどこかで水がもれている（また，9から16の間では水がもれていない）ことが分かります．
パイプと家をつなぐ部分（図では，たての赤い線の部分）のどこかで水がもれています．水もれの場所がどこであっても，水もれの場所が分かるまでにバルブを閉める回数の最小値はいくつでしょう？
正解： 4
解説：
この問題は，問題のある（水漏れの）個所を探す「探索アルゴリズム」の問題です．一番単純なのは，左側（あるいは右側）から1つずつ順番にバルブを閉めて確かめるということを繰り返せばよいわけですが，この方法（「線形探索」と呼ばれています）では最悪すべてのバルブを閉めて確認したところでやっと水漏れ個所を発見することができ，「15回」調べる必要があります．
この問題は，結局「二分探索アルゴリズム」で考えていけばよいのですが，「二分探索」を知らなくても，問題をよく読むとヒントが示されています．4文目を読んでみましょう．対象の範囲の真ん中のバルブを閉めて調べれば，残りの調べる範囲が半分になると書いてあります．つまり，これを残りの水道管が最後の1つになるまで繰り返せばよいのでは？と推測することができます．最初に真ん中のバルブを閉めることで，残り8軒が対象となり，その真ん中のバルブを閉めれば残り4軒，さらに残りの4軒の真ん中を閉めると残り2軒，最後に2軒の真ん中を閉めると1軒が特定されることになり，4回バルブを閉めれば必ず水漏れ個所を特定することができます．
考えられる応用問題： この問題をプログラム化する問題
問2
この問題は2021年に高校2～3年生を対象として出題されました．
問題タイトル： ビーバーソート
問題文：
川には長さが異なる丸太がいくつかあります．ビ太郎の仕事は，丸太を長さ順に並び替えることです．ビ太郎は川岸に沿って移動し，必ず2つの丸太の間で止まります．両隣の2本の丸太の長さを比較して，必要であれば入れ替えます．
ビ太郎は，最初にどのような並びで丸太が入ってきても，以下のようにして丸太を長さ順に並べ替えられることを知っています．
左端の丸太の右側の位置から始めます
左端の丸太の右側から始めて，右端の丸太の右側に来るまで次を繰り返します:
左側の丸太が右側の丸太よりも短い場合は，丸太1本分右に移動します．
右側の丸太が左側の丸太よりも短い場合は，これらの丸太を入れ替えてま
す．入れ替えたあと，開始位置（左端の丸太の右側の位置）にいなけれ
ば，丸太1本分左に移動します．
ビ太郎が4本の丸太をどのように並べ替えるか見てみましょう．この例では，ビ太郎は9回動きます（実際に動いた場合のみを数えています．左端の開始位置にいて，丸太を入れ替えたものの移動しなかった場合は数えません）．※実際のコンテストでは動画でこの様子を見ることができました．
ビ太郎が丸太を並び替えるのに動く回数は，丸太が最初にどのように入ってきたかによって決まります．最悪の場合，6本の丸太を並び替えるのにビ太郎は25回動く必要があります（左端の開始位置にいて，入れ替えたものの移動しなかった回数は5回です）．
ビ太郎は60個の丸太を並び替えないとなりません．ビ太郎が動く回数は，次のどの範囲に収まっているでしょう？
選択肢：
① 0 – 30
② 6 – 70
③ 59 – 300
④ 59 – 3600
正解： ④
解説：
データを順番に並び替える処理は「整列アルゴリズム」または「ソーティングアルゴリズム」と呼ばれ，基礎的なものは「情報Ⅰ」の教科書でも扱われています．よく扱われるアルゴリズムとしては，「選択ソート」，「バブルソート」，「マージソート」，「挿入ソート」などがありますが，今回のアルゴリズムはどれでしょうか？ ビ太郎が隣り合う丸太を比較しながら行ったり来たりする様子はバブルソートにも似ていますが，ちょっと違います．また，ビ太郎の右側の丸太が適切な位置になるまでビ太郎が左に動いていく様子は，挿入ソートにも似ていますが，やはりちょっと違います．
このアルゴリズムは「ノームソート」と呼ばれる整列アルゴリズムです．「ノーム」は「妖精」とか「精霊」という意味で「妖精」が順番に並んでいる植木鉢を正しい順番に並び変えていく様子からつけられた名前です．ただし，この「ノームソート」は高校の教科書レベルではまず載っていないアルゴリズムです（知っている生徒さんはかなりマニアック？）．そこで，問題を読みながら推測していくことになります．
まず，最良の場合，つまり左から順に丸太の長さが長くなって並んでいる場合を考えます．4本の場合は，ビ太郎は3回右に動けば終了ですし，6本であれば5回で終了です．とすると，n本の場合は，n-1回動けばよいということになり，これが最小値となります．
次に，最悪な場合，つまり左から順に丸太の長さが短くなって並んでいる場合を考えます．まず4本の場合を考えます．初期位置（左から1本目と2本目の間）で動かずに左右の丸太を入れ替えます．次に左から3本目の丸太を適正な位置（一番左側）に入れ替えるためには，ビ太郎は右に1回動いて入れ替え，左に1回動いて入れ替えればよいので1×2回動いて初期位置にいることになります．そして，この動きで左から1～3本目までは正しい順番になっていることに気が付きましたか？ すると，次は左から4本目の丸太を適正な位置（一番左側）に入れ替えていくためには，ビ太郎は右に2回動いて入れ替え，左に2回動いて入れ替えればよいので2×2回動いて初期位置にいることになります．最後に，右端まで行くのに3回動けば終了となりますので，合計(1+2)×2+3=9回となります．同様に6本の場合を考えると，(1+2+3+4)×2+5=25回動くことになり，問題文の例と一致します．すると，n本の場合は，(1+2+・・・+(n-3)+(n-2))×2+(n-1)=(n-1)×(n-1)回となります．
60本の丸太の場合，最良では59回，最悪では59×59ですから3,481回となります．よって，これを満たす選択肢は④となります．
なお，このノームソートですが，他の整列アルゴリズムと比べて何か良いことがあるのかというと，並び替えの最中に，右側にデータ（今回の例では丸太）を新たに付け加えても対応できるといった特徴があります．
考えられる応用問題： この問題をプログラム化する問題
問3
この問題は2019年に高校2～3年生を対象として出題されました．
問題タイトル： スカーフ制作機
問題文：
スカーフを自動的に制作する機械が開発されました．次の図は，この機械がスカーフの柄（がら）を決めるルールを表しています:
機械は，左の青い矢印から始めて，矢印にたどって絵柄を移動し，移動した絵柄を順にスカーフの柄と決め，右の白い矢印に到達すると，スカーフの柄はすべて決まり，その柄のスカーフを制作します．
上の図のルールで制作されるスカーフはどれでしょう．
選択肢：
①
②
③
④
正解： ①
解説：
問題文中の図は「状態遷移図」と呼ばれるものです．状態遷移図とはその名の通り，ある状態に何かが起こると状態がどのように変わるかを図に示したものです．状態遷移図は，ソフトウェアやプログラムを設計するときや動作を検証するときに使われる重要な考え方です．
ここでは，以下の図に示されるように，それぞれの状態（柄）をA～Eの文字に置き換えて説明します．
この問題では，最初にAからスタートします．AからはBかCに遷移できることが示されています．したがって，この段階では選択肢をA～Eで示した①ABBBBDE，②ACECCCE，③ABDECCE，④ACEABDEはどれも正しいことが分かります．
次に，BからはBかDに遷移できることが示されていますので，やはりこの段階では正しくない選択肢はないことが分かります．
一方，CからはEにしか遷移できませんので，ここでCが続いている②と③は正しくないことが分かります．
次に，DからはEにしか遷移できませんので，この条件は①，④共に満たしていることになります．
最後にEに注目すると，EからはCか「終了」に遷移することができることから，EからAに遷移している④は正しくないことが分かります．
したがって①が正解となります．
問4
この問題は2019年に高校2～3年生を対象として出題されました．
問題タイトル： 回って回って回って
問題文：
ベルトコンベアー上の軸に設置された二等辺三角形の板があります．三角形の板は，軸の周りに回転し，2つの頂点は軸から近く，残りの頂点は軸から離れています．最初は，ある頂点が軸の真上にあり，三角形が120°回転すると，必ず頂点の1つが軸の真上にくるように，軸の位置が調整されています．
ベルトコンベアーの上にいくつか出っ張りがあります．三角形の板が出っ張りの下を通過するとき出っ張りに当たると，反時計回りに 120° 回転します．出っ張りは2種類あります:
長い出っ張りの下を三角形の板が通過すると，必ず反時計回りに 120° 回転します
短い出っ張りの下を三角形の板が通過すると，軸から遠い頂点が上のときは120° 回転しますが，軸から近い頂点が上のときは回転しません
ボブは，最初に三角形のどの頂点が上にあっても，通過したら同じ位置になるような出っ張りの組合せを考えています．同じ位置にさえなっていれば，それがどの位置でもボブは気にしません．
ボブの希望通りになるのはどれでしょう?
選択肢：
① 短い，長い，短い，長い
② 長い，短い，長い，長い
③ 長い，短い，短い，長い
④ 短い，長い，長い，短い
正解： ④
解説：
この問題では，棒のところを通ると状態（三角形の向き）が変わりますので，以下のような「状態遷移図」を描いて考えることが有効になります．
上の図では〇の中が三角形の向き（状態）を示しています．ここでもそれぞれの状態をA～Cと置き換えて説明します．たとえば，①ではAからスタートするとABCCA，BからスタートするとBBCCAとなり両方ともAで終了します．しかし，CからスタートするとCCABCとなりCで終了するので，終了したときの状態は同じではありません．どの状態（ABC）から出発しても終了したときにどれも同じ状態で終了するのは，④で必ずBで終了します．
類似問題：
自動販売機で商品が出てくるまでの状態遷移図
キーボード入力された文字列で数値として受け取ることができるものを判別するための状態遷移図
まとめ
ここでは，国際情報科学コンテスト「ビーバーチャレンジ」の過去に出題された問題から高等学校「情報Ⅰ」と関係するものを4例紹介しました．「情報科学」とは問題解決のための方法を考える学問で文系・理系を問わず，現代の社会に求められている力です．高等学校「情報Ⅰ」は情報科学的な要素が多く含まれていますので，ビーバーチャレンジとは親和性が非常に高いと考えられます．ぜひ，楽しみながらチャレンジしてほしいと思います．
なお，Bebras - International Challenge on Informatics and Computational Thinking 作『ビーバーチャレンジの問題』は クリエイティブ・コモンズ 表示 - 非営利 - 継承 4.0 国際 ライセンスで提供されています．
参考文献
1）「ビーバーチャレンジ」情報ページ https://bebras.eplang.jp/
（2023年2月20日受付）
（2023年4月6日note公開）
■石塚丈晴（正会員）
関西大学大学院総合情報学研究科修了．博士（情報学）．静岡大学工学部，福岡工業大学短期大学部を経て，現在大阪電気通信大学メディアコミュニケーションセンター教授．専門は情報科学教育，プログラミング教育．日本教育工学協会，教育システム情報学会，日本情報科教育学会など各会員．情報オリンピック日本委員会ジュニア部会メンバ．
情報処理学会ジュニア会員へのお誘い
小中高校生，高専生本科～専攻科1年，大学学部１～3年生の皆さんは，情報処理学会に無料で入会できます．会員になると有料記事の閲覧，情報処理を学べるさまざまなイベントにお得に参加できる等のメリットがあります．ぜひ，入会をご検討ください．入会はこちらから！