Time Limit: 2 sec / Memory Limit: 256 MB
問題文
たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。
- まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
- 次に、それぞれのマスが通行可能な空きマス(
.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。
今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。幅優先探索というのは以下の手法です。
- スタート地点から近い(たどり着くための最短手数が少ない)マスから順番に、たどり着く手数を以下のように確定していく。説明の例として図1の迷路を利用する。
- 最初に、スタート地点は、スタート地点から手数0でたどり着ける(当然)ので、最短手数0で確定させる(図2)。
- 次に、スタート地点の四近傍(上下左右)の空きマスについて、手数1で確定させる(図3)。
- 次に、手数1で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数2で確定させる(図4)。
- 次に、手数2で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数3で確定させる(図5)。
- 次に、手数3で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数4で確定させる(図6)。
- 上記の手順を確定の更新が無くなるまで繰り返すと、スタート地点からたどり着ける全ての空きマスについて最短手数が確定する(図7)。スタートとゴールは必ず空きマスを辿ってたどり着けるという制約があるので、ゴール地点への最短手数も分かる。
さて、この処理をスマートに実装するためには、先入れ先出し(FIFO)のキュー(Queue)というデータ構造を用いると良いことが知られています。もちろん、使わなくても解くことは可能です。今回、よく分からなければ思いついた方法で解くことをおすすめします。先入れ先出しのキューとは以下のような機能を持つデータ構造です。
- 追加(Push): キューの末尾にデータを追加する。
- 取り出し(Pop): キューの先頭のデータを取り出す。
このデータ構造を使うと、先ほどの幅優先探索の説明における「マスの最短手数の確定」のタイミングでその確定マスをキューに追加し、追加操作が終わればPopを行い、取り出したマスの4近傍を調べるということを繰り返せば(つまり先に追加されたものから順番に処理していけば)、簡潔に処理ができることが分かります。
入力
入力は以下の形式で標準入力から与えられる。
R\ C
sy\ sx
gy\ gx
c_{(1,1)}c_{(1,2)}\ …\ c_{(1,C)}
c_{(2,1)}c_{(2,2)}\ …\ c_{(2,C)}
:
c_{(R,1)}c_{(R,2)}\ …\ c_{(R,C)}
- 1 行目には、行数 R(1≦R≦50)と列数 C(1≦C≦50)がそれぞれ空白区切りで与えられる。
- 2 行目には、スタート地点の座標 (sy,sx) が空白区切りで与えられる。スタート地点が sy 行 sx 列にあることを意味する。 1≦sy≦R かつ 1≦sx≦C である。
- 3 行目には、ゴール地点の座標 (gy,gx) が空白区切りで与えられる。ゴール地点が gy 行 gx 列にあることを意味する。 1≦gy≦R かつ 1≦gx≦C であり、(gy,gx)≠(sy,sx)であることが保障されている。
- 4 行目から R 行、長さ C の文字列が 1 行ずつ与えられる。各文字は
.もしくは#のいずれかであり、i 回目 (1≦i≦R) に与えられられる文字列のうち j 文字目 (1≦j≦C) について、その文字が.なら、マス (i,j) が空きマスであり、#なら、マス (i,j) が壁マスであることをあらわす。 - 盤面は壁マスで囲まれている。つまり、i=1,i=R,j=1,j=C のうちいずれか1つでも条件を満たすマス (i,j) について、c_{(i,j)} は
#である。また、スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。
出力
- スタート地点からゴール地点に移動する最小手数を 1 行に出力せよ。最後に改行を忘れないこと。
入力例1
7 8 2 2 4 5 ######## #......# #.###### #..#...# #..##..# ##.....# ########
出力例1
11
問題文中の例です。
入力例2
5 8 2 2 2 4 ######## #.#....# #.###..# #......# ########
出力例2
10
図8のように進めば 10 手でたどり着くことが進むことができます(※Sはスタート、Gはゴールをあらわす)。
入力例3
50 50 2 2 49 49 ################################################## #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# #................................................# ##################################################
出力例3
94
もはやただの広い空間であり、迷路と呼んで良いのかは分からないがこの問題でこのような盤面も迷路として扱う。兎にも角にも、スタートからゴールへの最短手数は 94 である。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
整数 N, M, P が与えられる。
N の P 乗を M で割ったあまりを求めよ。
入力
入力は以下の形式で標準入力から与えられる。
N M P
1 行目には、整数 N, M, P (1≦N,M≦10^{9}, 1≦P≦10^{14}) が、スペース区切りで与えられる。
出力
N の P 乗を M で割ったあまりを出力せよ。
解説
入力例 1
12 15 7
出力例 1
3
12 の 7 乗は 35831808 になります。これを 15 で割った余りは 3 です。
入力例 2
123456789 234567894 6574837563712
出力例 2
120678297
数が非常に大きくなることもあります。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
n 個の葉を持つ順序付き二分木を作りたい。 この二分木のコストは以下のように定義される。
Σ_{i=1}^{n} w_i × depth(i)
ただし、depth(i) は、二分木における左から i 個目の葉の深さを表す。 w_i は入力として与えられる重みである。 コストの最小値を求めよ。
入力
入力は以下の形式で標準入力から与えられる。
n w_1 w_2 ... w_n
- 1 行目には、要素の個数を表す整数 n (1≦n≦100,000) が与えられる。
- 2 行目には、要素の重みを表す n 個の整数が与えられる。このうち i (1≦i≦n) 番目の要素は、i 番目の要素の重みを表す w_i(1≦w_i≦1,000) である。
出力
条件を満たす順序付き二分木のコストの最小値を出力せよ。
部分点
この問題には部分点が設定されている。
- n ≦ 100 を満たすデータセットに正解した場合は、50 点が与えられる。
- n ≦ 3,000 を満たすデータセットに正解した場合は、上記とは別に 50 点が与えられる。
- 追加の制約のないデータセットに正解した場合は、上記とは別に 1 点が与えられる。
解説
入力例1
6 1 2 3 4 9 3
出力例1
53
以下の図のような二分木が最適となります。
図 1 : サンプル入出力に相当する二分木
このような二分木を作った場合、コストは 53 になります。