Codeforces Round #206(Div.2) 参戦記

出題やら時間が合わないやらの理由で、およそ半月ぶりのコンテスト参加となったのが今回のCodeforces Round #206。リハビリがてらのつもりでしたが、蓋をあけてみると…。

<参戦記>
取り敢えずAを読んで、すぐに答えを思いついたので、答えを書いて提出、一発Passed。ちょっと遅かったかな？と思いつつBを読むと、これもまたやるだけで、同じぐらいの時間で一発Passed。という事で、Cにうつる。読んでみて、DPなどせずとも直接式を出せそうだったので、計算式を出す。似たような総和計算が必要ということで、尺取り法で計算させて間に合うようにしてアップし、一発Passed。この段階で、Dを解いている人が少なかったので、Eに行くが、Eの間に合う解が見つからない。Dも全然わからない。諦めて、Standingsを見ていると、終了直前にEは100人以上がPretest Passed。
「え、これEだよな？割と虐殺が起こるのでは？」と思っていると、約1割しか通らない虐殺が起きて、順位が一気に上がりました。Systest前後でこれだけ順位が変わったのは久しぶりな気がします。

<Aの題意>
ある非負整数に対し、各位の総和を取る。この操作を、再度その総和に取る。これを繰り返すと、最終的には1桁の自然数となる。丁度$k$桁の自然数のうち、この操作の結果が$d$となるような数を1つ出力せよ。ただし、そのような数が存在しない場合は"No solution"と出力せよ。$k$は1000以下、$d$は0以上9以下。

<Aの解き方と感想>
入力例などにひっかかって難しく考えるとドツボにはまります。
最初に$d$を出力し、そのあと0を$k$回出力すれば終わりです。ただし、$d=0$かつ$k>1$の場合は、"No solution"です。
スマートな解をぱっと思いつくかどうかが勝負という感じです。

<Bの題意>
ある町には$n$のバス路線と、$m$のトロバス路線がある。この路線には、4種類の切符があり、次の通りである。

1.任意の路線に1回だけ乗れる切符。$c_1$という額で販売されている。
2.任意の1路線に好きなだけ乗れる乗り放題切符。$c_2$という額で販売されている。

3.バス路線ないしトロバス路線のみの乗り放題切符。バス路線版は全バス路線に、トロバス路線版は全トロバス路線に好きなだけ乗れる。いずれも$c_3$という額で販売されている。

4.全ての路線に好きなだけ乗れる乗り放題切符。$c_4$という額で販売されている。

ここまでの各パラメータと、バス路線の利用回数が入力される時、最安コストを求めるプログラムを作成せよ。

<Bの解き方と感想>
順に比較するだけです。まず、1の切符で路線毎に額を計算し、2の切符に置き換えるべき路線は2の切符に置き換えます。これにより、バス路線全体のコストとトロバス路線全体のコストが出るので、3の切符と比較して、置き換えるべきなら置き換えます。最後に両方のコストを足して、これが4の切符より高いなら4の切符に置き換えます。

似たような構造が3回ある問題で、2回にしてもおそらく問題としては成り立ちますが、実装量を稼ぐという観点からしても、これぐらいでいいのかなと思います。

<Cの題意>
$n$個の品物があり、各々の重さは$w_i$である。今、あるロボットにこの品物を全て取ってもらう。ロボットが出来る操作は「現在最も左側にある品物を左手で取る」「現在最も右側にある品物を右手で取る」の2種類である。ロボットが左手で$i$番目の品物をとった場合、$l\times w_i$のエネルギーコストがかかる($l$は定数)。同じく、右手で$j$番目の品物をとった場合、$r\times w_j$のエネルギーコストがかかる($r$は定数)。また、連続して同じ手を使った場合には余分なエネルギーコストがかかる。左手を連続して使った場合は都度$Q_l$のエネルギーコストが、右手の場合都度$Q_r$のエネルギーコストがかかる。各パラメータが与えられる時、エネルギーコストを最小化せよ。

<Cの解き方と感想>
左手で$N_l$個の品物を取る場合、右手で取るのは$n-N_l$個であり、このときどの品物がどちらの手に取られるかは一意に定まります。つまり、左側から$N_l$個目までは左手に取られ、他は右手に取られます。したがって、かかる連続コストの総和を$Q_s$とする時、全ての品物を取るのに必要なエネルギーコストは
\[
\sum^{N_l}_{k=1} lw_k +\sum^{n}_{k=N_l+1} rw_k + Q_s
\]
により計算できます。更に、$Q_s$は、左手と右手の回数がわかっている時、それをできるだけ交互に使うという戦略により簡単に最小値を求めることができます。
(多い側の回数-少ない側の回数-1)に、$Q_l,Q_r$のいずれか(多い側に対応しているもの)をかければ、$Q_s$になります。

先の式の総和部分に尺取り法を使えば、時間についても特にビクビクすることはないでしょう。直接導き出しましたが、DPの人も多かったようで、またその答えも見てみたいところです。

<結果のまとめ等>
ooo--,2730点,21位/1682人で、Ratingは1646->1753！初のDiv.1昇格となりました。が、正直次回から戦える気がしません…。
問題原文はこちら。

記念撮影

[A,AC (C言語)]

[B,AC (C言語)]

[C,AC (C言語)]