AtCoder Beginner Contest 035

A - テレビ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は画面の幅が W 、高さが H のテレビを持っています。

このテレビの画面アスペクト比 W:H が 4:3 か 16:9 か判定してください。

入力

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

W H

1 行目にテレビの画面の幅と高さを表す 2 つの整数 W,H (1≦H<W≦10^5) が空白区切りで与えられる。
テレビの画面アスペクト比は 4:3 か 16:9 になることが保証される。

出力

高橋君のテレビの画面アスペクト比 W:H が 4:3 ならば4:3を、 16:9 ならば 16:9 を 1 行に出力せよ。改行を忘れないこと。

入力例 1

4 3

出力例 1

4:3

画面の幅が 4 、高さが 3 のテレビの画面アスペクト比は 4:3 なので4:3と出力してください。

入力例 2

16 9

出力例 2

16:9

画面の幅が 16 、高さが 9 のテレビの画面アスペクト比は 16:9 なので16:9と出力してください。

入力例 3

28 21

出力例 3

4:3

B - ドローン

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

無限に広い二次元グリッドの原点 (0, 0) に高橋君と 1 台のドローンがいます。このドローンは文字列が与えられた時、文字列の先頭から末尾までのそれぞれの文字を 1 つの命令と解釈して順に実行します。命令は以下の 4 種類です。

L 現在のドローンの位置を (x, y) として (x-1, y) に移動する
R 現在のドローンの位置を (x, y) として (x+1, y) に移動する
U 現在のドローンの位置を (x, y) として (x, y+1) に移動する
D 現在のドローンの位置を (x, y) として (x, y-1) に移動する

今、ドローンに何らかの命令が与えられ、どこかへと移動しました。高橋君はドローンに送られた命令を表す文字列である S を手に入れたものの、いくつかの箇所は破損し?になり分からなくなってしまいました。ただし、?が元々はL、R、U、Dのいずれかの文字だったことが分かっています。

ドローンと高橋君の距離はドローンの位置を (x,y) としてマンハッタン距離 |x|+|y| で表されます。求める値の種類を表す整数 T が与えられるので、移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、 T=1 ならば最大値を、 T=2 ならば最小値を求めてください。

入力

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

S
T

1 行目にドローンに与えられた命令を表す文字列 S(1≦|S|≦10^5) が与えられる。ここで、 |S| は文字列 S の長さを表す。
S はL、R、U、D、?の 5 種類の文字のみからなる。
2 行目に求める値の種類を表す整数 T (1≦T≦2) が与えられる。

出力

T=1 ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最大値を 1 行に出力せよ。
T=2 ならば移動を終えたあとのドローンと高橋君の距離としてありうる値のうち、最小値を 1 行に出力せよ。
改行を忘れないこと。

部分点

この問題には部分点が設定されている。

T=1 のデータセットに全て正解した場合 100 点が与えられる。
追加制約のないデータセットに正解した場合、追加で 1 点が与えられ、合計 101 点が得られる。

入力例 1

UL?
1

出力例 1

ドローンが最終的にいる可能性がある位置は (-2,1), (-1,0), (-1,2), (0,1) の 4 つです。ドローンと高橋君の距離 |x|+|y| のうち最大値は 3 となります。
このケースは部分点の追加制約を満たします。

入力例 2

UD?
1

出力例 2

ドローンが最終的にいる可能性がある位置は (1,0), (-1,0), (0,1), (0,-1) の 4 つです。ドローンと高橋君の距離 |x|+|y| のうち最大値は 1 となります。
このケースは部分点の追加制約を満たします。

入力例 3

UUUU?DDR?LLLL
1

出力例 3

このケースは部分点の追加制約を満たします。

入力例 4

UULL?
2

出力例 4

このケースは部分点の追加制約を満たしません。

C - オセロ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

黒の面に0、白の面に1が書かれた N 個のオセロの駒が、どの駒も黒の面が上を向くように一列に並べられています。その後、ある区間にある駒を全て裏返すという操作が Q 回だけ行なわれました。具体的には i 回目の操作においては、左から l_i 番目の駒から r_i 番目の駒までの駒全てが裏返されました。

最終的な盤面を求めてください。

入力

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

N Q
l_1 r_1
.
.
.
l_Q r_Q

1 行目に駒の数と操作回数を表す 2 つの整数 N,Q (1≦N,Q≦200,000) が空白区切りで与えられる。
2 行目から続く Q 行のうち i 行目においては、 i 回目の操作の範囲を表す 2 つの整数 l_i, r_i (1≦l_i≦r_i≦N) が空白区切りで与えられる。

出力

最終的な盤面を表す文字列 S を 1 行に出力せよ。 S の左から i 文字目は左から i 番目の駒の上向きの面に書かれた数字となる。改行を忘れないこと。

部分点

この問題には部分点が設定されている。

1≦N,Q≦2,000 を満たすデータセットに正解した場合、 60 点が与えられる。
追加制約のないデータセットに正解した場合は、追加で 40 点が与えられ、合計 100 点が得られる。

入力例 1

出力例 1

盤面ははじめ00000です。
1 回目の操作により、盤面は11110となります。
2 回目の操作により、盤面は10001となります。
3 回目の操作により、盤面は10101となります。
4 回目の操作により、盤面は01010となります。
最終的な盤面である01010が求める答えです。
このケースは部分点の追加制約を満たします。

入力例 2

出力例 2

10110000011110000000

このケースは部分点の追加制約を満たします。

D - トレジャーハント

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋君が住む国には N 箇所の町と町同士をつなぐ一方通行の道が M 本あり、それぞれの町には 1 から N の番号が割りふられています。 i 番目の道は a_i 番の町から b_i 番の町へ移動することが可能であり、移動に c_i 分だけかかります。

所持金が 0 円の高橋君は T 分間のトレジャーハントに出かけることにしました。高橋君は開始 0 分の時点で 1 番の町にいます。また、開始から T 分の時点にも 1 番の町にいなくてはなりません。高橋君が i 番の町に 1 分間滞在すると、 A_i 円が高橋君の所持金に加算されます。

T 分間のトレジャーハントによって高橋君の所持金は最大いくらになるか求めてください。

入力

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

N M T
A_1 … A_N
a_1 b_1 c_1
.
.
.
a_M b_M c_M

1 行目に町の数と道の数、トレジャーハントの分数を表す 3 つの整数 N,M,T (2≦N≦10^5, 1≦M≦min(N(N-1),10^5), 1≦T≦10^9) が空白区切りで与えられる。
2 行目には i 番目の町に滞在したときに得られるお金の情報を表す整数 A_i(1≦A_i≦10^5) が空白区切りで与えられる。
3 行目から続く M 行のうち i 行目においては、 i 番目の道の情報を表す 3 つの整数 a_i, b_i, c_i (1≦a_i,b_i≦N,a_i≠b_i, 1≦c_i≦10^5)が空白区切りで与えられる。
i≠j であるような i,j において、a_i≠a_j または b_i≠b_j のどちらかが成立する。

出力

トレジャーハントの結果としてありうる高橋君の所持金のうち最大値を 1 行に出力せよ。改行を忘れないこと。

部分点

この問題には部分点が設定されている。

1≦N≦200 を満たすデータセットに正解した場合 50 点が与えられる。
追加制約のないデータセットに正解した場合は、追加で 50 点が与えられ、合計 100 点が得られる。

入力例 1

出力例 1

開始から 0 分の時点から 2 分かけて町 1 から町 2 に移動します。
開始から 2 分の時点から 2 分間、町 2 に滞在します。所持金は 6 円になります。
開始から 4 分の時点から 1 分かけて町 2 から町 1 に移動します。
開始から 5 分の時点で町 1 にいます。トレジャーハントが終了します。
このケースは部分点の制約を満たします。

入力例 2

出力例 2

開始 0 分の時点から 3 分間、町 1 に滞在するのが最適であり、所持金を 3 円にすることができます。
このケースは部分点の制約を満たします。

入力例 3

8 15 120
1 2 6 16 1 3 11 9
1 8 1
7 3 14
8 2 13
3 5 4
5 7 5
6 4 1
6 8 17
7 8 5
1 4 2
4 7 1
6 1 3
3 1 10
2 6 5
2 4 12
5 1 30

出力例 3

このケースは部分点の制約を満たします。