トップ > プロコン > JOI 2015/2016 本選（オープンコンテスト）

JOI 2015/2016 本選（オープンコンテスト）

プロコン

まだ3問目までしか解いてないです。4,5問目は難しくて解けません。

しかし、修羅場になると予想された1問目〜3問目まで全てDPとは、手抜きなのか…4,5問目は修羅場か。

A:オレンジの出荷 (Oranges)

問題概要

オレンジがN個ベルトコンベアに1列に並んで流されてくる。これらをいくつかの段ボールに梱包するのだが、1つの段ボールにつき、その中の最も大きいオレンジの大きさをA、最も小さいオレンジの大きさをB、段ボールの中のオレンジの個数をSとした時、コストがK+S(A-B)かかる。段ボールは大量にあるが、1つの段ボールにつきM個までしか梱包できない。

オレンジN個梱包する最小コストはいくつか。

解説

最初、アップロードされたサンプルには答えがありませんでした()

更に「段ボールの中の個数はダンボール毎に異なっていて構わない」という条件を見逃したので、新しい問題をダウンロードして気づくまで2時間半。死亡です。

DP[i][j]:i番目のオレンジを見ているとき、現在使っている箱の中にj個入っている時の1〜(i-1)個までのオレンジを入れるコスト

とでも定義しましょう（厳密には違います）。

こうすると、各状態から次のオレンジへと進む操作は

  • 今使っている箱にそのままオレンジを追加する

  • 今使っている箱は打ち切り、そのオレンジは新しい箱に入れる

の2パターンです。配るDPをしていくのですが、上の中で、1つ目の操作ではコストは変更せず、AとBのみを更新します。2つ目の捜査ではAとBを新しいオレンジの大きさにし、今まで使っていた箱のコストをDPに追加します。O(NM)。

この時点で気づいていると思いますが、配列にDPだけでなくAとBも同じ要素数必要です。

なお、JOIのテストシステムではN×Mの2次元配列を用いるとMLE判定されるので、2×Mで使いまわします。

https://github.com/HyogaGlacier/Other-Programing-Contest/blob/master/2016-ho-t1.cpp

誤読といい、MLEといい、災難な問題でした。

B:スタンプラリー 2 (Collecting Stamps 2)

問題概要

商店街ではN店の店が1直線に並んでいる。この商店街でスタンプラリーを行うらしく、スタートからゴールまでにJ、O、Iのスタンプを順番に3店回って押してもらわなくてはならない。ここで、新しく1店が商店街に来ることになっている。既存のN店舗がどのスタンプを扱うのかが与えられるので、新しい1店舗を任意の店の間に設置し、任意のスタンプを扱った時、最大何通りの訪れ方があるのか求めよ。

解法

取り敢えず、「答え＝既存の店だけでの訪れ方＋新しい店を訪れる訪れ方の最大値」と変形できます。

まずは既存の店のみを使った訪れ方。

DP[i][j]:i番目の店の前にいて、現在のスタンプはj個押してもらっている通り数

と定義すると、

  • その店によることでスタンプラリーが進むとき、その店を訪れる

  • その店は訪れない

の2通りが有ります。スタンプラリーの進捗はJが押されたら1、JOと続いたら2、JOIと揃ったら3です。

状態3の時は問答無用で2つ目の行動だけを行います。後は作業で既存の店のみを訪れる通り数は求まります。

問題は新しい店。もし、新店舗が扱うのが

  • Jのスタンプなら、新店舗よりも後に何通りOIとスタンプを押せる店の組み合わせがあるのか

  • Oのスタンプなら、新店舗よりも前にいくつJを扱う店があり、新店舗より後にいくつIを扱う店があるのか

  • Iのスタンプなら、新店舗より前に何通りJOとスタンプを押せる店の組み合わせがあるのか

が分かれば良さそうです。OIの組み合わせとJOの組み合わせについては先程のDPと同じように行います。ただし、OIは店Nから後ろ向きに行います。

真ん中のパターンは単純に累積和を取ればOKです。Iの数はOIと同様後ろから行います。

これらが分かれば、

  • 新店舗より後のOIの通り数

  • 新店舗より前のJの数×新店舗より後のIの数

  • 新店舗より前のJOの数

の最大値を新店舗の各位置で求めればOKです。O(N)。

https://github.com/HyogaGlacier/Other-Programing-Contest/blob/master/2016-ho-t2.cpp

C:鉄道運賃 (Train Fare)

問題概要

N個の都市が有り、2都市を繋ぐ鉄道がM有ります。各鉄道の運賃は1です。Q年間に渡り、1年に1線、運賃が1の線の運賃を2に値上げします。

各都市から都市1へ行く最低運賃が値上がりすると、その都市の住民は不満に思います。値上げ開始前に比べ、Q年間の各年で何都市の住民が不満を持っているか求めてください。

解説

この問題はなぜかMLE判定を受け続けている（原因は不明）ため、完全に合っているとは言えないかもしれませんが、参考程度に。

都市i→都市1の最低運賃＝都市1→都市iの最低運賃です。よって都市1からダイクストラをすれば各都市値上げ開始前の最低運賃が分かります。

ここで、各線が値上げする毎にダイクストラをやり直していてはキリがありません。1回目のダイクストラでどの線が切れたら最低運賃で都市1へ行けなくなるかが分かればOKです。

よって、各都市に最低運賃だけでなく、いつ不満に思う予定かも記録していきます。コストが更新できるときは、必ず不満になるタイミングも更新します。コストが一致した時（＝そこへ向かう最短ルートが複数ある場合）は2ルートのうち、不満になるタイミングが遅い方を適用します。

後は情報処理。

https://github.com/HyogaGlacier/Other-Programing-Contest/blob/master/2016-ho-t3.cpp

なんでMLEを食らうんだろう…

感想

本選のボーダーは241点。

初めの3問は全部難しくないDPだし、本選に行った人は殆ど全員解けているものだと思ったのだけれど…予選で事故った自分が悔しい。

4,5問目は難しそうなので、先に他の優先順位の高い問題（DDPC予選のCとか）を片付けたい。