A - 不完全迷路

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

あなたは、道端で怪しげな迷路ジェネレーターを拾ってしまいました。 迷路ジェネレーターを動かすと、縦Hマス、横Wマスの迷路を自動で生成してくれます。 しかし、それには不具合があり、ゴールにたどり着くことのできない迷路を生成するようでした。 そこで、あなたは迷路を修正し、ゴールにたどり着くことのできるようにすることにしました。

迷路には、壁#と道.があり、スタートのマスSとゴールのマスGが1マスずつあります。 プレイヤーは、スタートのマスから移動を始め、隣接する縦横4マスの壁でないマスへ移動しながら、ゴールのマスを目指します。 あなたは、ここから壁のマスを 1マスのみ 道のマスに替えることで、ゴールにたどり着くことのできる迷路を作ることにしました。

ただし、ただ適当な壁を道に変えるでは面白くないと考えたあなたは、スタートからゴールまでの最短経路長が 最長 になるように壁を道に変えることにしました。

上記の操作を行った場合の、スタートからゴールまでの最短経路長を答えてください。

入力

H W
line_1
line_2
...
line_H
  • 1行目には、迷路の高さHと、迷路の幅W (2 \leq H, W \leq 298)が与えられます。
  • 2行目以降のH行には、W文字の文字列line_iが与えられます。各line_i (1 \leq i \leq H)は、#,.,S,Gで構成されており、#が壁、.が道、Sがスタート地点、Gがゴール地点を表します。

なお、S,Gは迷路の中に必ず1つづつ存在します。

与えられる迷路は、SからGへたどり着くことができず、必ず1マスの壁を道に替えるとゴールへたどりつけることが保証されています。

出力

修正した迷路のゴールまでの最短経路長を1行で出力してください。 出力の末尾には改行を入れること。

入力例1

6 8
S..#...#
##...#..
..###.##
........
.#######
.......G

出力例1

28

入力例2

5 6
#.S.#.
###...
...###
.#.#.G
.....#

出力例2

10

ループするような道もありえます

入力例3

4 6
S.....
###.##
######
.....G

出力例3

8

厚い壁もありえます

入力例4

6 8
S.......
########
...#....
.##..##.
...#.#..
.#.G#..#

出力例4

12

最初からS、Gどちらとも繋がっていない道もありえます

入力例5

7 8
.#......
S#.#.###
...#.#.#
###.#.G.
.....#..
..##.#.#
........

出力例5

14
B - ライツアウト

Time Limit: 4 sec / Memory Limit: 291 MB

問題文

ある日、太郎くんが散歩をしていると、空から怪しい機械が落ちてきました。その機械が気になった太郎くんは拾って調べてみることにしました。

どうやらこの機械には縦Hマス、横Wマスの形に並んだON、OFFの2通りの状態を取るライトがあり、あるライトを押すとそのライトとそのライトに隣接する上下左右のライトのON、OFFが反転するようです。

中央の赤丸のライトを押した場合

しかし、落下時の衝撃でいくつかのライトが壊れてしまい押すことができなくなってしまっています。ただし、隣接するライトを押すと壊れたライトの状態は通常通り反転するようです。

太郎くんは、全てのライトの状態をOFFにするのに必要な最小のライトを押す回数が気になりました。太郎くんのために全てのライトの状態をOFFにするために必要な最小のライトを押す回数を求めてください。

入力

入力は以下の形式で標準入力から与えられます。(標準入力中の変数を修正しました。(18:38))

H W
s_{0,0} s_{0,1} ... s_{0,(W-1)}
s_{1,0} s_{1,1} ... s_{1,(W-1)}
.
.
.
s_{(H-1),0} s_{(H-1),1} ... s_{(H-1),(W-1)}
N
x_1 y_1
x_2 y_2
.
.
.
x_n y_n
  • 1行目の、H, W (5 \leq H,W， H \times W \leq 400)は機械についているライトの行数と列数を表します。
  • 2行目以降のH行には、空白区切りでW個の0か1の数字が与えられます。0はライトの状態がOFF、1はライトの状態がONを表します。
  • H+1行目には壊れているライトの数N(0 \leq N \leq W \times H)が与えられます。(16:21 追記)
  • H+2行目以降のN行には、壊れているライトの列x_i(0 \leq x_i \leq W-1), 行y_i (0 \leq y_i \leq H-1)が与えられます。
  • この問題ではすべてのライトを消す手順があることが保証されています。(16:15 追記)
  • 同じ座標は二度与えられません。つまり、i \neq j ならば x_i \neq x_j または y_i \neq y_j が成り立ちます。(18:08 追記)

出力

全てのライトの状態をOFFにするための最小の反転回数を1行で出力してください。出力の末尾には改行を入れること。

入力例1

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
0

出力例1

5

入力例2

5 5
0 0 0 0 0
1 1 0 0 1
0 1 1 1 1
1 0 1 0 1
1 0 0 0 0
1
1 2

出力例2

9
C - 鏡餅

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

さまざまな大きさと色の n 個の餅が、塔のように積みあげられている。 上から t 番目の餅は、大きさが s_tで、色が c_t である（ここでは、便宜上色は整数で表される）。

鏡餅は、3つの同じ色の餅を大きい順に下から重ねたものである。 あなたは、餅の塔から鏡餅を作るために以下の操作を行う。 餅の塔の上から餅を1つづつ取り、受け取るか捨てるかのどちらかを行う。 3つ受け取るごとに、受け取った餅を順番に重ねて鏡餅を作る。 つまり、i,j,k番目(i < j < k)の餅をこの順に 受け取ったとき、 s_i > s_j > s_k かつ c_i = c_j = c_k であるなら、またその時に限って、鏡餅を1つ作ることができる。

餅の塔の情報が与えられる。最大でいくつの鏡餅をつくることができるか求めよ。

入力

入力は以下の形式で標準入力から与えられる。 
n
s_1 c_1
... 
s_n c_n
s_t,c_t は それぞれ上から t 番目の餅の大きさと色を表す ( 1 \leq t \leq n )。 どちらも整数で表される。
  • n,s_i,c_i は整数
  • 1 \leq n \leq 10^5
  • 1 \leq s_i \leq 10^9
  • 1 \leq c_i \leq 10^5

出力

作ることのできる鏡餅の個数の最大を出力せよ。出力の末尾には改行を入れること。

入力例 1

8
9 1
6 1
8 1
7 1
5 2
2 1
4 2
3 2

出力例 1

2

鏡餅を2つ作るには、たとえば以下のようにすればよい。 1,3,4番目の餅を受け取り、大きさ9,8,7で色1の鏡餅をひとつ作る。 5,7,8番目の餅を受け取り、大きさ5,4,3で色2の鏡餅をひとつ作る。

入力例 2

9
9 1
8 2
7 3
6 4
5 5
4 6
3 7
2 8
1 1

出力例 2

0

色の異なる餅を使って鏡餅をつくることはできません。

入力例 3

12
72846 3
36153 3
35490 4
825561 1
21513 3
24495 1
13460 2
8 2
358 1
466 4
6287 3
98738 4

出力例 3

1
D - 幾何問題を書こう

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

A君は、答えが無理数になりうる幾何問題を作りました。 答えが有理数であれば誤差が出ないように出力できることを学んだA君は、 答えが必ず有理数になるように工夫して、次のような問題にしました。 

体積が v の球を手に入れた。この球を削ってできるだけ大きな立方体を作りたい。
削り出せる立方体のうち、一番大きいものの一辺の長さを r 倍して答えよ。

答えはは必ず 0 でない有理数になることが保証されている。

A君はすでにこの問題のテストケースとして使う v の候補を n 個決めましたが、 困ったことに、実数 r をどう決めれば答えが有理数になるのかが分かりません。 そこで、あなたはA君にテストケース候補 v_1,...,v_n を見せてもらい、 答えが有理数になるテストケースができるだけ多くなるように 実数 r を決めてあげることにしました。 うまく実数 r を決めると、最大でいくつのテストケースを使うことができるでしょうか？

入力

入力は以下の形式で標準入力から与えられる。 
n
v_1
... 
v_n
  • n,v_i は整数
  • 1 \leq n \leq 30000
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)

出力

答えが有理数になるテストケース数の最大を一行に出力してください。出力の末尾には改行を入れること。

部分点

この問題には部分点が設定されている。
  • n\leq 2000 かつ v_i\leq 10^6 であるデータセットに 正解した場合、98点が得られる。
  • 追加制約のないデータセットに正解した場合さらに 2 点が得られ合計 100 点が得られる。

注意

有理数とは、整数 p と 0 でない整数 q を使って \(\frac{p}{q}\) と表せる数のことである。
A君の問題では、答えが 0 にならないことを保証したいので、 r は 0 としてはいけない。

入力例 1

4
1
1
125
8

出力例 1

4

例えば\(r=\sqrt[6]{\frac{3\pi^2}{4}}\)とすると、どれも有理数になります。
rの値を修正しました。(17:14)

入力例 2

3
4
32
1

出力例 2

2

例えば\(r=\sqrt[6]{3\pi^2}\)とすると、1番目と 2番めが有理数になります。
rの値を修正しました。(17:14)

入力例 3

20
90277606625
641956187000
1264908284352
91500888625
5856056872
722220853000
374787639808
1264908284352
220190972141
1264908284352
46848454976
533633182461
251078438387
5856056872
732007109000
158113535544
19764191943
1247997633984
974301462079
46848454976

出力例 3

15
E - 10進数の数列

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

花子はある数列を眺めています。

その数列に以下の操作を行います。

  1. 隣り合っていない 要素をいくつか選ぶ
  2. 数列に現れる順番を変えずに選んだ数を並べる
  3. それを十進法の数として読む

花子は、このような操作をして作ることのできない最小の正の整数がいくらなのか気になりました。

例えば、「3 0 1」という数列が与えられたとします。 花子の作ることのできる正の整数は、1,3,31です。

この場合、

  • 1は作れますが、2は数列に一つもないので作ることができません。
  • 「13」などの数字が現れる順番を無視したような正の整数は作れません。
  • 「30」や「301」のように、隣り合った数字を用いて作ることはできません。

花子のために、作ることのできない最小の正の整数を求めてください。

入力

n
d_1 d_2 d_3 ... d_n
  • 1行目に数列の長さ n (1 \leq n \leq 10000)が与えられます。
  • 2行目には、数列(d_1 d_2 ... d_n)が空白区切りで与えられます。d_i (i = 1 , ... , n ) は、0以上9以下の数字です。

出力

花子が作ることのできない最小の正の整数を出力してください。 なお、先頭に余計な0を出力しないよう注意してください。 出力の末尾には改行を入れること。

入力例1

3
3 0 1

出力例1

2

入力例2

12
1 2 1 2 3 4 5 6 7 8 9 0

出力例2

21

入力例3

20
1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 0

出力例3

100