実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
高橋君は 2 つの問題から成る T 分のコンテストに参加することになりました。
1 問目はちょうど A 分で解くことができ、 解くと B 点が得点に加算されます。
2 問目はちょうど C 分で解くことができ、 解くと D 点が得点に加算されます。
2 問目の方が 1 問目より難しいので、配点は B \leq D となっていますが、好きな順番で解くことができます。
コンテストの開始や、1つの問題が解き終わると同時に次の問題を解き始めることができ、またコンテスト終了と同時に解き終わることも許されます。
高橋君は最大何点取ることが出来るでしょうか。
制約
- 1 \leq T,A,B,C,D \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
T A B C D
出力
高橋君の取ることのできる最大の得点を出力せよ。
入力例 1
100 20 500 40 1000
出力例 1
1500
時間内に両方解き終わることができます。
入力例 2
50 100 1500 100 1500
出力例 2
0
どちらも解けない場合の得点は 0 点です。
入力例 3
100 100 1000 100 1000
出力例 3
1000
どちらの問題を解いても同じです。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
初め箱には赤い玉が X 個、青い玉が Y 個入っています。
高橋君は以下の操作を繰り返して、箱を空にしたいです。
- 赤い玉を 1 個、青い玉を 3 個箱から取り出す。
もしくは、
- 赤い玉を 3 個、青い玉を 1 個箱から取り出す。
各操作ではこの 2 つのいずれか好きな方を行うことができ、毎回同じ操作を行う必要はありません。
高橋君のために、箱を空にする方法があるかどうか判定してください。
制約
- 0 \leq X,Y \leq 10^9
- X+Y>0
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
X Y
出力
箱を空にすることができる場合は Yes
を、できない場合は No
を出力せよ。
入力例 1
3 1
出力例 1
Yes
1 回の操作で空にすることができます。
入力例 2
1 2
出力例 2
No
どちらの操作も行う事ができません。
入力例 3
4 4
出力例 3
Yes
例えば以下のように 2 回で箱を空にできます。
1 回目は、赤い玉を 1 個、青い玉を 3 個箱から取り出す。
2 回目は、赤い玉を 3 個、青い玉を 1 個箱から取り出す。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
数直線として表すことのできる街に N 人が暮らしており、i 番目の人は座標 x_i に住んでいます。同じ座標に 2 人以上住んでいることはありません。
座標 x に住む人と、座標 y に住む人が交流するのに必要なコストは |x-y| です。
この街全体の交流コストは、N のうち全ての 2 人の組み合わせ 1 \leq i < j \leq N が交流するのにかかるコストの和として計算されます。
この交流コストを出力してください。
制約
- 2 \leq N \leq 10^5
- 0 \leq |x_i| \leq 10^8
- x_i は全て異なる
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N x_1 x_2 ... x_{N-1} x_N
出力
この街の交流コストを出力せよ。
入力例 1
2 -2 3
出力例 1
5
-2 と 3 に住む人同士のコストは 5 です。
入力例 2
3 10 1 5
出力例 2
18
10 と 1 に住む人同士のコストは 9 です。
10 と 5 に住む人同士のコストは 5 です。
1 と 5 に住む人同士のコストは 4 です。
よって、街の交流コストは 18 です。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
英小文字から成る文字列 S が与えられます。
これは code
のように、先頭の文字がその文字列においてアルファベット順で最小となる文字列を1つ以上連結してできたものです。
元となるそれぞれの文字列には、先頭と同じ文字が複数含まれていたことはありません。
S は最小で何個の文字列を繋げてできた可能性があるでしょうか。
制約
- 1 \leq |S| \leq 10^5
- S は英小文字から成る
入力
入力は以下の形式で標準入力から与えられる。
S
出力
連結して S になるような題意の文字列の個数の最小値を出力せよ。
入力例 1
codethanksfes
出力例 1
2
例えば codeth
と anksfes
を連結するとできます。
入力例 2
atcoder
出力例 2
1
atcoder
は条件を満たします。
入力例 3
aaa
出力例 3
3
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
1 以上 T 以下の整数を、各 i は 0 個以上 a_{i} 個以下の範囲で、好きな個数黒板に書くことができます。
書かれている整数に対して次の操作を繰り返して、ただ 1 つの整数が黒板に書かれているようにできるような整数の書き方は何通りあるでしょうか。
- 黒板に書かれている整数のうち、2 つ以上ある整数 X を 2 つ消して、黒板に X+1 を 1 つ書く
答えは非常に大きくなることがあるので、1000000007 で割った余りを計算してください。
ただし 2 つの書き方が異なるとは、それぞれの書き方において操作を始める前に黒板に書かれている個数が異なるような整数が存在する場合を表します。
制約
- 1 \leq T \leq 300
- 0 \leq a_i \leq 300
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
T a_1 a_2 ... a_{T-1} a_T
出力
上手く操作を行うことで黒板に書かれている整数を 1 つに出来るような選び方の個数を 1000000007 で割った余りを出力せよ。
入力例 1
2 1 1
出力例 1
2
1 を 1 つ書くか、2 を 1 つ書く方法が条件を満たします。
入力例 2
3 2 1 1
出力例 2
6
入力例 3
8 300 300 300 300 300 300 300 300
出力例 3
220439161
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
高橋君は、N 頂点から成る根付き木上で、M 枚のコインを使って以下の操作をちょうど K 回行おうとしています。
この木は、頂点 i の親が p_i であるものとして与えられます。p_i = 0 である頂点が根です。
各操作では、
- 根にコインが置かれていない場合に、根に新しいコインを置く
もしくは
- コインの置かれている頂点を 1 つ選んで、コインの置かれていない子のどれかにコインを移動する
のどちらかを行うことができます。
K 回の操作のあと、M枚 のコイン全てが木のどこかに置かれていなければなりません。
1 枚目に根に置いたコイン, 2 枚目に根に置いたコイン, ..., M 枚目に根に置いたコイン の置かれている頂点を v_1, v_2, ..., v_M とします。
高橋君は、この列 v_1, v_2, ..., v_M のうち、辞書順で最小であるものが知りたくなりました。
高橋君のためにこの列を求めてあげてください。
列 u_1, u_2, ..., u_M が 列 v_1, v_2, ..., v_M より辞書順で小さいとは、u_i < v_i かつ 、全ての j < i で u_j = v_j が成り立つような 1 \leq i \leq M が存在する場合を言います。
ただし、ちょうど K 回の操作を行えない場合や、M 枚のコインを木に置けない場合は、-1 を出力してください。
制約
- 1 \leq M \leq N \leq 300
- 0 \leq K \leq 10^5
- 0 \leq p_i \leq N
- p_i = 0 となる i はただ 1 つ存在する
- (i, p_i) に辺を張ってできるグラフは木を成す
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M K p_1 p_2 ... p_{N-1} p_N
出力
K 回の操作後、M 枚のコインが全て置かれているように出来る場合は、
v_1 v_2 ... v_{M-1} v_M
のように、不可能な場合は -1 を出力せよ。
入力例 1
3 2 4 2 0 2
出力例 1
1 3
次ののように操作を行うことで \{1, 3\} の列を作ることができ、これより辞書順で小さい列を作ることはできません。
- 1 枚目のコインを頂点 2 に置く
- 1 枚目のコインを頂点 2 から 1 に動かす
- 2 枚目のコインを頂点 2 に置く
- 2 枚目のコインを頂点 2 から 3 に動かす
上の画像では、1 枚目のコインを赤、2 枚目のコインを青で表しています。
入力例 2
3 2 5 2 0 2
出力例 2
-1
5 回の操作を行うことが出来ないので、 -1 を出力してください。
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
高橋君は、初めに N 枚のカードの表に 1 から N の整数を 1 つずつ書いた後、裏返してシャッフルし、また 1 から N の整数を 1 つずつ書きました。
1 \leq i \leq N 枚目のカードには、表に a_i が、裏にb_i が書かれています。
この N 枚のカードを、それぞれ好きな面を上に向けて置き、見えている整数の和を最大にしようと考えました。
しかしこのままでは高橋君には簡単すぎます。
高橋君は、見えている整数の種類が少なすぎると悲しいので、K 種類以上の整数が見えるという条件のもとで和の最大値を求めることにしました。
高橋君のためにこの値を計算してあげてください。
制約
- 1 \leq K \leq N \leq 5000
- 1 \leq a_i, b_i \leq N
- a_1, a_2, ..., a_N には 1, 2, ..., N が 1 度ずつ現れる。
- b_1, b_2, ..., b_N には 1, 2, ..., N が 1 度ずつ現れる。
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K a_1 a_2 ... a_{N-1} a_N b_1 b_2 ... b_{N-1} b_N
出力
和の最大値を出力せよ。
入力例 1
2 2 2 1 1 2
出力例 1
3
表裏が \{1, 2\} のカードと \{2, 1\} のカードがあります。
両方を表にするか、両方を裏にすることで 2 つの整数が見えるようにでき、和は 3 です。
入力例 2
2 1 2 1 1 2
出力例 2
4
表裏が \{1, 2\} のカードと \{2, 1\} のカードがあります。
両方を 2 の面を表にしてよく、和は 4 が最大です。
入力例 3
3 2 2 3 1 1 3 2
出力例 3
7
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
整数が 1 つずつ書かれたカードが N 枚積んであり、上から i 枚目には a_{i} が書かれています。
AliceとBobはこのカードを使ってゲームを行うことにしました。
2 人はAliceから始めて交互に、残っているカードを上から 1 枚以上好きなだけ取り、この時取った整数の和を書き出します。
カードが無くなるとこのゲームのスコアを、書き出された整数を用いて計算します。
書き出された整数の個数を K 個とした時、小さい方から (K+1)/2 以上の最小の整数 番目の値がこのゲームのスコアです。
2 人はカードに書かれている数を事前に知っています。Aliceはゲームのスコアを出来るだけ大きく、Bobは小さくしたいです。
2 人がそれぞれ最善に振る舞った時、このゲームのスコアはいくつになるでしょうか。
制約
- 1 \leq N \leq 1000
- 0 \leq |a_i| \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 ... a_{N-1} a_N
出力
2 人が最善の取り方をした場合の、ゲームのスコアを出力せよ。
入力例 1
2 1 -1
出力例 1
1
Aliceが初めに \{1, -1\} を取ると、書かれる整数は \{0\} で、スコアは 0 になります。 Aliceが初めに \{1\} を取ると、Bobは \{-1\} を取ることになり、書かれる整数は \{1, -1\} で、スコアは 1 になります。
よってAliceにとっては \{1\} を取る方が良く、スコアは 1 となります。
入力例 2
3 3 1 4
出力例 2
8