AtCoder Regular Contest 039

A - A - B problem

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は次のような問題を考えました。

3 桁の整数 A、B が与えられるので A - B を求める。

しかしあまりにも簡単すぎるので、ちょっと変更して次のような問題にしました。

3 桁の整数 A、B が与えられる。
A と B のどちらかを 1 桁だけ書き換えてもよい時の、A - B の答えになり得る整数の最大値を求める。

なお、一番上の桁が 0 であるような整数へと書き換えることはできません。例えば 123 を 023 へと書き換えたりすることはできません。

高橋君は自信満々であなたへとこの問題を出題してきました。ぜひ挑戦してみてください。

入力

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

A B

1 行に 2 つの整数 A(100 ≦ A ≦ 999)、B(100 ≦ B ≦ 999) が空白区切りで与えられる。

出力

A、B のどちらかを 1 桁だけ書き換えてもよい時の、A - B の答えになり得る整数の最大値を 1 行に出力せよ。出力は標準出力に行い、末尾に改行を入れること。

入力例1

567 234

出力例1

A を 567 から 967 に書き換えれば A-B は 733 となり、この値が A-B の最大値となっています。

入力例2

999 100

出力例2

どちらも書き換えない時に A-B が最大値となることもあります。

入力例3

100 999

出力例3

-99

答えは負になることもあります。

B - 高橋幼稚園

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は幼稚園の先生です。高橋君は N 人の児童にちょうど K 個のキャンディを配り切ることにしました。

ここで、全体の幸福度を、各児童が貰ったキャンディの個数の積として定義します。

高橋君は N 人の児童にキャンディを配り切ったときの、全体の幸福度を最大化したいと思っています。全体の幸福度を最大化するようなキャンディの分配方法が何通りあるかを数えてください。答えは大きくなる可能性があるので答えを 1,000,000,007(10^9+7) で割った余りを出力してください。

各児童に配られたキャンディの個数が 1 つでも異なっていれば、配り方は区別されます。児童は区別され、キャンディは区別されません。また、定義からキャンディを 1 つも貰えない児童が 1 人でもいると、全体の幸福度は 0 になることに気をつけてください。

入力

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

N K

1 行目には、児童の数とキャンディの数を表す 2 つの整数 N (1 ≦ N ≦ 100) と K (1 ≦K ≦ 500) が空白区切りで与えられる。

部分点

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

80 点分のテストケースでは、問題文の制約に加え、さらに N≦K を満たす。
残りの 20 点分のテストケースに追加の制約はない。

出力

出力は以下の形式で標準出力に行うこと。

1 行目に、求める答えを 1,000,000,007 で割った余りを出力せよ。

末尾の改行を忘れないこと。

入力例1

4 10

出力例1

4 人の児童のうち、2 人にキャンディを 3 個ずつ、残りの 2 人にキャンディを 2 個ずつ配ると、全体の幸福度が 3×3×2×2=36 となり、またこの時最大値を達成しています。

そのような配り方は、4 人の児童に配られたキャンディの数を c_1,c_2,c_3,c_4 とすると、(c_1,c_2,c_3,c_4) が

(3,3,2,2)
(3,2,3,2)
(3,2,2,3)
(2,3,3,2)
(2,3,2,3)
(2,2,3,3)

となるような配り方であり、6 通り存在します。

入力例2

100 450

出力例2

538992043

出力するものは、本来の答えを 1,000,000,007 で割った余りだということに気をつけてください。

入力例3

5 2

出力例3

どうキャンディを配っても全体の幸福度が 0 になるので、どう配っても良いです。

C - 幼稚園児高橋君

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

無限に広がる二次元格子があります。原点 (0,0) から右に x、上に y 進んだ格子点の座標を (x,y) と表します。

幼稚園児の高橋君はこの格子上で好き放題に動くのが好きです。しかし、あまりにも好き勝手に動くせいで行方不明になってしまいました。高橋君は以下の行動をしたことが調査により分かっています。

最初、高橋君は (0,0) にいました。
高橋君は好きな方向(上下左右)を決めて、その方向に直進します。そして、今までに訪問していない格子点を踏むまで直進し続けます。訪問していない格子点を踏むといったん止まります。
そして、高橋君は疲れるまで上記の操作を繰り返し、疲れると、その格子点で寝てしまいました。

保護者であるあなたは、高橋君がちょうど K 回方向を決めて直進したこと、そして各時点でどの方向に直進したかを知ることができました。あなたは、プログラムを書いて高橋君が寝ている場所を突き止めることにしました。

入力

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

K
S_1S_2S_3…S_K

1 行目には、高橋君が移動した回数を表す整数 K (1≦K≦200,000) が与えられる。
2 行目には、高橋君の移動の情報を表す K 文字の情報が与えられる。そのうち i(1≦i≦K) 番目の文字 S_i は i 回目の移動でどの方向に直進したかを表している。S_i が L,R,U,D のときそれぞれ i 回目の移動で左、右、上、下方向に直進したことを表す。

出力

出力は以下の形式で標準出力に行うこと。

1 行目に、2 つの整数 x,y を出力せよ。これは高橋君の寝ている場所の座標が (x,y) であることを表す。

末尾の改行を忘れないこと。

入力例1

3
RLU

出力例1

-1 1

高橋君がいったん止まった格子点を開始地点も含めて順番に列挙すると、(0,0)→(1,0)→(-1,0)→(-1,1) となります。

入力例2

7
RURDRUL

出力例2

0 1

入力例3

25
RLRLRLRLRLRLURLRLRLRLRLRL

出力例3

-12 1

D - 旅行会社高橋君

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋君とあなたはTK国でHS会社という旅行会社を経営しています。 TK国は N 個の頂点と M 本の辺からなる連結な単純無向グラフです。各頂点にはそれぞれ 1 から N の番号が振られています。

HS会社では、顧客ごとに旅行計画を立てて提供するサービスを行っています。これまでは、旅行計画を温もりのある手作業で作成していました。ですが突然の旅行ブームがTK国に訪れ、ナウでヤングな若者は皆旅行をするようになりました。もちろん会社は大忙し、とうとうコンピューターに頼ることにしました。

HS会社では、顧客から始点、中継点、終点という 3 つの頂点を与えられるので、始点から中継点を通り終点へと到着するような旅行計画を提供しています。ただし、顧客が退屈しないように、同じ辺を複数回通るような旅行計画は提供しないようにしています。同じ頂点を複数回通る事に制限はありません。つまり旅行計画は、始点から中継点を通り終点に到着するトレイルです。

あなたはとりあえず、顧客ごとにそのような旅行計画は存在するのかどうかだけを判別するプログラムを書くことにしました。

入力

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

N M
X_1 Y_1
X_2 Y_2
:
X_M Y_M
Q
A_1 B_1 C_1
A_2 B_2 C_2
:
A_Q B_Q C_Q

1 行目は 2 つの整数 N(3 ≦ N ≦ 100,000)、M(1 ≦ M ≦ 200,000) が空白区切りで与えられ、これはTK国の頂点数と辺数を表す。
2 行目からの M 行は辺の情報を表す。そのうち i 行目には 2 つの整数 X_i、Y_i が空白区切りで与えられ、これは i 番目の辺が頂点 X_i(1 ≦ X_i ≦ N) と頂点 Y_i(1 ≦ Y_i ≦ N) を結んでいることを表す。
2+M 行目には、 1 つの整数 Q(1 ≦ Q ≦ 100,000) が与えられる。これはプログラムに旅行計画が存在するかを判定させたい顧客が Q 人いることを表す。
3+M 行目からの Q 行は顧客の情報を表す。そのうち i 行目は 3 つの整数 A_i、B_i、C_i が空白区切りで与えられ、これは i 番目の顧客に与えられた始点、中継点、終点がそれぞれ頂点 A_i(1 ≦ A_i ≦ N)、頂点 B_i(1 ≦ B_i ≦ N)、頂点 C_i(1 ≦ C_i ≦ N) であることを表す。
TK国は連結なグラフである。
TK国は単純なグラフである、つまり多重辺や自己辺は存在しない。
A_i、B_i、C_i は互いに異なる。

出力

Q 行出力せよ。そのうち i 行目は i 番目の顧客の旅行計画が存在するなら OK、存在しないならば NG である。出力は標準出力に行い、末尾に改行を入れること。

入力例1

出力例1

OK
NG
OK
OK

以下にこの入力でのTK国を図示する。

一例として、

1 番目の顧客には 1 - 2 - 3
3 番目の顧客には 2 - 3 - 5 - 4 - 3
4 番目の顧客には 3 - 4 - 5

という旅行計画が提供できる。

また、 2 番目の顧客に提供できる旅行計画は存在しない。

入力例2

出力例2

NG
OK
OK
OK
OK
NG
NG
OK
NG
NG
NG

以下にこの入力でのTK国を図示する。

入力例3

出力例3

OK
OK
NG
OK
OK
NG
NG
OK
OK
OK

以下にこの入力でのTK国を図示する。