A - ニコニコ文字列２

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ある文字列 A について、A="25" または A="2525" または A="252525" ... というふうに "25" を何回か繰り返した文字列になっているとき、A はニコニコ文字列であるといいます。たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

ニワンゴ君があるサイトで使っているパスワードは、0 から 9 の数字から成る長さ N の文字列です。しかし、ニワンゴ君はパスワードの一部を忘れてしまいました。ニコニコ文字列となるような連続した部分文字列をパスワードの文字列から取り出す方法が X 通り以上あることは覚えています。ただし、文字列として同じであっても、取り出し位置が異なっていれば別々に数えたものとします。

パスワードとして考えられる文字列の個数を 1,000,000,007 (10^9+7) で割った余りを求めてください。

入力

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

N X
S
  • 1 行目には、2 つの整数 N (1 ≦ N ≦ 252), X (0 ≦ X ≦ 252) が空白区切りで与えられる。これは、パスワードの長さが N であり、ニコニコ文字列となるような連続した部分文字列を取り出す方法が X 通り以上であるということを表す。
  • 2 行目には、パスワードの情報を表す 1 つの文字列 S が与えられる。S は、0 から 9 の数字と ? のみから成る長さ N の文字列であり、S の i 文字目が、
    • 数字である場合、パスワードの i 文字目がその数字であることを表す。
    • ? である場合、パスワードの i 文字目がどの数字であるかが分からないということを表す。

出力

パスワードとして考えられる文字列の個数を 1,000,000,007 (10^9+7) で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3 1
2?5

出力例1

2

パスワードとして考えられる文字列は "225" と "255" の 2 つです。

入力例2

15 4
???5????????9??

出力例2

976934094

パスワードの 1 文字目は 0 でも良いことに注意してください。

入力例3

4 10
1234

出力例3

0

このように、忘れている部分が 1 箇所もないこともありえます。

また、ニコニコ文字列となるような連続した部分文字列を取り出す方法が X 以上であるような文字列が存在しないこともありますが、この場合は条件を満たす文字列が 0 個なので、0 を出力すれば良いです。

B - コメント

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ニワンゴ君は、動画サイトのコメントの表示方法の新たな案を考えています。

コメントは画面の右から左に 1 秒につき 1 文字分の速さで流していきます。コメントが N 個ある動画では、それらのコメントを好きな順番で 1 秒おきに流していきます。つまり、i 個目に流したコメントは、最初に流したコメントから右に i-1 文字ずれた位置に表示されることになります。

ニワンゴ君は「N 個のコメントの同じ位置の文字が全て同じ文字である状況」を 1 回以上作りたいと思っているのですが、コメントを流す順番をうまく決めることによって作ることができるでしょうか？「N 個のコメントの同じ位置の文字が全て同じ文字である状況」とは、全ての i について i 個目に流したコメントの X-i 文字目の文字が Y である、というような整数 X と文字 Y の組が存在する状況を表します。

入力

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

N
S_1
S_2
:
S_N
  • 1 行目には、コメントの個数を表す 1 つの整数 N (2 ≦ N ≦ 200) が空白区切りで与えられる。
  • 2 行目からの N 行には、コメントの情報が与えられる。このうち i 行目には、1 つの文字列 S_i が与えられる。S_i は小文字アルファベット (a-z) のみからなる長さが 1 以上の文字列であり、i 番目のコメントを表す。また、コメントの文字列の長さの和は 10^5 以下である。

部分点

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

  • N ≦ 52 かつ、コメントの文字列の長さの和が 2,525 以下であるデータセット 1 に正解した場合は、30 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 60 点が与えられる。

出力

コメントを流す順番をうまく決めることによって「N 個のコメントの同じ位置の文字が全て同じ文字である状況」を 1 回以上作ることができる場合は YES、作ることができない場合は NO を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

3
abcd
bdac
aca

出力例1

YES

2 番のコメント、1 番のコメント、3 番のコメントという順番でコメントを流した場合、

bdac
 abcd
  aca

のように表示され、左から 4 文字目の位置の文字が全て c になります。

入力例2

4
dwango
niconico
niwango
ginza

出力例2

NO
C - ドライブ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ニワンゴ君が住んでいるニコニコ町には N 個の交差点があり、それぞれの交差点には 1 から N の番号がついています。また、2 つの交差点を結ぶ M 本の道があり、それぞれの道には 1 から M の番号がついています。道 i を通ると、交差点 A_i から交差点 B_i または 交差点 B_i から交差点 A_i に 2^i の時間で行くことができます。

ニワンゴ君は今からドライブに出かけるところです。ドライブの経路は、交差点 1 から出発し、M 本全ての道を少なくとも 1 回以上通って、交差点 1 に戻って来る、というような経路にしたいと思っています。そのような経路をたどってドライブをするときにかかる時間の最小値を求めてください。ただし、答えは非常に大きくなることがあるため、1,000,000,007 で割った余りを求めてください。

入力

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

N M
A_1 B_1
A_2 B_2
:
A_M B_M
  • 1 行目には、2 つの整数 N (2 ≦ N ≦ 400,000), M (1 ≦ M ≦ 500,000) が空白区切りで与えられる。これは、ニコニコ町にある交差点が N 個、道が M 本であるということを表す。
  • 2 行目からの M 行では、道の情報が与えられる。このうち i 行目には、2 つの整数 A_i, B_i (1 ≦ A_i ≦ N, 1 ≦ B_i ≦ N, A_i ≠ B_i) が与えられる。これは、道 i が 交差点 A_i と交差点 B_i を結んでいることを表す。同じ交差点の組を結ぶ道は 2 本以上存在しない。また、どの交差点からどの交差点までも、いくつかの道を通ることによってたどり着けることが保証されている。

部分点

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

  • N ≦ 2,525 かつ M ≦ 2,525 を満たすデータセット 1 に正解した場合は、40 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 70 点が与えられる。

出力

ドライブにかかる時間の最小値を 1,000,000,007 で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

4 5
1 2
3 4
2 3
1 3
2 4

出力例1

70

この入力例では、ニコニコ町は以下のような構造をしています。

例えば、交差点を 1,2,3,4,2,3,1 の順でたどるとかかる時間が 2^1 + 2^3 + 2^2 + 2^5 + 2^3 + 2^4 = 70 となります。

入力例2

6 10
4 6
4 5
3 6
5 2
3 2
1 2
3 4
6 1
2 4
1 3

出力例2

2132
D - コインの取り合い

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

ニワンゴ君とニコモバちゃんはコインを使ったゲームをしています。

はじめ N 個のコインが 1 列に並んでいて、左から順に 1 から N の番号がついています。奇数番のコインは表、偶数番のコインは裏の面が上になっています。コイン i の価値は S_i です。

このゲームは N-1 ターンからなり、奇数ターン目のプレイヤーはニワンゴ君で、偶数ターン目のプレイヤーはニコモバちゃんです。i ターン目ではプレイヤーは、コイン i またはコイン i+1 のどちらかをひっくり返すことが出来ます。どちらもひっくり返したくない場合は、どちらもひっくり返さなくても良いです。

N-1 ターンが終わった後に、上を向いている面が表であるコインをニワンゴ君が、裏であるコインをニコモバちゃんが獲得します。このとき、自分が獲得したコインの価値の和がプレイヤーのスコアとなります。このとき、ニワンゴ君のスコアはいくつになるでしょうか？ただし、2 人はとても頭がいいので、それぞれが自分のスコアを最大化するような最適の戦略をとるものとします。

また、ゲームを始める前にニコモバちゃんがコインに落書きをしてしまい、コインの価値が下がってしまうことがあります。ニコモバちゃんは合計 Q 回落書きをして、i 回目に落書きしたコインはコイン P_i で、落書きによってコイン i の価値は D_i 下がりました。

Q 回の落書きそれぞれについても、落書きの直後にゲームを始めた場合のニワンゴ君のスコアを計算してください。

入力

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

N
S_1 S_2 ... S_N
Q
P_1 D_1
P_2 D_2
:
P_Q D_Q
  • 1 行目には、コインの枚数を表す 1 つの整数 N (2 ≦ N ≦ 200,000) が与えられる。
  • 2 行目には、コインのはじめの価値を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 S_i (1 ≦ S_i ≦ 10^9) は、コイン i のはじめの価値を表す。
  • 3 行目には、ニコモバちゃんが落書きをした回数を表す 1 つの整数 Q (0 ≦ Q ≦ 200,000) が与えられる。
  • 4 行目からの Q 行には、ニコモバちゃんの落書きの情報が与えられる。このうち i 行目には、2 つの整数 P_i (1 ≦ P_i ≦ N), D_i (1 ≦ D_i) が空白区切りで与えられる。これは、i 回目の落書きでコイン P_i の価値が D_i 下がったことを表す。ただし、各コインの価値は常に 1 以上であることが保証される。

部分点

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

  • Q = 0 を満たすデータセット 1 に正解した場合は、10 点が与えられる。
  • S_i ≦ 25 を満たすデータセット 2 に正解した場合は、上記とは別に 80 点が与えられる。
  • 全てのテストケースに正解した場合は、上記とは別に 90 点が与えられる。

出力

出力は Q+1 行からなる。1 行目には、はじめの状態からゲームを始めた場合のニワンゴ君のスコアを出力し、2 行目から Q+1 行目までのうち i (1 ≦ i ≦ Q) 行目には、i 回目の落書きの直後にゲームを始めた場合のニワンゴ君のスコアを出力せよ。出力の末尾にも改行を入れること。

入力例1

4
1 2 3 4
1
4 3

出力例1

7
5

この例では、4 枚のコインがあり、それらの価値は左から順に 1,2,3,4 です。はじめ、コインの上の面は「表裏表裏」となっています。この状態からゲームを始めると、

  • ニワンゴ君がコイン 2 をひっくり返す → ニコモバちゃんがコイン 3 をひっくり返す → ニワンゴ君がコイン 4 をひっくり返す

となり、最終状態のコインの上の面は「表表裏表」なので、ニワンゴ君のスコアは 7 点となります。

また、この例では 1 個のクエリがあります。クエリによってコイン 4 の価値が 1 に下がります。この状態からゲームを始めると、

  • ニワンゴ君がコイン 2 をひっくり返す → ニコモバちゃんがコイン 2 をひっくり返す → ニワンゴ君がコイン 4 をひっくり返す

となり、最終状態のコインの上の面は「表裏表表」なので、ニワンゴ君のスコアは 5 点となります。

入力例2

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

出力例2

19
16
16
12
11
11