AtCoder Regular Contest 035

A - 高橋くんと回文

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くんは、ある文字列を持っていました。あるとき、Cat Snuke がやってきて文字列の一部を食べてしまいました。

高橋くんは元の文字列が回文であった可能性があるかを知りたいです。そこで、食べられた文字を適切に埋め合わせて、回文とすることができるか調べてください。食べられた文字それぞれを、どの文字で埋め合わせるかは自由に決められます。

入力

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

Cat Snuke に食べられた後の文字列 s (1 ≦ \|s\| ≦ 1,000) が 1 行で与えられる。ただし、\|s\| は文字列 s の長さを表す。
文字列 s は英小文字、または * から成ることが保証される。* は食べられた文字を表す。それ以外の文字は、元の文字列の文字を表す。

出力

元の文字列が回文であった可能性があるならば YES 、可能性がないならば NO と標準出力に出力せよ。

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

入力例1

ab*

出力例1

YES

* を a で埋め合わせると、aba となるので、元の文字列は回文であった可能性がある。

入力例2

abc

出力例2

NO

abc は回文ではない。

入力例3

a*bc*

出力例3

YES

acbca と埋め合わせると回文となる。

入力例4

***

出力例4

YES

B - アットコーダー王国のコンテスト事情

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くん様は、アットコーダー王国の王様です。

プログラミングコンテスト好きな彼が統治するアットコーダー王国では、年に一度コンテストが開催されます。

このコンテストでは N 問の問題が出題されます。また、順位を付ける際の 1 つの要素としてペナルティというものが存在します。ある問題を正解したとき、コンテスト開始から経過した時間分だけのペナルティが、各問題ごとに発生します。そして、その発生したペナルティの総和がコンテストペナルティとなります。ARCのペナルティとは異なるルールであることに注意してください。

非常に優秀な国民である貴方には、全ての問題を解く力があります。しかも、全ての問題について、その問題を正解するためにどれだけ時間をかければよいのかを知っており、ちょうどその時間取り組むと必ず正解することができます。

貴方は、自由な順番で問題を解くことができるので、コンテストペナルティが最小となるように解こうと思いました。

全ての問題を解くときのコンテストペナルティの最小値と、そのような解き方が何通りあるかを 1,000,000,007(10^9+7) で割った余りを答えて下さい。

入力

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

N
T_1
T_2
:
T_N

1 行目には、コンテストでの問題数を表す整数 N (1 ≦ N ≦ 10,000) がスペース区切りで与えられる。
2 行目からの N 行には、各問題を解くのにかかる時間の情報が与えられる。そのうち i (1≦i≦N) 行目には、整数 T_i (1≦T_i≦10,000) が書かれており、i 番目の問題を解くのに T_i 分かかることを示す。

部分点

この問題には部分点が存在する。

100 点中 50 点分のテストケースにおいて、コンテストペナルティが最小となるような解き方の数は 1 通りである。

出力

出力は以下の形式で標準出力に出力せよ。

1 行目には、コンテストペナルティの最小値を出力せよ。32bit整数型ではオーバーフローする可能性があることに気をつけること。
2 行目には、コンテストペナルティが最小となるような解き方の数を 1,000,000,007(10^9+7) で割った余りを出力せよ。

入力例1

2
20
10

出力例1

40
1

2 番目の問題を解いてから 1 番目の問題を解くのがよい。

コンテストが開始する(時刻：0 分)。
10 分後、2 番目の問題に正解する(時刻：10 分)。この時点で発生するペナルティは 10 分である。
その 20 分後、1 番目の問題に正解する(時刻： 30 分)。この時点で発生するペナルティは 30 分である。

コンテストペナルティは 40(=10+30) 分となる。

入力例2

出力例2

21
12

入力例3

出力例3

91
227020758

どのような順番で解いても良い。余りを取るのを忘れないこと。

C - アットコーダー王国の交通事情

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋くん様は、アットコーダー王国の王様です。彼が統治するアットコーダー王国は、1 から N までの番号が付けられた N 個の都市とそれらを結ぶ双方向に行き来可能な M 本の道路からなります。それぞれの道路には長さがあります。アットコーダー王国の任意の都市の組み合わせ (A,B) について、A からいくつかの道路を辿って B に辿り着けることが保障されています。

高橋くん様は、アットコーダー国民の幸せが、交通の利便性に大きく依存していると考えています。国民がどれくらい幸せかを調べるために、ありうる全ての都市間の最短経路長の総和 S を求めたいと思っています。

都市 i と j の間の最短経路長を D(i,j) とすれば S は、

と表されます。

また、高橋くん様は公共事業で、K 本の新たな道路を建設しようと思っています。この建設によって、ある都市間を直接結ぶ道路が 2 本以上存在してしまうことがありますが、その場合、既にある道路は取り壊さず、新しく追加します。

あなたの仕事は、新たな道路を与えられた順番に建設していき、建設の度に前述の S を計算するプログラムを書くことです。

入力

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

N M
A_1 B_1 C_1
A_2 B_2 C_2
:
A_M B_M C_M
K
X_1 Y_1 Z_1
:
X_K Y_K Z_K

1 行目には、都市の数と道路の数を表す 2 つの整数 N (1 ≦ N ≦ 400) と M (1 ≦M ≦ 1000) がスペース区切りで与えられる.
2 行目からの M 行には、既存の道路の情報が与えられる。そのうち i (1≦i≦M) 行目には、i 番目の道路の情報を表す 3 つの整数 A_i(1≦A_i≦N)、 B_i(1≦B_i≦N)、 C_i(1≦C_i≦1,000) がスペース区切りで与えられる。これは、i 番目の道路が都市 A_i と B_i を距離 C_iで結んでいることを表す。A_i≠B_i であり、同じ都市間を直接結ぶ道路は高々 1 つである。
任意の都市の組み合わせ (A,B) について、A からいくつかの道路を辿って B に辿り着けることが保障されている。
2+M 行目には、新たに建設する道路の数を表す K (1≦K≦400) が書かれている。
3+M 行目からの K 行には、新たに建設する道路の情報が与えられる。そのうち i (1≦i≦K) 行目には、i 番目の新たな道路の情報を表す 3 つの整数 X_i(1≦X_i≦N)、 Y_i(1≦Y_i≦N)、 Z_i(1≦Z_i≦1,000) がスペース区切りで与えられる。i 番目の新たな道路が都市 X_i と Y_i を距離 Z_i で結ぶことを表す。X_i≠Y_i である。

出力

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

i (1≦i≦K) 行目には、i 番目までの新たな道路を建設した直後の、ありうる全ての都市間の最短経路長の総和 S を出力せよ。

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

入力例1

出力例1

10
8

初期状態は以下の通りです。

一度目の建設の直後、グラフは以下のようになります。

二度目の建設の直後、グラフは以下のようになります。

入力例2

出力例2

D - 高橋くんとマラソンコース

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

高橋くんはマラソン大会の主催者で、今度開くマラソン大会の計画案を練っています。高橋くんの住む街には東西と南北に伸びるそれぞれ 10^6 本の道があり、南北に伸びる道のうち西から x 番目の道と、東西に伸びる道のうち南から y 番目の道が交わる交差点を (x,y) と表します。

マラソンコースの作りを簡単にするため、道は東か北の方向へのみ進めるようにしました。高橋くんはマラソンコースで参加者のタイム計測に使える場所として、N 個のチェックポイント (p_i,q_i) を決めました。

高橋くんの街では、参加者はマラソン大会で一人ひとりが違った経路を取りたがるため、コースの異なる経路の数が重要です。タイム計測の必要から、チェックポイント u からチェックポイント v (u < v) までマラソンコースを設定したとき、u≦i≦v となるチェックポイント i 全てを参加者は通る必要があります。

そこで、高橋くんは以下の Q 個のクエリに答える必要があります。

k_j 番目のチェックポイントの場所を (a_j,b_j) に変更する。
チェックポイント l_{1j} からチェックポイント r_{1j} までの異なる経路の総数と、チェックポイント l_{2j} からチェックポイント r_{2j} までの異なる経路の総数のうち、どちらが大きいかを判定する。ただし、経路の数のうち多い方は、少ない方の 2 倍以上はあることが保証される。

高橋くんを助けるためのプログラムを書いてください。

入力

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

N
p_1 q_1
p_2 q_2
:
p_N q_N
Q
t_1 …
:
t_Q …

1 行目には、チェックポイントの数を表す整数 N (2 ≦ N ≦ 2*10^5) が与えられる。
2 行目からの N 行には、チェックポイントの位置を表す整数 p_i, q_i(1 ≦ p_i, q_i ≦ 10^6) が空白区切りで与えられる。
N+2 行目には、クエリの数を表す整数 Q( 1 ≦ Q ≦ 2*10^5) が与えられる。
N+3 行目から Q 行には、クエリが与えられる。t_j は j 番目のクエリの種類を表す。
t_j = 1 のとき、その行に k_j, a_j, b_j(1 ≦ k_j ≦ N, 1 ≦ a_j, b_j ≦ 10^6) が空白区切りで与えられる。
t_j = 2 のとき、その行に l_{1j}, r_{1j}, l_{2j}, r_{2j} (1 ≦ l_{1j} < r_{1j} ≦ N, 1 ≦ l_{2j} < r_{2j} ≦ N ) が空白区切りで与えられる。
任意の i(1 ≦ i ≦ N-1) に対し、チェックポイント i からチェックポイント i+1 までの経路が常に（クエリでチェックポイントの場所が変更されても）1 つは存在することが保証される。また、チェックポイントの位置が重なることはない。

部分点

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

30 点分のテストケースにおいて、2≦N≦1,000, 1≦Q≦1,000 を満たす。

出力

種類 2 のクエリに対する答えを 1 行ずつクエリの与えられた順に出力せよ。チェックポイント l_{1j} からチェックポイント r_{1j} までの経路のほうが多い時は FIRST、チェックポイント l_{2j} からチェックポイント r_{2j} までの経路のほうが多い時は SECOND と出力せよ。

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

入力例1

出力例1

FIRST
SECOND
FIRST

1 番目のクエリでは、チェックポイント1 からチェックポイント3 までの経路の数は、以下のように 5 つである。

チェックポイント 3 からチェックポイント 4 までの経路の数は、以下のように 2 つである。

よって、FIRST と出力する。

2 番目のクエリでは、経路の数はそれぞれ 5 と 10 なので、SECOND と出力する。

3 番目のクエリでチェックポイント 2 の位置が変更された後、4 番目のクエリでは、経路の数はそれぞれ 10 と 2 なので、FIRST と出力する。

入力例2

出力例2

FIRST
FIRST
FIRST

比べる数は非常に大きくなることに注意してください。