社内プロコンの問題作ったよ！(2回目)

というわけで前回に引き続き社内プロコン(一般)の問題を作りました。

問題は全部で4問で配点はこんな感じ。

	問題	満点
A	Bring Boarding Pass	50
B	Rita in Roma	100
C	Boarding is Boring	150
D	Souvenir Sequence	200

難易度は ABC を意識した難易度で作っていて、時間は3時間です。すべての問題について部分点がかならず設定されていて、一部でもあっていれば点数が入るようなテストデータになっています。

実はなんと今回D問題の案はけんちょんさんに作っていただきました！！！
ありがとうございました！！
本当にレベルも高い問題で感謝も大きく勉強することも多かったです。

A - Bring Boarding Pass

入力として $x, a, b$ が与えられて大きさ $x$ (S or L) の飛行機の前から $a$ 番目、左から $b$ 番目の座席番号を出力する問題。小さい飛行機が 33 の座席で大きい飛行機が 343 の座席です。入力例と出力例はこんな感じ。

入力 L 10 9
出力 10J

これは座席の英字が ABC DEFG HJK と言うようになっているので注意が必要ですねと言う問題でした。

B - Rita in Roma

ローマ数字をアラビア数字に変換する問題。入力例と出力例はこんな感じ。

入力 MMMCMXCIX
出力 3999

基本的には対応している数字を足していくのですが、4とか9の表記が減算側で表記されているのでそこに注意して変換を行えばいい問題でした。

C - Boarding is Boring

数字で遊ぶ問題です。入力として $a, b ( 0 \leq a, b \leq 10^5 )$ が与えられて、 $a$ に対して以下の3種類を行うことができます。

$a$ に2をかける
$a$ を2で割り小数点以下を切り捨てる
$a$ に1を足す

この3つの各操作を好きな回数行うことができるときに $a$ を $b$ にするための最小の操作回数を求めてくださいという問題です。ちなみに操作を行ったことによるオーバーフローなどは考えないとします。

入力例と出力例はこんな感じ。

入力 17 4
出力 2

この問題はC問題として出したのですが、コンテストが終わってみると通してる人がほとんどいなくてびっくりしました。
(思ったより難しかったみたい?)ちょっと反省

D - Souvenir Sequence

これはけんちょんさんにいただいた問題の原文が一番ようやくとしてわかりやすいのでそれを載せます。

$n$ 個の整数から成る数列 $a_1, a_2, \dots, a_n$ が与えられる。これを $K$ 個の連続する区間に分割して、各区間について総和をとって得られる数 $b_1, b_2, \dots, b_K$ の最大値を最小化したい。

これの最小値を求めてくださいという問題でした。制約は、

$2 \le K \le N \le 5000$
$0 \le a_i \le 1000$

部分点として $K = 1, 2, 3$ の時にそれぞれ50, 100, 150 点が入るようになっています。入力例と出力例はこんな感じ。

入力

5 2
3 6 7 1 9

出力

実は、案をいただいた時は $-1000 \le a_i \le 1000$ という制約だったのですが、この制約にすると、満点解法の難易度がAtCoderでいうと500点レベルになります。これだとさすがに社内で誰も解けないだろう、ということで泣く泣く制約を小さくさせていだたきました… この問題は各部分点に対しての解法がしっかりと考え込まれていて、これが競プロの上位の力かと思い知らされました。(すごい)