共通テストの問題を深さ優先探索してみた

競プロとは直接関係ありませんが,競プロで得た知識のDFS(深さ優先探索)を使って問題を解きました.

本記事では言語はC++を使っていますが,一応他の言語を使った人でも読めるように解説したつもりです.

ちなみに,初めて紙面上で解いた時はDFSではなくBFS(幅優先探索)で私は解きました.

手作業ならDFSは大変なので...

BFSの実装は綺麗なステップ数の保持の仕方がよくわかりませんでした(おい)

BFSで実装した人はぜひ議論しましょう.

問題設定

以下,共通テストの数学IA,題4問より抜粋です.

第4問

円周上に15個の点 P_0, P_1, \cdots , P_{14}が反時計回りに順に並んでいる.

最初,点 P_0に石がある.

さいころを投げて偶数の目が出たら石を反時計回りに5個先の点に移動させ,奇数の目が出たら時計回りに3個先の点に移動させる.

この操作を繰り返す.

例えば,石が点 P_5にあるとき,さいころを投げて6の目が出たら石を点 P_{10}に移動させる.

次に,5の目が出たら石を点 P_7に移動させる.


<中略>


(4)点 P_1, P_2, \cdots, P_{14}の中から点を1つ選び,点 P_0にある石をさいころを何回か投げてその点に移動させる.

そのために必要となる,さいころを投げる最小回数を考える.

例えば,さいころを1回だけ投げて点 P_0にある石を点 P_2に移動させることはできないが,さいころを2回投げて偶数の目と奇数の目が1回ずつ出れば,点 P_0にある石を点 P_2へ移動させることができる.

したがって,点 P_2を選んだときには,この最小回数は2回である.

 P_1, P_2, \cdots, P_{14}のうち,この最小回数が最も大きいのは,点 であり,その最小回数は である.

(出典:独立行政法人 大学入試センター 共通テスト 数学IAより)

考察

以下,反時計回りの n個先への移動を +n,時計回りの n個先への移動を -nで表します.

まず,点 P_0から一手で行ける点は, +5の移動による P_5と, -3の移動による P_{12}の2つです.

さらに,点 P_5, P_{12}からそれぞれ +5の移動と -3の移動を考えることで,点 P_0から二手で行ける点がわかります.

 P_5からは点 P_{10}, P_2に,点 P_{12} からは点 P_2, P_9に一手で行けるので,点 P_0から二手で行ける点は点 P_2, P_9, P_{10}の3つです.

これを繰り返すことで点 P_0からの最小移動ステップ数が求まります.

私はこれをDFS(幅優先探索)で実装しました.

イメージ図は下のようになります.

f:id:chankilu23:20210125132731j:plain

左に伸びる辺は +5の移動を,右に伸びる辺は -3の移動を表しています.

色の説明をします.

青の点は,その点から +5の移動と -3の移動をするために再帰的に操作をする点です.

赤の点は,現在のステップ数よりも最適なステップ数が既に見つかっているため,再帰をせず次の点の探索に移るという点です.

緑の点は,再帰呼び出しをしますが,後の方でより最適なステップ数が見つかるので図では省略しているという点です.(なので,実際の図はもっと大きくなります)

これをコードで書いていきます.


変数として以下を宣言します.

vector<int> step(15, 20);                                           

記法の意味ですが,step[15]というint型の配列の要素を全て20で初期化する,と捉えてください.

vectorという型で宣言していますが,普通の配列だと思ってもらってもこの記事では差し支えありません.

step [ i ]には,点 P_0から点 P_iに移動する最小ステップ数を更新しながら格納していきます.


それではDFSの中身を見ていきます.

void dfs(int current_point, int height){
  int next_point1 = (current_point + 5)%15;
  int next_point2 = (current_point - 3 + 15)%15;

  if(height < step[next_point1]){
    step[next_point1] = height;
    dfs(next_point1, height+1);
  }
  if(height < step[next_point2]){
    step[next_point2] = height;
    dfs(next_point2, height+1);
  }
}

引数は,現在見ている点current_point,現在の点のステップ数に+1をした値のheight,の2つです.

1行目と2行目で次に訪れる点を計算します.15個の点は円上に並んでおり,点 P_0と点 P_{14}は互いに移り合うので,15で割った余りの考え方で計算できます.

負数になることも考慮して, -3の移動では15を足してからmod 15をします.


その下の2つのif文は同じことをしているので1つ目だけ説明します.

移動が +5, -3の先の点で同じことをするので再帰をするのですが,再帰をする条件としては,現在のステップ数heightが,移動先の点のその時点での最適ステップ数より小さいことです.

再帰をするとステップ数は1増えるので,移動先の点のその時点での最適ステップ数がheightより小さければ再帰をする意味がないです.


それでは最後に実行結果を以下に示します.

 点  最小ステップ数 
 0        0
 1        5
 2        2
 3        4
 4        4
 5        1
 6        3
 7        3
 8        5
 9        2
 10       2
 11       4
 12       1
 13       6
 14       3

これを見ると,点 P_0からの最小ステップ数は点 P_{13}が一番大きいことがわかります.

よって設問(4)の答えは,:13,:6です.


というわけで競プロ番外編,共通テストの問題を深さ優先探索してみた,でした.

出典:独立行政法人 大学入試センター 共通テスト 数学IA