共通テストの問題を深さ優先探索してみた
競プロとは直接関係ありませんが,競プロで得た知識のDFS(深さ優先探索)を使って問題を解きました.
本記事では言語はC++を使っていますが,一応他の言語を使った人でも読めるように解説したつもりです.
ちなみに,初めて紙面上で解いた時はDFSではなくBFS(幅優先探索)で私は解きました.
手作業ならDFSは大変なので...
BFSの実装は綺麗なステップ数の保持の仕方がよくわかりませんでした(おい)
BFSで実装した人はぜひ議論しましょう.
問題設定
以下,共通テストの数学IA,題4問より抜粋です.
第4問
円周上に15個の点が反時計回りに順に並んでいる.
最初,点に石がある.
さいころを投げて偶数の目が出たら石を反時計回りに5個先の点に移動させ,奇数の目が出たら時計回りに3個先の点に移動させる.
この操作を繰り返す.
例えば,石が点にあるとき,さいころを投げて6の目が出たら石を点に移動させる.
次に,5の目が出たら石を点に移動させる.
<中略>
(4)点の中から点を1つ選び,点にある石をさいころを何回か投げてその点に移動させる.
そのために必要となる,さいころを投げる最小回数を考える.
例えば,さいころを1回だけ投げて点にある石を点に移動させることはできないが,さいころを2回投げて偶数の目と奇数の目が1回ずつ出れば,点にある石を点へ移動させることができる.
したがって,点を選んだときには,この最小回数は2回である.
点のうち,この最小回数が最も大きいのは,点 シ であり,その最小回数は ス である.
(出典:独立行政法人 大学入試センター 共通テスト 数学IAより)
考察
以下,反時計回りの個先への移動を,時計回りの個先への移動をで表します.
まず,点から一手で行ける点は,の移動によると,の移動によるの2つです.
さらに,点からそれぞれの移動との移動を考えることで,点から二手で行ける点がわかります.
点からは点に,点からは点に一手で行けるので,点から二手で行ける点は点の3つです.
これを繰り返すことで点からの最小移動ステップ数が求まります.
私はこれをDFS(幅優先探索)で実装しました.
イメージ図は下のようになります.
左に伸びる辺はの移動を,右に伸びる辺はの移動を表しています.
色の説明をします.
青の点は,その点からの移動との移動をするために再帰的に操作をする点です.
赤の点は,現在のステップ数よりも最適なステップ数が既に見つかっているため,再帰をせず次の点の探索に移るという点です.
緑の点は,再帰呼び出しをしますが,後の方でより最適なステップ数が見つかるので図では省略しているという点です.(なので,実際の図はもっと大きくなります)
これをコードで書いていきます.
変数として以下を宣言します.
vector<int> step(15, 20);
記法の意味ですが,step[15]というint型の配列の要素を全て20で初期化する,と捉えてください.
vectorという型で宣言していますが,普通の配列だと思ってもらってもこの記事では差し支えありません.
step ]には,点から点に移動する最小ステップ数を更新しながら格納していきます.
それでは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個の点は円上に並んでおり,点と点は互いに移り合うので,15で割った余りの考え方で計算できます.
負数になることも考慮して,の移動では15を足してからmod 15をします.
その下の2つのif文は同じことをしているので1つ目だけ説明します.
移動がの先の点で同じことをするので再帰をするのですが,再帰をする条件としては,現在のステップ数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
これを見ると,点からの最小ステップ数は点が一番大きいことがわかります.
よって設問(4)の答えは, シ :13, ス :6です.
というわけで競プロ番外編,共通テストの問題を深さ優先探索してみた,でした.