Mujin Programming Challenge 2018

A - コンテスト名

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

コンテストの名前の候補として、英大文字からなる文字列 S が与えられます。

この文字列の先頭 5 文字が MUJIN であるかどうか判定してください。

制約

S は英大文字からなる
1 \leq |S| \leq 10

入力

入力は以下の形式で標準入力から与えられる。

出力

与えられる文字列の先頭 5 文字が MUJIN である場合は Yes 、そうでない場合は No を出力せよ。

入力例 1

MUJINPC

出力例 1

Yes

入力例 2

MUJIINPC

出力例 2

No

入力例 3

MJPC

出力例 3

No

B - セキュリティ

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

初めロボットがある部屋には A 人おり、その後人が出入りしましたが、部屋に誰もいなくなった瞬間があるかどうかが気になっています。

人の出入りを表す文字列 S が与えられます。S の i 文字目が + の場合は時刻 i に 1 人が部屋に入ってきたこと、- の場合は 1 人が部屋から出ていったことを表します。

記録が始まる前後も含めて、部屋の中が 0 人になったことがあるかどうか判定してください。

制約

0 \leq A \leq 100
1 \leq |S| \leq 100
S は + または - から成る
部屋に人がいない状態で - が記録されていることはない
A は整数

入力

入力は以下の形式で標準入力から与えられる。

A
S

出力

部屋に人がいない瞬間がある場合は Yes を、ない場合は No を出力してください。

入力例 1

3
+++---

出力例 1

No

入力例 2

4
+-----++-

出力例 2

Yes

入力例 3

0
++++

出力例 3

Yes

初め部屋には誰もいなかったので、Yes を出力します。

C - 右折

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

N 行 M 列のマス目があります。上から i 行目、左から j 列目にあるマスを (i,j) で表します。特に、左上のマスは (1,1) であり、右下のマスは (N,M) です。マス目の状態は二次元配列 s で表され、s_{ij} が # のときマス (i,j) には障害物があり、. のとき障害物がないことを表します。

高橋君は、このマス目のいずれかのマスに、上下左右いずれかの方向を向けたロボットを置きました。ロボットは向いている方向に 1 マス以上まっすぐ進んだ後、向きを右に 90 度変え、再びまっすぐに 1 マス以上進んで停止しました。この過程でロボットが通ったマス(置かれたマスおよび停止したマスを含む)のいずれにも障害物はなく、またロボットがマス目の外に出ることはありませんでした。

ロボットが置かれたマスと停止したマスの順序対としてありうるものの個数を求めてください。

制約

2 \leq N,M \leq 2\times 10^3
s_{ij} は # または . である

入力

入力は以下の形式で標準入力から与えられる。

N M
s_{11}...s_{1M}
:
s_{N1}...s_{NM}

出力

ロボットが置かれたマスと停止したマスの順序対としてありうるものの個数を出力せよ。

入力例 1

3 3
..#
...
#.#

出力例 1

((1,1),(2,2)),((1,1),(3,2)),((1,2),(2,1)),((2,1),(1,2)),((2,1),(3,2)),((2,2),(1,1)),((2,3),(1,2)),((2,3),(1,1)),((3,2),(2,3)) の 9 個が条件を満たします。

入力例 2

2 5
.#.#.
..#..

出力例 2

入力例 3

6 8
#......#
##....##
#.#..#.#
#..##..#
#......#
#......#

出力例 3

D - うほょじご

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

正の整数 x に対し、rev(x) で x を 10 進表記してできる文字列を反転したものを 10 進表記に持つ整数を表します。例えば、rev(123)=321,rev(90)=9,rev(5)=5 です。

正の整数 N,M が与えられます。1\leq x\leq N, 1\leq y\leq M なる整数の組 (x,y) であって、 (x,y) から始めることで以下の一連の操作を無限に繰り返すことができるものの個数を求めてください。

x,y のいずれかが 0 なら、終了する
x < y なら x を rev(x) で、そうでないなら y を rev(y) で置き換える。
上の操作後、x < y となっていれば y を y-x で、そうでなければ x を x-y で置き換える。

制約

1\leq N,M\leq 999
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

N M

出力

整数の組 (x,y) であって、(x,y) から始めることで操作を無限に繰り返すことができるものの個数を出力せよ。

入力例 1

13 13

出力例 1

(13,13) が条件を満たします。具体的には、操作は (13,13)→(13,18)→(13,18)→...... と続きます。

入力例 2

20 30

出力例 2

入力例 3

314 159

出力例 3

E - 迷路

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 行 M 列のマス目があります。上から i 行目、左から j 列目にあるマスを (i,j) で表します。特に、左上のマスは (1,1) であり、右下のマスは (N,M) です。

マス目の状態は二次元配列 s で表され、s_{ij} が # のときマス (i,j) には障害物があり、. または S または G のとき障害物はありません。

ロボットは 0 秒にS のマスからスタートし、 G のマスに出来るだけ短い時間で辿り着こうとします。

しかしロボットは常にどの方向にも動けるというわけではありません。

長さ K の文字列 d が与えられます。毎秒、ロボットは隣接するマスに移動するか、今いるマスにとどまることができます。ただし、t 秒後から t+1 秒後にかけては、t を K で割った余りを r (0 \leq r \leq K-1) として、 d_{r+1} の方向にのみ 1 秒かけて 1 マス進むことが出来ます。現在いるマスを (i,j) とした時、d_{r+1} が U の場合は (i-1,j) に、 D の場合は (i+1,j) に、L の場合は (i,j-1) に、 R の場合は (i,j+1) に移動できます。マス目の外に出るような移動や、障害物があるマスへの移動は出来ません。

この条件のもとで S からG のマスに辿り着くまでの最短の時間を求めてください。

制約

2 \leq N,M \leq 1000
1 \leq K \leq 100000
s は # または . または S または G からなる
S と G の書かれたマスはそれぞれ 1 つずつ存在する
d の長さは K
d は U または D または L または R からなる
N,M,K は整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K
d_{1}...d_{K}
s_{11}...s_{1M}
:
s_{N1}...s_{NM}

出力

ロボットが S から G まで移動するのにかかる最短の時間を出力せよ。ただし、どのように移動しても S から G まで移動出来ない場合は -1 を出力せよ。

入力例 1

2 3 5
UDRRL
S..
.#G

出力例 1

入力例 2

3 3 5
UDUDD
S..
...
.G.

出力例 2

-1

どのように移動しても 2 列目に移動出来ません。

入力例 3

3 3 5
UDLRD
S..
.#.
..G

出力例 3

F - チーム分け

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 人を、それぞれの人がただ 1 つのチームに属するようにチーム分けを行います。

しかし、人によっては多くの人が属するチームに属したくないと考えています。

この条件は N 要素からなる整数列 a で表され、i 番目の人は a_{i} 人以下から成るチームに配属されることになります。

チーム分けをするに当たってこのようなチーム分けは何通り考えられるのかを計算したくなりました。答えは非常に大きくなることがあるので、998244353 で割ったあまりを出力してください。ただし、2 つのチーム分けが異なるとは、ある 2 人が存在して、片方のチーム分けでは同じチームに属するがもう片方のチーム分けでは違うチームに属する、という場合を表します。

制約

1 \leq N \leq 1000
1 \leq a_i \leq N
入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_{N-1} a_N

出力

条件を満たすチーム分けの方法の場合の数を 998244353 で割ったあまりを出力せよ。

入力例 1

1
1

出力例 1

1 人をチーム分けする方法は 1 通りです。

入力例 2

3
3 3 2

出力例 2

条件を満たすチーム分けは、((1),(2),(3)), ((1,2),(3)), ((1,3),(2)), ((2,3),(1)) の 4 通りです。

入力例 3

10
3 1 4 1 5 9 2 6 3 10

出力例 3

G - 移動

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

この問題では Q 個のクエリが与えられます。i 個目のクエリは 7 つの整数 a_i,b_i,c_i,d_i,e_i,f_i,k_i で表されます。クエリ毎に、x_1=a_i,y_1=b_i,x_2=c_i,y_2=d_i,x_3=e_i,y_3=f_i,K=k_i として以下の問題を解いた答えを出力してください。

ロボットが 1 台あり、時刻 0 には xy 平面上の点 (0,0) にいます。ロボットはいずれも (0,0) でなくどの 2 つの向きも全く同じでも正反対でもない 3 つのベクトル (x_1,y_1),(x_2,y_2),(x_3,y_3) を持っており、以下の規則で移動します。

時刻 t にロボットがいる座標を (x,y) とすれば、時刻 t+1 には、ロボットは座標 (x,y),(x+x_1,y+y_1),(x+x_2,y+y_2),(x+x_3,y+y_3) のいずれかにいる。

非負整数 K が与えられます。時刻 K にロボットがいる点としてありうるものの個数を 998244353 で割ったあまりを求めてください。

制約

1 \leq Q \leq 10^4
0 \leq |a_i|,|b_i|,|c_i|,|d_i|,|e_i|,|f_i| \leq 10^9
0 \leq k_i \leq 10^9
各 i に対し、(a_i,b_i),(c_i,d_i),(e_i,f_i) はいずれも (0,0) でなく、かつこれらのうちのどの 2 つも同じ向きを向いておらず、どの 2 つも全く正反対の向きを向いていない。より正確には、どの 2 つの外積も 0 でない
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

Q
a_1 b_1 c_1 d_1 e_1 f_1 k_1
:
a_Q b_Q c_Q d_Q e_Q f_Q k_Q

出力

各クエリに対し、時刻 K にロボットがいる点としてありうるものの個数を 998244353 で割ったあまりを出力せよ。

入力例 1

9
1 0 0 1 1 1 3
1 0 0 1 -1 -1 3
3 1 4 1 5 9 265
77162 -78112 -90809 -88927 99617 -89012 1000000000
123 456 789 -123 -456 -789 987654321
0 1 2 3 4 5 0
10000000 10000000 20000000 30000000 -50000000 -80000000 130000000
123456789 442514372 -902777152 -78816277 -887267123 667261667 908855261
1 2 3 4 5 6 7

出力例 1

最初のクエリでは、時刻 3 にロボットがいる点としてありうるものは (x,y)(0\leq x,y\leq 3) とあらわされる点であり、これは 16 個あります。 2 番目のクエリでは、時刻 3 にロボットがいる点としてありうるものは (-3,-3),(-2,-2),(-2,-1),(-1,-2),(-1,-1),(-1,0),(-1,1),(0,-1),(0,0),(0,1),(0,2),(0,3),(1,-1),(1,0),(1,1),(1,2),(2,0),(2,1),(3,0) の 19 個です。

H - タイル張り

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

H\times W のマス目のすべてのマスを白か黒で塗る方法であって、以下の条件を満たすように 1\times 2 のタイル何枚かを(必要ならそのうち何枚かを回転させて)置くことができるようにする方法の個数を 998244353 で割ったあまりを求めてください。

タイルはマス目からはみ出してはならず、また異なるタイル同士が重なってはならない。
全てのタイルは、マス目のちょうど 2 マスを完全に覆う。
白く塗られたすべてのマスは、ちょうど 1 枚のタイルによって覆われている。
黒く塗られたすべてのマスは、タイルに覆われていない。

制約

1 \leq H \leq 5
1 \leq W \leq 10^9
入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。

H W

出力

条件を満たす塗り分けの個数を出力せよ。

入力例 1

2 2

出力例 1

全てのマスを白く塗る 1 通り、全てのマスを黒く塗る 1 通り、隣接する 2 マスを黒く塗り、残りの 2 マスを白く塗る 4 通りの合計 6 通りが条件を満たします。

入力例 2

3 4

出力例 2

入力例 3

5 100

出力例 3

655553721