ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

京都大学プログラミングコンテスト(KUPC)2013

競プロの練習会で、こちらのセットを使用したバチャコンをチームで行ったので解いた問題についてのメモをしていきます。
チームメイトはICPC出場時と同じくやまさん(@yamasangamasan)、べるくん(@dora_marutation)でした。加えて、相手チームがICPC本戦出場チームであり実力差が大きいので、tossyさん(@tossy)に助っ人として考察、デバッグの手助けをしていただきました(この手助けがなかったらおそらく大変なことになっていたと思います…)。
自分はA問題を解き、その後CDEの実装を行いました。
というわけでこの4問についての方針をメモしておきます。

A - 旧総合研究7号館

提出コード
与えられた年に使われていた校舎の名称を答えよ、という問題です。
まず、入力を、年をキー、名称を値として記録します。その後、出力したい年から、名前が見つかるまで年をさかのぼっていく、というようにして答えを求めました。
元年の名前を記録しておくのも忘れないようにしましょう。

C - チョコレート

提出コード
辛いチョコレートを食べたときの減点がなく、またあるマスのチョコレートを食べたいときには、それより上のチョコレートがすべて食べ終えた状態になっていないといけないので、前提としてチョコレートは全て食べることにします(減点の部分についてはtossyさんに指摘されて気づきました)。
(i,j)マスのチョコレートを食べるとするとき、そのチョコレートの味が変わる可能性があるのは、その上下左右のマスのチョコレートを食べたときですが、(i,j)マスのチョコレートを食べるためには(i-1,j)にあるチョコレートは食べ終えてないといけません(なので、一番上の行以外のチョコレートは、必ず最低1回は味が変化していることになります)。加えて、食べたいチョコレートより下にある(i+1,j)のチョコレートを食べることはできません。
斜め下のチョコレートは味の変化に影響がないので、あとは左右、つまり(i,j-1)と(i,j+1)のチョコレートによってしか、味に影響がありません。
まとめると、それぞれの行について甘い味を食べる最大値を考えてから、最後に足し合わせれば答えを求めることができます。

ということで次に、ある行についての甘い味の最大値の求め方を考えます(iが1以外のときは、上の行のチョコを食べないといけないので、入力の時点で反転しているものとします)。
ある行について最初に食べることができるのは、両端にあるチョコレートのうちどちらか1つになります。つまり、最低でもそのどちらか一方は、味の反転を1度もせずに食べなければなりません。
次に、両端以外のチョコレートについて考えます。
両端以外のチョコレートを食べるには、少なくとも右側か左側のうち少なくともどちらか1つを食べないといけません。なので、少なくとも1回は味の反転をしなければなりません。
さて、少しでも甘い味のチョコレートを食べるためには、どのように食べればよいか、ということを考えたとき、その行の中で一番最後に食べるチョコレートが鍵となってきます。なぜなら、

  1. 両端にあるチョコレートなら、その行の最後に食べたときのみ、味を1回反転させて食べることができる

  2. 両端以外なら、少なくとも1回は味を反転させなければならなかったのが、最後に食べるチョコレートのみ、味をもとにもどすことができる

ということになるからです。
最後に食べることができるのは、多くても少なくても1粒なので、最後に食べるチョコは、途中で食べた場合だと辛い味になってしまうものを食べることにすれば、甘い味をより多く食べることができます。
逆に、全てのチョコレートが、途中で食べると甘い味になるもの(つまり、10001のようなパターン)は、最後に食べるものだけどうしても辛い味になってしまいます。
最初の上下の考察と合わせてうまくまとめ、処理の内容を書いていくと、

  1. 1番上の行以外について考える場合、まずその行のチョコの味をすべて反転させておく

  2. 両端はそのまま、両端以外の味を全て反転し、辛い味と甘い味の数をカウントする

  3. 辛い味のものが1つでもあれば、甘い味の数+1を、逆に1つもなかった場合は甘い味-1を、食べた甘い味の合計に加える

  4. 1~3をすべての行について繰り返し、最後に食べた甘い味の合計を出力する

となります。
…ここで考察を終えたいのですが、実は列の数(つまりn)が1だったときのみこの考察は適用外になっています。なので、nが1だった場合のみ、例外処理をしてあげる必要があります。具体的には、1を終えた時点でその行が甘い味になっていたら合計に1追加、そうでなければスルーする、という方針になります。

D - カーペット

提出コード
実際には、CよりDの方が方針がはやくたったので、先にこちらを通しています。
制約を見て、まずO(N^{2})が無理そうなのでO(N)O(NlogN)ぐらいにおさめないとなぁ、と感じます。
そして、入力や図とにらめっこすると、どうやらa_iが増えるたびに数字が増えている、ということがわかるので、そこをベースに考えていきます。
次に、これだけだと通らないケースを考えます。
n=3で、a_iが順に1、3、2であるようなケースを考えると、上の法則だと答えは2ですが、実際には3枚必要になることがわかります。
与えられたサンプルと見比べると、a_iの値がa_{i-1}より小さいときに、a_{i-2}a_iと一致していると据え置き、異なるときには+1枚されていることがわかります。
これらをまとめて実装するには、スタックを活用するとあっという間に解けてしまいます(この部分はtossyさんにヒントをいただきました)。
ということで、実装にあたっての処理をまとめると、
現在スタックの一番上の数字(はじめは0を入れておきます)と、a_iを比較して、

  • スタックのトップ>a_iであったらそうでなくなるまでスタックから要素を取り出す

  • 一致していたらそのまま、次の入力へ

  • スタックのトップ\lt a_iであったら、a_iをスタックに格納し、カーペットの枚数を一枚追加

という作業を繰り返すと、答えが求まります。

E - すごろく

提出コード
すごろくです。
基本的には、ゴールへ行く方法の存在がわかっているので、答えからスタートへの行き方を逆算していき、その行き方になるようなダイスの目を待ちます。
1手あたりの重みは特に変わらないので、幅優先探索で逆算をして…
というところで、tossyさんからさらにヒントをいただきました。
実は、ダイスには偏りがある可能性が存在します(例えば、1、1、1、1、1、2、のようなパターンです)。それに対応するために、1手あたりの重みをダイスの目によって変えていきます。
基本を10として、それをダイスの確率で割ります。上のパターンだと、1が5/6であり、2が1であるので、1手の重みは1が12、2が60になります。
この1手の重みを、辺の重みとみなし、幅優先探索ダイクストラ法にチェンジすることで、さらにゴールへ行く確率を上げます。
実装の順番としては、
まず、2次元配列memo[i][j]を作成し、現在i番にいるときに、ダイスでjが出たときに、ワープの処理をして最終的にたどり着く場所のメモをします(加えて、ダイスの目は正負どちらにも進むことができるので、3次元配列に拡張して両方を処理しました)。このとき、ダイスの目だけ進んだ時点で双六の範囲外にならないように気を付けます。
次に、そのメモをもとに、地点xに行く1手前の場所と、そこで出す必要があるダイスの目(正負も区別します)のペアを、xごとに分けて記録していきます。
その後、記録したペアをもとに、ダイクストラ法を用いてスタートからゴールまでの経路を作成します。ある地点で出す必要があるダイスの目を記録していきます。
最後に、ダイクストラ法で作成したメモをもとに、入力に対する動作を出力していきます。
この問題は、確実に通る、という確証がなかったのですが、無事に通すことができました。

残った時間でH問題を考えていましたが、歯がたちませんでした。後日実装したらまたメモをしようと思います。

2718/8/20追記
B、Hを通しました。というわけでメモをしていきます。

B - ライオン

提出コード
制限がとても小さいので、それぞれのオリに入れるライオンの数を全部試せば良いです。
それぞれのオリに入れるライオンの数を決めたら、これまた愚直に、来園者の情報と一致するかを見ていき、問題なければ最大値の更新を行います。探索が終わったら、最大のときのオリの情報を出力すればよいでしょう。

H - N and K

提出コード
めちゃくちゃ難しかったです。バチャコン終了後に、先輩から解法について説明していただいたのですが、消化しきれず、一日寝かせました。

前提として、c++同様、ここでの割り算はすべて切り捨てで計算します。
まず、nのときの最大の長さを求めます。これは、(n+1)/2となっています。
条件にあう数列を1つ簡単に上げると、(n+2)/2からnまでを全て羅列した数列は条件を満たしていますが、これに1つでも要素を追加しようとすると、追加しようとしている要素の2倍がすでに数列に含まれてしまっているので、この長さを超えることができません。
ということで、Kは(n+1)/2を超えていたら、-1を出力することになります。

これ以降は、Kが(n+1)/2以下であるとします。
次に、長さが(n+1)/2でかつ、全ての要素が最小の値になっているような数列を求めてみます。
仮にn=0のときを、長さ0の数列であるとしておきます。
任意のnのときの数列は、

  1. n-1のときの最適解となる数列をまずそのままコピーする

  2. nが奇数であれば、nを新しく数列の末尾に追加する

  3. nが3の倍数であったとき、n/3が存在すると条件を満たさなくなるので、n/3を、2倍した(n×2)/3と置き換える

  4. (n×2)/3が3の倍数であったとき、(n×2)/9があると条件を満たさなくなるので、(n×2)/9を、2倍した(n×4)/9と置き換える

  5. 置き換えたものが3の倍数である限り、4の操作を繰り返す(3で割った数を、その2倍と置き換える操作です)

という処理をすることで、前から順番に求めることができます。
例を挙げてみます。
n=9だとします。n=8のときは{2,3,5,7}です(これも1から順に、以下と同様の操作をすることで求めることができます)。

  1. n=8をコピーすることで{2,3,5,7}になります。

  2. 9は奇数なので末尾に追加します。{2,3,5,7,9}になります。

  3. 9を3で割ると3なので、これを2倍した6と置き換えます、昇順に並び替えて、{2,5,6,7,9}になります。

  4. 置き換えた6も3の倍数であり、これは3で割ると2なので、2を、2倍した4に置き換えます。{4,5,6,7,9}になります。

4は3の倍数ではないので作業を終了し、最終的な答えは{4,5,6,7,9}になります。

数列を求めることはできましたが、このままだと莫大な量の操作が必要になります。そこで、もう少し高速に求める方法を探します。
上の処理の内容からわかるように、奇数と、2^{i}倍したものに密接な関係があるので、それをうまく表にします(運営側の解説スライドの図を参考にしています)。nが小さいとわかりづらいので、解説スライド同様n=30を例にとってみることにします。
f:id:emtubasa:20180820172847p:plain
一番下の行に奇数を並べていきます。そして、それぞれの列の2倍、4倍、…2^{i}倍したものを積み重ねていくと、この図になります。
赤い数字が、最適解となる数列に採用されている数字になります。
図からもわかるように、1列につき1つの数字が採用されます。
そして、ある行の左端の、青い背景の数字をiとすると、その行は、初項2^{i}、公差2^{i+1}の等差数列になっています。
そして、それぞれの列の数字の採用の仕方ですが、
下の行から順番に見ていきます。
まだ決まっていない個数をxとしたとき(例えばi=0のときは15になります)、x-(x+1)/3個だけ、その行の右側から採用します。
これも例を見ていきます。
i=0のとき、x=15なので、x-(x+1)/3に当てはめ、10個だけ右側から順番に採用していきます。よって、11~29が採用されます。
i=1のとき、x=5になります。よって、x-(x+1)/3より、選べる部分の中から3つ採用するので、10,14,18が採用されます。
i=2のとき、x=2になります。上と同様にして、12だけ採用されます。
i=3のとき、x=1となります。8が採用されます。
というようにして、赤い数字が無事に採用されます。
この方法であれば、数列の最適解に採用される数字が先ほどと比べてだいぶ高速に求まります。

数字選び方がわかったところで、いよいよK番目の数字を探します。
下の行から順番に、採用される数字の中で二分探索をします。K番目の数字がなかったら、一つ上の行へ移動し、その行で同様に二分探索をします。これを繰り返します。
あとは、ある数が何番目の数字かを調べることができれば、上の操作を繰り返し行うことでK番目の数字を求めることができます。
というわけで、ある数をpとして、それが何番目の数なのかを求めます。
求め方は割と単純です。
下の行から順番に、p以下の数を数えていきます。
最適解の数列に含まれる含まれないを区別しないとき、i行目の数字は初項2^{i}、公差2^{i+1}の等差数列になっていることを思い出すと、p以下の数字の個数は(p+初項)/公差で求めることができます。
そして、その行の中で採用されない個数が、まだ選ばれていない列の数をxとしたときに(x+1)/3であったので、これを先ほどの個数から引けばいいです。
注意点がいくつかあります。
一つ目は、先ほどの図でp=29が何番目かを調べたいとき、上のままの処理を行うと、i=1では、22、26が個数として加算されてしまいます。
これは、i行目全体での、p以下の数字の個数をを{min(p,(x+1)/3)+初項}/公差とすることで対処できます。
二つ目は、p=8を調べたいとき、i=0では{min(p,(x+1)/3)+初項}/公差が4になりますが、ここから(x+1)/3を引くと、-1になります。-1個というのはありえないので、負になった場合は0になおしてあげる、という処理が必要になります。

以上より、pが何番目の数字かを求めることができます。これを、下の行から二分探索することで、答えを求めることができます。

2018/8/21追記
F問題も通しました!

F - 7歳教

提出コード
想定解は、区間の終点でソートしてからO(N^{2})のDPをして求めるそうです。
自分はO(N^{3})で通しました。
最初は想定解と同様、ワーシャルフロイド法を適用して、惑星iから惑星jへの最短経路をあらかじめ求めておきます。
また、ある惑星で布教活動を行うとしたとき、最善の選択肢は、必ず「その惑星で行うことができる時間いっぱいまで布教活動を行う」という選択肢になります(つまり、途中で仮に切り上げて別の惑星へ向かっても、いいことは何一つありません)。ということで、これ以降は布教活動する、ということは時間いっぱいまで行うという意味にします。
さて、その後の処理ですが、dp[i][k]として、i番目に惑星kで布教活動したときの、布教時間の最大値
とします。
すると、
dp[i][k] = max(dp[i][j]+jからkに移動して布教できる時間)
となります。
ただし、jからkに移動しても布教活動を行う時間がない場合、-1とします。
i=0のときは、スタート直後にsからkに移動して布教できる時間を格納しておきます。
あとは、i、j、kの3重ループで答えを求めます。dpの更新を行うたびに、最終的な答えの更新も行いましょう。そしてn=1のときのみ、コーナーケースになってしまうので、そこだけ愚直に求めてしまいます。



今回はACDEに加えて、べるくんがB問題も通して、全体でABCDEの5完でした。
細かいところや一番のポイントをtossyさんに教わっているので3人だと確実にこの量は通せない気がしますが、その分糧になったものが多いかなとは思います。
チームで挑んで5問だったので、この問題を1人でずばずばといていく、本番のコンテスト参加者の強さを思い知りました。