A - DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016に参加しようと考え、公式サイトを確認しています。 公式サイトにはDiscoPresentsDiscoveryChannelProgrammingContest2016とだけ書いてあります。

あなたが持っているPCのディスプレイは 1 行に W 文字までしか表示することができません。そのため、 W+1 文字目以降は改行され、次の行に表示されます。 具体的な表示例についてはサンプルを確認してください。

さて、あなたのPCのディスプレイではDiscoPresentsDiscoveryChannelProgrammingContest2016はどのように表示されているでしょうか？

入力

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

W
  • 1 行目に 1 行に表示可能な文字数を表す整数 W (1≦W≦51) が与えられる。

出力

表示結果を出力せよ。末尾の改行を忘れないこと。表示例についてはサンプルを確認せよ。

入力例 1

40

出力例 1

DiscoPresentsDiscoveryChannelProgramming
Contest2016
  • このケースにおいては 2 行にわたって出力が行われます。
  • このディスプレイは 1 行に 40 文字までしか表示することができないので 41 文字目からは次の行に表示されています。
  • 2 行目はContest2016の 10 文字が表示されています。余分な空白文字や改行、末尾の改行忘れには注意してください。

入力例 2

17

出力例 2

DiscoPresentsDisc
overyChannelProgr
ammingContest2016
  • このケースにおいては 3 行にわたって出力が行われます。
  • このディスプレイは 1 行に 17 文字までしか表示することができないので 18 文字目、 35 文字目からは次の行に表示されています。
  • 3 行目はammingContest2016の 17 文字が表示されています。余分な空白文字や改行、末尾の改行忘れには注意してください。

入力例 3

51

出力例 3

DiscoPresentsDiscoveryChannelProgrammingContest2016
  • このケースにおいては出力は 1 行に収まります。余分な空白文字や改行、末尾の改行忘れには注意してください。
B - ディスコ社内ツアー

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたはDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のディスコ社内ツアーの案内人です。

社内ツアーにおいて案内する部屋が N 箇所あり、それぞれの部屋には 1 から N の番号が割り振られています。建物の構造は環状となっており、 i(1≦i≦N-1) 番目の部屋から i+1 番目の部屋へと移動可能です。 N 番目の部屋からは 1番目の部屋へと移動可能です。これらの道は一方通行であり、逆向きに移動することはできません。

i 番目の部屋にいるとき、その部屋を見学するか隣の部屋へ移動するかどちらかを選ぶことが可能です。ただし、参加者に何度も同じ部屋を見学させると飽きてしまうため、見学はそれぞれの部屋につき 1 度しか行うことはできません。 あなたは社内ツアーを長年行ってきた経験から i番目の部屋を見学したときに得られる面白さはある整数 A_i で表されることを知っています。

社内ツアーは 1 番目の部屋から出発して、全ての部屋を見学し終わった状態で 1 番目の部屋にいるように終わらなくてはなりません。 あなたは参加者に社内ツアーを楽しんでもらうため、見学した部屋の面白さを見学した順番に並べたとき、広義単調増加列であるように部屋を案内することにしました。 このような制約のもとで社内ツアーを行うとき、建物内を最低何周する必要があるでしょうか？

ここで、 n 項からなる数列 a が a_1 ≦ a_2 ≦ ... ≦ a_n を満たすとき、 a は広義単調増加列であると呼ばれます。 また、 1 番目の部屋から移動し、全ての部屋を 1 度ずつ訪れて 1 番目の部屋に戻ってくることを、建物を 1 周すると呼びます。

入力

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

N
A_1 A_2 … A_N
  • 1 行目に案内する部屋の数 N (2≦N≦10^{5}) が与えられる。
  • 2 行目に各部屋の見学したときの面白さを表す整数 A_i (1≦A_i≦10^{5}) が空白区切りで与えられる。

出力

与えられた条件を満たすよう社内ツアーを行うのに必要な周回の回数の最低値を 1 行に出力せよ。末尾の改行を忘れないこと。

部分点

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

  • 2≦N≦100 を満たすデータセットに正解した場合 20 点が与えられる。
  • 1≦A_i≦Nかつi≠jにおいてA_i≠A_jが成立するようなデータセットに正解した場合上記の部分点とは別に 10 点が与えられる。
  • 追加制約のないデータセットに正解した場合さらに 70 点が得られる。

入力例 1

5
1 4 3 2 5

出力例 1

3
  • 下記のような順序で見学を行うことにより、 3 周で社内ツアーを終えることが可能です。 1 番目の部屋から出発し、すぐに 1 番目の部屋を見学することは許されています。ツアーは全ての部屋を見学し終えた状態で 1 番の部屋にいる状態で終わらなくてはならないことに注意してください。
  • 1 周目において、 1 番目の部屋と 4 番目の部屋を見学する。
  • 2 周目において、 3 番目の部屋を見学する。
  • 3 周目において、 2 番目の部屋と 5 番目の部屋を見学する。
  • このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。

入力例 2

5
1 2 3 4 5

出力例 2

1
  • 1 周目において、全ての部屋を見学することが可能です。
  • このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。

入力例 3

5
5 1 2 3 4

出力例 3

1
  • 最後に 1 番目の部屋を見学した直後にツアーを終了することで 1 周でツアーを終了することが可能です。
  • このケースは上記の部分点の 1 つ目の条件と 2 つ目の条件を満たします。

入力例 4

8
1 1 1 2 2 2 3 3

出力例 4

1
  • 部屋の面白さは重複しているものもあることに注意してください。
  • このケースは上記の部分点の 1 つ目の条件を満たしますが 2 つ目の条件は満たしません。
C - アメージングな文字列は、きみが作る！

Time Limit: 3 sec / Memory Limit: 256 MB

問題文

あなたはDISCO社の面接を受けています。 あなたは面接官から「英小文字だけからなる文字列 S を与えるので、ある 3 種類の操作から 1 つ選んで行うということをちょうど K 回だけ行ってあなたが考えるアメージングな文字列を作ってください」というお題を与えられました。

許されている操作は以下の 3 つです。

  1. 文字列 S の i(1≦i≦|S|) 文字目を削除する。
  2. 文字列 S の i(1≦i≦|S|) 文字目を別の英小文字で置換する。
  3. 文字列 S の i(1≦i≦|S|+1) 文字目に好きな英小文字を挿入する。

あなたは、 K 回の操作で作ることが可能な文字列のうち辞書順で最小のものを作って面接官を驚かせることにしました。

ここで、ある文字列 X について、 |X| は文字列 X の長さを表すものとします。
また、ある文字列 s=s_1s_2s_3...s_n と t=t_1t_2t_3...t_m について、以下のどちらかを満たすとき、辞書順比較で s<t であるといいます。

  • ある整数 i(1≦i≦min(n,m)) に関して、 1≦j<i を満たす任意の整数 j において s_j = t_j が成立し、かつ s_i<t_i が成立する。
  • 任意の整数 i(1≦i≦min(n,m)) に関して s_i = t_i が成立し、かつ n<m が成立する。

入力

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

S
K
  • 1 行目に面接官から与えられた英小文字だけからなる文字列 S (2≦|S|≦300,000) が与えられる。
  • 2 行目に行わなければならない操作回数を表す整数 K (1≦K≦|S|-1) が与えられる。

出力

S に対して K 回操作を行って作ることが可能な文字列のうち辞書順最小のものを 1 行に出力せよ。末尾の改行を忘れないこと。

部分点

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

  • 2≦|S|≦10, 1≦K≦min(|S|-1,4) を満たすデータセットに正解した場合は 10 点が与えられる。
  • 2≦|S|≦200を満たすデータセットに正解した場合はさらに 10 点が与えられる。
  • 2≦|S|≦1,000を満たすデータセットに正解した場合はさらに 20 点が与えられる。
  • 2≦|S|≦300,000を満たすデータセットに正解した場合はさらに 60 点が与えられ、合計 100 点が得られる。

入力例 1

abc
1

出力例 1

aabc
  • S の先頭にaを挿入した文字列aabcが 1 回の操作で作ることが可能な辞書順最小の文字列です。
  • このケースは、 1 番目の部分点の制約を満たします。

入力例 2

abc
2

出力例 2

a
  • S の 2 文字目と 3 文字目を削除した文字列aが 2 回の操作で作ることが可能な辞書順最小の文字列です。
  • このケースは、 1 番目の部分点の制約を満たします。

入力例 3

acb
1

出力例 3

aab
  • S の 2 文字目を置換した文字列aabが 1 回の操作で作ることが可能な辞書順最小の文字列です。
  • このケースは、 1 番目の部分点の制約を満たします。
D - DDPC特別ビュッフェ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

A 君と B 君はDISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016本戦のDDPC特別ビュッフェを楽しんでいます。 A 君のトレーには N 個の料理が、 B 君のトレーは M 個の料理が置かれています。 A 君のトレーにある i 番目の料理の美味しさは A_iで、 B 君のトレーにある j 番目の料理の美味しさは B_j で表されます。

とっても仲良しな 2 人はより昼食を楽しむため、A 君のトレーにある料理 1 つと、 B 君のトレーにある料理 1 つを交換するという操作をちょうど K 回行うことにしました。 A 君のトレーにある料理の美味しさの総和が a で、 B 君のトレーにある料理の美味しさの総和が b で表されるとき、 2人の幸福度は a×b で表されます。

K 回交換を行ったあとのありうる幸福度のうち、最大の値を求めなさい。

入力

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

N M K
A_1 A_2 … A_N
B_1 B_2 … B_M
  • 1 行目に A 君と B 君の持っている料理の数を表す整数 N, M (1≦N,M≦55) と料理の交換回数 K(1≦K≦999) が与えられる。
  • 2 行目に A 君のトレーに置かれている i 番目の料理の美味しさを表す整数 A_i (0≦A_i≦22,222) が空白区切りで与えられる。
  • 3 行目に B 君のトレーに置かれている j 番目の料理の美味しさを表す整数 B_j (0≦B_j≦22,222) が空白区切りで与えられる。

出力

ありうる 2 人の幸福度の最大値を 1 行に出力せよ。末尾の改行を忘れないこと。

部分点

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

  • K=1 を満たすデータセットに正解した場合 10 点が与えられる。
  • 0≦A_i,B_j≦55を満たすようなデータセットに正解した場合上記の部分点とは別に 20 点が与えられる。
  • 追加制約のないデータセットに正解した場合さらに 70 点が得られ合計 100 点が得られる。

入力例 1

3 2 1
2 2 3
3 2

出力例 1

36
  • A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。

入力例 2

3 2 2
2 2 2
3 3

出力例 2

36
  • 1 回目の交換で A 君のトレーにある美味しさ 2 の料理と B 君のトレーにある美味しさ 3 の料理を交換し、 2 回目の交換で A 君のトレーにある美味しさ 3 の料理と B 君のトレーにある美味しさ 2 の料理を交換すると 2 人の幸福度は 36 となり、これが最大の幸福度です。