章末問題

以下の問題を用意しておきました。解いてプログラミングになれましょ。

例題 1

与えられた数が素数かどうか判定する関数を実装せよ。

bool is_prime(long n) {
  // ここに書く
  return true;
}

解き方

愚直に 2 から n 未満までのどの数でも割り切れないかどうか調べるとこうなる。

bool is_prime(long n) {
  for (long i = 2; i < n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

でも、√n 以下の数までで割れるかどうか調べるだけでいい。

bool is_prime(long n) {
  for (long i = 2; i * i <= n; ++i) {
    if (n % i == 0) {
      return false;
    }
  }
  return true;
}

実際はもうちょっと効率の良いやり方もあるけれど、大抵はこのくらいで大丈夫。

問 1

こんな入力がされる。

N M
V1
V2
V3
:
VN
Q1
Q2
Q3
:
QM

• N は V の個数を表す整数。
• M は Q の個数を表す整数。
• V は整数。
• Q は 0 以上 N 未満の整数。

それぞれの Q ごとに、Q 番目 (0 始まり) の V が偶数なら 1 を、奇数なら 0 を出力せよ。

入力例:

5 8
3
1
7
8
-2
2
2
3
0
4
1
1
2

出力例:

00101000

問 2

V 個の異空間どうしが、E 個のポータルで繋がれている。0 番目の空間から、V - 1 番目の空間へ移動したい。でもポータルをたくさん通ってしまうと何らかの負荷が大きいので、ポータルを通る回数をできるだけ少なくしたい。

最小で何回通ればいいか計算しよう。

E V
src1 dst1
src2 dst2
:
srcE dstE

• E は src と dst の個数を表す整数
• V は正の整数
• src と dst は 0 以上 V 未満の整数
• 0 番目の空間から V - 1 番目の空間まで到達できないような入力はない。

各ポータルは src 番目の空間から dst 番目の空間につながっている。

ポータルを通る最小の回数を出力せよ。

入力例:

5 5
0 1
1 2
1 4
4 3
3 5

出力例

4

問 3

なんか知らんけど迷路に迷い込んでいるみたい。だが都合のいいことに迷路の地図がある。お小水も近いので早く脱出したい。

現在地からゴールまでの最短経路を求めよう。

W H
Ix Iy
maze_1_1 maze_1_2 .. maze_1_W
maze_2_1 maze_2_2 .. maze_2_W
:        :           :
maze_H_1 maze_H_2 .. maze_H_W

• W と H は 0 以上 2e3 以下の整数
• Ix は 0 以上 W 未満の整数
• Iy は 0 以上 H 未満の整数
• maze は文字で、'#' か ' ' のどちらか
• 最短経路が二通り以上ある / 存在しないような入力はない。

W は迷路の幅で、H は迷路の高さ。

左上を (x, y) = (0, 0) として、現在位置は (Ix, Iy) である。

ゴールは外周の空いたマスならどこでもいい。

通る道を '.' にして出力せよ。

入力例:

10 10
1 1
##########
# ## #   #
# #  # # #
# #    # #
# # # ## #
#   # #  #
# #   # ##
# # # # ##
#   # #  #
######## #

出力例:

##########
#.## #...#
#.#  #.#.#
#.#....#.#
#.#.# ##.#
#...# #..#
# #   #.##
# # # #.##
#   # #..#
########.#