いろはちゃんコンテスト Day1

A - 一問目

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

文字列 S が与えられます。S の頭文字を出力してください。

制約

1 \leq |S| \leq 100
S は半角英数字からなる文字列

入力

文字列 S が 1 行に与えられます。

出力

Sの頭文字を出力してください。最後に改行を入れてください。

入力例 1

Iroha

出力例 1

入力例 2

AtCoder

出力例 2

B - ローリング・老人と海

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

読書家のいろはちゃんは、「老人と海」という文字列の頭文字を末尾に持っていくと「人と海老」になることに気づきました。いろはちゃんのお気に入りの本の題名 S に対し、「先頭の文字を末尾に移動する」という操作を K 回ほどこした文字列を答えてください。

制約

1 \leq |S| \leq 1000
0 \leq K \leq 1000
S は半角英数字からなる文字列

入力

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

 S 
 K

出力

S に操作を K 回ほどこした文字列を 1 行に出力してください。最後に改行を入れてください。

入力例 1

JKrolling
2

出力例 1

rollingJK

JKrolling に 1 回操作すると KrollingJ になり、もう 1 回操作すると rollingJK になる。

入力例 2

JKrolling
99

出力例 2

JKrolling

9 回操作するごとに元の文字列に戻ります。

入力例 3

iroha
168

出力例 3

hairo

入力例 4

EARTH
444

出力例 4

HEART

C - Halcyon

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

いろはちゃんは、最近Halcyon Daysというものを知りました。いろはちゃんの暦の上で、これは、12 月 N 日の冬至とその前の 1 週間のことを指します。物理好きさんはやさしいのでいろはちゃんにHalcyon Daysが何日か教えてあげることにしました。冬至の日付である N が与えられるので、Halcyon Daysの日付を 8 日間出力してください。

制約

8 \leq N \leq 31

入力

\(1\) 行にNが与えられます。

出力

Halcyon Daysの日付を昇順(小さい順)に、\(1\) 行に \(1\) つずつ、計 \(8\) つ出力してください。

入力例1

出力例1

冬至は21日で、Halcyon Daysの起点は14日となります。

入力例2

出力例2

D - 肉と肉のぶつかり合い

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

いろはちゃんは、プロレスの試合を観戦します。その試合のルールは次のようなものです。

高橋君と青木君が勝負をする。高橋君の戦闘力は X であり、青木君の戦闘力は Y である。
双方が、野良レスラーの N 人の中から N/2 人づつ援軍をとる。
援軍は、高橋君から始めて交互に 1 人づつ野良レスラーを選んで自陣に加えていく。
i 人目の野良レスラーの戦闘力は A_i である。
高橋君とその援軍(高橋軍)、青木君とその援軍(青木軍)のうち、戦闘力の和が大きいほうが勝ち。但し、等しい場合は引き分け。

あなたは超能力者です。高橋君と青木君の両者が最善を尽くすとき、この試合の勝者を言い当ててください。

制約

2 \leq N \leq 100
Nは偶数である
1 \leq X,Y \leq 100
1 \leq A_i \leq 100 (1 \leq i \leq N)

入力

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

N\ \ X\ \ Y
A_1\ \ A_2\ \ ...\ \ A_N

出力

高橋軍が勝つならTakahashi
青木軍が勝つならAoki
引き分けるならDraw

を一行に出力してください。

入力例1

2 2 2
3 1

出力例1

Takahashi

高橋君が1人目の野良レスラーを選ぶと戦闘力の和が高橋軍 5\ -\ 3青木軍となり勝てます。

入力例2

2 2 100
3 1

出力例2

Aoki

青木君が強すぎて勝てません。

入力例3

4 5 5
5 5 5 5

出力例3

Draw

どう足掻いても引き分けです。

E - 放課後

Time Limit: 1 sec / Memory Limit: 256 MB

配点: 300 点

この問題の解説はこちら。

問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

きたむーは高校の競技プログラミング部に所属し、放課後も熱心にプログラミングに取り組んでいた。しかし最近、きたむーには彼女ができたようだ。

デートがしたい！　デートがしたい！　デートがしたい！

デートに着実に蝕まれていくプログラミング学習の時間。このままではきたむーのレートが落ちてしまうことに危機感を覚えたあなたは、彼の放課後のスケジュールを管理してあげることにした。

あなたは以下の点に配慮して明日以降の N 日分のスケジュールを立てることにした。

きたむーそれぞれの日の放課後に「デート」「競プロ」のうちいずれか片方の行動をとる。

きたむーは A 日以上デートできないと、愛が足りずに動けなくなってしまうので、 A 日に一度は必ずデートする。

このカップルには明日から N 日以内に B 回の記念日があり、それぞれ D_1,D_2,\cdots,D_B 日後である。この日には必ずデートを行う。 D_i は互いに異なる。

なお、きたむーは今日デートしており、彼の高校に休日はないものとする。

あなたはきたむーが競プロに取り組む日数を最大化したい。

制約

入力される値はすべて整数である
1 \leq N \leq 10^{18}
1 \leq A \leq N
0 \leq B \leq min(N,2 \times 10^5)
1 \leq D_i \leq N (1 \leq i \leq B)
D_i \neq D_j (1 \leq i,j \leq B かつ i \neq j)
入力はすべて整数

入力

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

N A B
D_1 D_2 \cdots D_B

出力

きたむーにプログラミング学習をさせることができる日数の最大値を1行で出力せよ。

入力例 1

10 4 2
4 6

出力例 1

明日から10日間のスケジュールを考えるが、4日以上競プロが連続してはならず、4日後、6日後の2日の記念日がある。競プロをP、デートをDと表記するなら、例えば、PPPDPDPPPDとスケジュールを組むことで7日競プロに取り組ませることができる。

入力例 2

10 1 0

出力例 2

寂しがりすぎ。

入力例 3

5 2 5
1 2 3 4 5

出力例 3

記念日多すぎ。

入力例 4

10 5 3
4 3 7

出力例 4

入力例 5

100 16 11
90 98 88 82 40 16 32 45 87 67 48

出力例 5

F - Head of The Dragon

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 300 点

この問題の解説はこちら。

問題文

整数N,Kが与えられます。 a_1 × a_2 × .... × a_K = Nを満たす数列aを構成できるか判定し、構成できるならばその数列の中で辞書順で最小の数列を一つ構成してください。なお、数列の各要素は 2 以上の正の整数から構成されていなければならないものとします。

制約

1 \leq N \leq 10^9
1 \leq K \leq 10^9

入力

正整数NとKが一行で与えられます。

N　K

出力

条件を満たす数列が存在しない場合、-1を単独で出力してください。そうでない場合、整数をK個出力してください。

入力例 1

30 3

出力例 1

2 3 5

2 × 3 × 5 = 30なのでこの数列は条件を満たしています。

他に3 2 5や5 2 3などの数列も考えられますが、辞書順で最小なのは2 3 5なので解としては不適切です。

入力例 2

30 4

出力例 2

-1

どのようにしても数列を構成することができません。

入力例 3

123456 7

出力例 2

2 2 2 2 2 2 1929

G - 友達以上恋人以下

Time Limit: 1 sec / Memory Limit: 256 MB

配点: 400 点

この問題の解説はこちら。

問題文

※きたむーとはこの問題の作問のお手伝いをした人の名前である。また、きたむーの彼女はいろはちゃんではない。

これはきたむーが彼女を射止める前の話である。彼は彼女に事前に伝えられていた。

「あなたは友達以上恋人以下」

と。彼は思った。

「つまり恋人も含むよね？？恋人になってもいいですよってことだよね？？ね？？」

というわけで彼は思いを伝えることにしたが、いきなり思いを伝えても受け入れてもらえないかもしれない。そこで、彼は何日かに分けて少しずつ思いを伝えることにした。

きたむーは明日から N 日間のうちちょうど M 日に彼女のもとへ行き、好意をほのめかす。なお、それぞれの日の彼女の機嫌は A_i であるとあらかじめ予想できているため、彼は極力機嫌のいい日に彼女のもとへ行きたい。しかし、あまり時間が空きすぎてはよくないと考えた彼は、 K 日以上時間を空けない、つまり連続する K 日に1回は好意をほのめかすことにした。ただし、今日は既に好意をほのめかしている。

あなたはきたむーの行動をシミュレートしたくなった。きたむーが好意をほのめかす日の彼女の機嫌の合計の最大値を求めよ。

制約

入力される値はすべて整数である
1 \leq N \leq 365
1 \leq M \leq N
1 \leq K \leq N
1 \leq A_i \leq 10^9 (1 \leq i \leq N)

入力

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

N M K
A_1 A_2 \cdots A_N

出力

きたむーが好意をほのめかす日の彼女の機嫌の合計の最大値を1行で出力せよ。ただし、条件を満たす選び方が存在しない場合は-1を出力せよ。

入力例 1

5 2 3
5 1 3 2 4

出力例 1

例えば、1日目と3日目に好意をほのめかせば機嫌の合計は8となる。機嫌の合計が9以上になることは無い。

入力例 2

2 1 1
100 100

出力例 2

-1

入力例 3

1 1 1
100

出力例 3

入力例 4

10 6 4
56 1 82 32 4 11 74 49 90 6

出力例 4

H - ちらし寿司

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 400 点

この問題の解説はこちら。

問題文

いろはちゃんは、ちらし寿司が食べたいです。

ところで、非負整数Xを10進法で表したときの各桁の数字の和をf(X)とします。

整数Nが与えられるので、以下の条件を満たす非負整数Xの最小値を求めてください。

f(X) = f(N)
X \neq N

制約

1 \leq N \leq 10^{15}

入力

正整数Nが一行で与えられます。

出力

条件を満たすXの最小値を出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

I - リスのお仕事

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

この問題の解説はこちら。

問題文

今日のリスの仕事は、どんぐりをある木からある木まで運ぶことです。
リスの住んでいる森には全部で N 本の木があり、それぞれの木には 1 から N までの整数の名前が付けられています。また、それぞれの木を行き来できる枝が全部で \(M\) 本あり、\(i\) 本目(1 \leq i \leq M)の枝を使って木 A_i と木 B_i の間を双方向に渡れます。
それぞれの枝から次の木までは大きさ C_i の隙間があり、リスがジャンプしないといけません。リスは同じ大きさの隙間はノリノリで渡りますが、どんぐりをもちながらジャンプするのは疲れるので、前に跳んだ隙間と違う大きさの隙間をジャンプする前に休憩をすることにしました。ただし、最初のジャンプでは休憩をしません。

リスは木 1 にあるどんぐりを持って、休憩回数が最少となるようなルートを通って木 N まで運びます。
森の精霊であるいろはちゃんは、リスが休憩する場所とゴールの木におやつの木の実を K 個ずつおいてあげたいです。
いろはちゃんはいくつの木の実を用意すればいいでしょう。

制約

2 \leq N \leq 10^5
0 \leq M \leq 10^5
1 \leq K \leq 10^4
1 \leq A_i, B_i \leq N
A_i \neq B_i
i \neq j について (A_i, B_i, C_i) \neq (A_j, B_j, C_j)
1 \leq C_i \leq 10^5

入力

以下の形式で与えられます。

N \ M \ K
A_1 \ B_1 \ C_1
\vdots
A_M \ B_M \ C_M

出力

必要な木の実の数の最小値を出力してください。リスが木 N にたどり着けない場合は-1と出力してください。 そうでない場合、リスは全員同じルートを通るので、(最少の休憩回数+1) \times Kを出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

解説

J - ヌクレオチド

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

問題文

高橋君は世界征服のために Q 個のウイルスを作ることにしました。そのためには塩基列を考えることが重要ですが、あまりに候補が多すぎるのであなたに助けを求めてきました。

x 番目に作りたいウイルスの塩基列は、長さ N_x の数列 A_1, A_2, \cdots, A_{N_x} であって、以下の条件を満たすものとして表せます。

各要素は 0, 1 のどちらか。
回文である。つまり、 1 \leq i \leq N_x について、 A_i = A_{N_x+1-i} が満たされる。
転倒数は K_x である。ただし、転倒数とは、整数組 (i, j) であって、i < j かつ A_i > A_j となるものの個数を表す。

条件を満たす数列 A_i は何通りあるでしょうか。答えは非常に大きな数になる可能性があるので、 10^9+7 で割った余りを求めてください。

制約

1 \leq Q \leq 10^5
1 \leq N_i \leq 10^5
0 \leq K_i \leq N_i(N_i - 1) / 2
入力はすべて整数

入力

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

 Q 
N_1\ K_1 
\vdots
N_Q\ K_Q

出力

Q 行出力してください。

i 行目には、i 番目に作りたいウイルスの塩基列としてあり得る数列の個数を 10^9+7 で割った余りを 1 行に出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

K - ルーレット

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : \(600\) 点

この問題の解説はこちら。

問題文

いろはちゃんは、\(N\) 個のルーレット用の円盤と十分な個数のルーレット用の球を持っています。各円盤には \(1\) から \(N\) までの整数番号が割り振られています。

円盤の周囲には整数が書かれています。具体的には、円盤 \(i\) の周囲には \(M_i\) 個の整数 \(A_{i,1},\ A_{i,2},\ \dots\ A_{i,M_i}\) が書かれています。これらの整数には重複があるかもしれません。

また、円盤 \(i\) を回してそこに球を転がすと球は \(A_{i,1},\ A_{i,2},\ \dots\ A_{i,M_i}\) のいずれかが書かれたところに入ります。このとき、球が \(A_{i, j}\ (1≦j≦M_i)\) に入る確率は \(1/{M_i}\) です。

ある日、天才的な発想を持ついろはちゃんはこれらの円盤を使った遊びを思いつきました。それは次のようなものです。

まず、全ての円盤を回してそれぞれに球を転がす。
円盤 \(1, 2, \dots N\) の順に、球が入ったところに書いてある整数をつなげて読む。
- 例えば、円盤が \(3\) 個あり、球が入ったところに書いてある整数が円盤 \(1, 2, 3\) 上でそれぞれ \(11, 2, 717\) だった時は、\(112717\) を読み上げることになる。

いろはちゃんは読み上げられる整数の期待値が知りたくなりました。しかし、彼女はプログラマではなかったので期待値を求めることができませんでした。

あなたが優秀なプログラマであるかどうかは知りませんが、プログラマでないいろはちゃんのために期待値を求めてください。

ただし、期待値 (以降 \(E\) とする) は小数になることがあるので、代わりに \(E \times M_1 \times M_2 \times\ \dots\times\ M_N\) (この値は必ず整数になる) を \(10^9+7\) で割った余りを求めてください。

制約

入力は全て整数である。
\(1≦N≦200,000\)
\(1≦M_i\ (1≦i≦N)\)
\(M_1 + M_2 +\ \dots\ + M_N≦200,000\)
\(1≦A_{i, j}≦10^9\ (1≦i≦N, 1≦j≦M_i)\)

入力

入力は以下の形式で与えられます。

\(N\)
\(M_1\ A_{1, 1}\ A_{1, 2}\ \dots\ A_{1, M_1}\)
\(M_2\ A_{2, 1}\ A_{2, 2}\ \dots\ A_{2, M_2}\)
\(\vdots\)
\(M_N\ A_{N, 1}\ A_{N, 2}\ \dots\ A_{N, M_N}\)

出力

\(E \times M_1 \times M_2 \times\ \dots\times\ M_N\) を \(10^9+7\) で割った余りを出力してください。

入力例 1

2
2 11 3
2 9 14

出力例 1

この入力例では \(2\) 個の円盤があり、それぞれ \(11, 3\) と \(9, 14\) が書かれています。

読み上げられる整数としてありうるものは \(119, 1114, 39, 314\) の \(4\) 個で、それぞれが等確率で出るので期待値は \(\frac{119+1114+39+314}{4}=396.5\) になります。

答えは \(396.5 \times 2 \times 2 = 1586\) となります。

入力例 2

3
3 172 11 31
2 701 5
2 12 21

出力例 2

43651798

読み上げられる整数としてありうるものは \(11512, 11521, 31512, 31521, 172512, 172521, 1170112, 1170121, 3170112, 3170121, 17270112, 17270121\) です。

入力例 3

3
1 1000000000
1 1000000000
1 1000000000

出力例 3

999966190

この入力例では必ず \(100000000010000000001000000000\) が読み上げられます。

\(10^9+7\) で割った余りを求めることに注意してください。

入力例 4

10
5 371094 2597554 69382646 8 99062422 
12 6553139 40789 2519037 81594 46824888 84 4912 27575435 2774 4060 331605 7438162 
5 36 65156096 71969458 2 221919 
7 738734 979629710 4841 7027881 6107446 267092962 634173170 
9 16252 6294622 6670 932636725 8 221842 111612 86053044 823517544 
3 589 70 347090831 
9 7853 6 3174 1 14675 42 10793760 777031 23350 
15 5143 23971 93 68615 4384503 3 5867 96099 81021 10506439 137503 43398308 52626 9895727 3 
6 9819 93 808 2025523 36 593697 
3 497384 767669 80690

出力例 4

993753975

L - をあぷろぶれむ

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 700 点

問題文

いろはちゃんは、高橋君に次の問題を出されました。

非負整数列 A_1, A_2, \dots, A_N が与えられる。
1 \leq l \leq r \leq N を満たすすべての整数組 (l, r) に対し、A_l xor ... xor A_r を計算して黒板に書く。
上の操作によって黒板に書かれた N(N+1)/2 個の整数を大きい順に並べ直したとき、K 番目の数が何になるか答えよ。

いろはちゃんは、この問題をすでに「AtCoder甲子園」で解いたことがあります。そのことを高橋君に伝えると、「xor は or の書き間違い だった」と言われました。この発言の真偽はともかく、上の問題の xor を or に読み替えて 解きなおしてください。

制約

1 \leq N \leq 10^5
1 \leq K \leq N(N+1)/2
0 \leq A_i < 2^{60}
N,K,A_i は整数

入力

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

N K
A_1
A_2
\vdots
A_N

出力

高橋君に出された問題の xor を or に読み替えた ときの答えを 1 行に出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4