Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 100 点
問題文
dwango社員のニワンゴくんは長さ 4 の数字のみからなる文字列 s を見つけました。
s がニコニコ文字列(後述)ならば Yes を、そうでなければ No を出力してください。
ある数字 x,y が存在して、s が xyxy と表されるとき、 s はニコニコ文字列であると呼ばれます。例えば 2525 や 4141、9999 はニコニコ文字列ですが、2255 や 1221、3334 はニコニコ文字列ではありません。
制約
- |s| = 4
- s は数字のみからなる
入力
入力は以下の形式で標準入力から与えられる。
s
出力
答えを出力せよ。
入力例 1
2525
出力例 1
Yes
- 問題文中の例の通りです
入力例 2
1881
出力例 2
No
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 300 点
問題文
dwango社員のニワンゴくんは2525SNSという新しいSNSを開発しています。 2525SNSは2525文字列のみ投稿可能な画期的なSNSです。
この問題において、25 の 1 回以上の繰り返しで表される文字列を2525文字列と呼びます。
例えば、25,2525,2525252525252525 などは2525文字列ですが、空文字列や 2255,2552,252 などは2525文字列ではありません。
まず、ニワンゴくんは2525文字列をいくつか作ることにしました。 ニワンゴくんは手元にあった文字列 s を 1 つ以上の部分列に分解し、分解された部分列それぞれが2525文字列となるようにしたいです。
最小でいくつの部分列に分解すればこれを達成可能ですか？どのように分解しても達成不可能な場合は -1 を出力してください。分解についてはサンプル 1 の説明も参照してください。
制約
- 1 \leq |s| \leq 2{,}525
- s は
2と5のみからなる
入力
入力は以下の形式で標準入力から与えられる。
s
出力
答えを出力せよ。
入力例 1
225525
出力例 1
2
- 1 つの部分列に分解した場合、
225525は2525文字列ではないため条件を満たしません。 - その他の分解としては例えば (
25,2525) となるような分解と (25,25,25) となるような分解が考えられます。それぞれについて正しい分解の例とそうでない例を示します。各部分列内において、s における相対的な出現順序が守られるように分解する必要があることに注意してください。 - (
25,2525) となるように 2 つの部分列に分解することで、それぞれの部分列が2525文字列となるように分解できます。
入力例 2
52
出力例 2
-1
- 分解方法は 2 通りありますが、それぞれの部分列が2525文字列となるように分解することはできません。
5と2に分解したのち、それぞれの順序を入れ替えて25を作ることは不可能なことに注意してください。
入力例 3
2255252252222555552522255255
出力例 3
5
入力例 4
25252
出力例 4
-1
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 500 点
問題文
dwango社員のニワンゴくんはゲームが大好きです。ニワンゴくんは「なんとかトゥーン」というゲームを遊んでいます。
このゲームはチーム戦で、N 人のプレイヤーからなるAチームと、M 人のプレイヤーからなるBチームに分かれて戦闘を行います。各プレイヤーは戦闘の間、相手チームのプレイヤーに対して「攻撃」を行うことができます。あるプレイヤーからあるプレイヤーに対する攻撃が成立すると、攻撃したプレイヤーの「キル数」が 1 加算され、同時に攻撃されたプレイヤーの「デス数」が 1 加算されます。どちらのプレイヤーも攻撃の後も戦闘を継続でき、攻撃したりされたりすることが可能です。あるプレイヤーが同じプレイヤーを複数回攻撃することもありえます。しかし、同じチームのプレイヤーを攻撃することはできません。戦闘の開始時点で、すべてのプレイヤーのキル数とデス数は 0 に設定されています。
ニワンゴくんは、戦闘が終わるとその結果を記録しています。ニワンゴくんの記録は以下の様なものです。まず、Aチームのプレイヤーをキル数の多い順（同じ場合デス数の少ない順）に並べ、それらのキル数を killA = [killA_1, killA_2, ..., killA_N] 、デス数を deathA = [deathA_1, deathA_2, ..., deathA_N] とします。同様にしてBチームのプレイヤーからも数列 killB = [killB_1, killB_2, ..., killB_M] および deathB = [deathB_1, deathB_2, ..., deathB_M] を定義します。ニワンゴくんは killA と killB のみを記録します。
ニワンゴくんは、 killA と killB から必ずしも一意に deathA と deathB を復元できないことに気が付きました。与えられた killA と killB に矛盾しない deathA と deathB の組み合わせは何通りあるでしょうか？答えは非常に大きくなりうるので、 1,000,000,007 (10^9 + 7) で割った余りを出力してください。
制約
- 1 \leq N, M \leq 100
- 0 \leq killA_i, killB_i
- killA_1 + killA_2 + ... + killA_N \leq 1,000
- killB_1 + killB_2 + ... + killB_M \leq 1,000
- killA_{i} \geq killA_{i+1} (1 \leq i \leq N - 1)
- killB_{i} \geq killB_{i+1} (1 \leq i \leq M - 1)
入力
入力は以下の形式で標準入力から与えられる。
N M killA_1 killA_2 ... killA_N killB_1 killB_2 ... killB_M
出力
答えを出力せよ。
入力例1
4 1 0 0 0 0 5
出力例1
6
deathA としてありえるのは、 [0, 0, 0, 5], [0, 0, 1, 4], [0, 0, 2, 3], [0, 1, 1, 3], [0, 1, 2, 2], [1, 1, 1, 2] の 6 通り、deathB としてありえるのは、 [0] の 1 通りなので、答えは 6 となる。
入力例2
4 1 3 2 1 0 5
出力例2
56
入力例1ではAチームの全員のキル数が同じなため、デス数は昇順である必要があったが、入力例2ではキル数が異なるため、デス数は昇順である必要はない。
入力例3
4 4 2 1 1 1 1 1 1 1
出力例3
66
deathA としてありえるのは 11 通り、deathB としてありえるのは 6 通りなので、答えは 66 となる。
入力例4
4 4 5 5 4 3 5 4 4 3
出力例4
322875
入力例5
5 5 100 100 100 100 100 50 50 50 50 50
出力例5
331829279
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 600 点
問題文
dwango社員のニワンゴくんは、アプリ開発に携わるエンジニアです。ニワンゴくんは、開発したアプリのビルド・テスト・デプロイなどを毎日行っています。業務を効率化するために、ニワンゴくんはこういった依存関係のあるタスクを適切に実行するプログラムを書くことにしました。
タスクは N 個あり、 i 番目のタスクを実行すると、その結果として x_i MB のデータがディスクに書き込まれます。ただし、タスクは別のタスクに依存していることがあり、全ての依存先タスクの実行結果がディスク上に書き込まれていなければそのタスクは実行できません。 i 番目 (2 \leq i \leq N) のタスクを依存先に持つタスクは a_i です。
N 個のタスクの依存関係は、連結な有向木になることが分かっています。つまり、どのタスクについても、そのタスクを依存先として持つタスクはちょうど1つだけ存在します。ただし、例外となる1番目のタスクはどのタスクからも依存されません。1番目のタスクは、それ以外のすべてのタスクに直接的、あるいは間接的に依存しています。
ニワンゴくんの目的は、1番目のタスクを実行し、その結果をディスク上に書き込むことです。さらにニワンゴくんは、計算資源をできるだけ節約したいと考えました。ニワンゴくんは、任意のタスクを実行した直後に、ディスク上に書き込まれている任意の 0 個以上のタスクの実行結果を選び、削除することができます。また、時間計算量も節約したいので、同じタスクを2回以上実行することはないようにしました。
ニワンゴ君が1番目のタスクの実行結果を得るにはどれだけのディスクが必要でしょうか？適切な順番でタスクの実行および実行結果の削除を行い、その過程での最大のディスク使用量（ディスクに書き込まれている実行結果の量の総和）が最小になるようにしてください。その最小値 (MB) を出力してください。
制約
- 1 \leq N \leq 20
- 1 \leq x_i \leq 1,000,000 (1 \leq i \leq N)
- 1 \leq a_i \leq i - 1 (2 \leq i \leq N)
入力
入力は以下の形式で標準入力から与えられる。
N
x_{1} x_{2} x_{3} ... x_{N}
a_{2} a_{3} ... a_{N}
出力
答えを出力せよ。
入力例1
5 3 5 2 4 6 1 1 2 2
出力例1
15
| 行動 | ディスクの消費量 |
|---|---|
| タスク4を実行する | 4 (= 4) |
| タスク5を実行する | 10 (= 4 + 6) |
| タスク2を実行する | 15 (= 4 + 6 + 5) |
| タスク4, 5の結果を削除する | 5 (= 5) |
| タスク3を実行する | 7 (= 5 + 2) |
| タスク1を実行する | 10 (= 5 + 2 + 3) |
このようにすれば、過程での最大ディスク消費量が15 MBとなります。この入力ではこれが最善です。
入力例2
2 3 5 1
出力例2
8
入力例3
5 1 2 3 4 5 1 2 3 4
出力例3
9
Time Limit: 2.525 sec / Memory Limit: 246 MB
配点 : 1000 点
問題文
これはインタラクティブな問題です。
dwango社員のニワンゴくんは N 頂点の木に住んでいます。 この木の頂点には 1 から N までの番号がついています。 この木の i 番目の辺は頂点 a_i と頂点 b_i を双方向につなぐ長さ 1 の辺です。 ニワンゴくんは どの頂点の次数も 5 以下である ことを知っています。
この木のいずれかの頂点にニワンゴくんの家がありますが、ニワンゴくんは家がどこにあるかを忘れてしまいました。
ニワンゴくんは自作のプログラムに最大で Q 回質問を行って、家のある頂点を特定したいです。
プログラムに 2 つの頂点の番号 u,v を渡すと、家のある頂点から近い方の頂点の番号が表示されます。
ただし、どちらの頂点も家のある頂点から同じ距離にある場合は 0 が表示されます。
制約
- 2 \leq N \leq 2{,}000
- Q = 14
- 1 \leq a_i,b_i \leq N
- 与えられるグラフは木
- どの頂点の次数も 5 以下
部分点
- どの頂点の次数も 2 以下であるようなデータセットに正解した場合、400 点が与えられる。
入出力
最初に、標準入力から以下の形式で入力が与えられる：
N Q
a_1 b_1
:
a_{N-1} b_{N-1}
その後、以下の形式で質問を出力せよ：
? u v
ここで、u,v は 1 以上 N 以下の整数でなくてはならない。 次に、質問の答えが標準入力から以下の形式で与えられる：
ans
ここで、ans は u,v,0 のいずれかである。 それぞれの値は以下のことを表す。
- u：u と v のうち、家のある頂点に近いのは u である
- v：u と v のうち、家のある頂点に近いのは v である
- 0：u と v は、家のある頂点から同じ距離にある
最後に、答えを以下の形式で出力せよ：
! x
ここで x は家のある頂点でなくてはならない。
ジャッジ
- 出力のあと、標準出力を flush せよ。従わない場合
TLEの可能性がある。 - 答えを出力した後、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は定義されていない。
- 出力の答えが間違っている場合の挙動は定義されていない(
WAとは限らない)。
入出力例
これは以下のような木において、頂点 3 にニワンゴくんの家がある場合の入出力例です。
| Input | Output |
|---|---|
| 6 14 1 2 5 2 3 1 3 6 1 4 |
|
| ? 4 5 | |
| 4 | |
| ? 1 6 | |
| 0 | |
| ? 6 5 | |
| 6 | |
| ! 3 |
- 頂点 4,5 のうち、頂点 3 に近いのは頂点 4 なので 4 が表示されます。
- 頂点 1,6 は頂点 3 から同じ距離にあるため、0 が表示されます。
- 頂点 6,5 のうち、頂点 3 に近いのは頂点 6 なので 6 が表示されます。
- 家がある頂点が 3 だと回答しました。14 回以下の質問で正しい答えを出力したため、正解となります。