CODE FESTIVAL 2014 予選B 解説 AtCoder株式会社 代表取締役 高橋 直大 2014/10/27 1 A問題 あるピアニスト 2014/10/27 ©AtCoder Inc. All rights reserved. 2 2 A問題 • 問題概要 – 2つの整数A,Bが与えられる。 – 大きい方を出力してください。 • 解説 – 比較演算子とif文を使って場合分けする – 諸言語で予め実装されているmax関数等を使う 2014/10/27 3 B問題 歩く人 2014/10/27 ©AtCoder Inc. All rights reserved. 4 4 B問題 問題概要 • 要素数Nの数列Aが与えられる。 • A[ 1]～A[i]の総和がKを超える最小のiを求めよ。 • 制約 – 1 ≦ N ≦ 100,000 – 1 ≦ A[i] ≦ 100,000 – 1 ≦ K ≦ 1,000,000,000 2014/10/27 5 B問題 アルゴリズム • 毎日、その日までに累計で何歩歩いたか求める。 – 累計歩数を保存しておく別の変数を用意してそれ に次々A[i]を足していけば良い。 • 各日について累計K歩を達成できたか求める。 – 簡単なif文 • 初めて累計K歩を達成した日を出力すれば良い。 2014/10/27 6 C問題 錬金術士 2014/10/27 ©AtCoder Inc. All rights reserved. 7 7 C問題 問題概要 • 2N( Nは整数) 文字の文字列S1, S2,S3がある • S1の半分とS2の半分を取ってきて並び替えることで S3が構成可能か判断せよ。 • 制約 – 2 ≦ 2 N ≦ 100,000 – S1,S2,S3は大文字アルファベットのみから構成される 2014/10/27 8 C問題 アルゴリズム • 構成する際に並び替えることができるので、S1,S2,S3 の文字列の順番は答えに影響しない – 各アルファベットを何個ずつ含むかだけが必要 • まずはN文字ずつ取り出すという制約を無視する – 取り出し方をアルファベットごとに独立して考えることが出 来る – 例えば「'A'をS1から何個取り出すか」と「'B'をS1から何個 取り出すか」は全く影響しあわない 2014/10/27 9 C問題 アルゴリズム • 各アルファベットについてS1から取り出すことが出 来る文字数の範囲を求める • S1から取り出す文字数が少なすぎると、S2から取り 出す文字数にかかわらず、S3を構成するのに足り なくなる – 例：S1='AABB' S2='AAAB' S3='ABBB'のときS1から' B 'を 1つしか取り出さないとすると、S３を構成できなくなる 2014/10/27 10 C問題 アルゴリズム • 各アルファベットについてS1から取り出すことが出 来る文字数の範囲を求める • S1から取り出す文字数が多すぎると、S2から取り出 す文字数にかかわらず、S3を構成するのに余ってし まう – 例：S1=‘AAAB’ S2=‘AABB’ S3=‘ABBB’のときS1から‘ A’を3つも取り出すとすると、S３を構成するのに余ってし まう 2014/10/27 11 C問題 アルゴリズム • 各アルファベットについてS1から取り出すことが出 来る文字数の範囲を求める • あるアルファベットがS1,S2,S3にそれぞれC1,C2,C3 文字ずつ含まれていたとすると、S1から取り出すこ とが出来る文字数の範囲は – max(0, C3-C2) ～ min(C1, C3) – この間の値は全てとれる 2014/10/27 12 C問題 アルゴリズム • 各アルファベットについてこの範囲をもとめて、うまく 総和がN/2にすることが出来るか判断すれば良い • できるだけ少なくS1から取り出した時の文字数と、で きるだけ多くS1から取り出した時の文字数の間に N/２があるかどうか判断する。 – それぞれさきほどの max(0,. C3-C2) ～ min(C1, C3) の 総和を取れば求めることが出来る 2014/10/27 13 D問題 登山家 1. 問題概要 2. アルゴリズム 2014/10/27 ©AtCoder Inc. All rights reserved. 14 14 D問題 問題概要 • 要素数Nの数列Aが与えられる。 • 各i( 1≦i≦N)に対してiとjの間の全てのk( jも含む)に ついてA[k]≦ A[ i]であるようなjの個数を求めよ。 • 制約 – 1≦N≦ 100,000 – 1≦A[i]≦100,000 2014/10/27 15 D問題 アルゴリズム • 図示 2014/10/27 16 D問題 アルゴリズム • 山小屋iから見える範囲 2014/10/27 17 D問題 アルゴリズム • 山小屋iから見える範囲 • これはiを含むある区間である • iに一番近いh[i]より高い山小屋が両端となる 2014/10/27 18 D問題 アルゴリズム • • • • 山小屋iから見える範囲 これはiを含むある区間である iに一番近いh[i]より高い山小屋が両端となる 両端をどう求めるか？ – 全探索 – DP – stackをつかう – 二分探索 2014/10/27 19 D問題 アルゴリズム • • • • 山小屋iから見える範囲 これはiを含むある区間である iに一番近いh[i]より高い山小屋が両端となる 両端をどう求めるか？ – 全探索 – DP – stackをつかう – 二分探索 2014/10/27 20 D問題 アルゴリズム • 山小屋iがそれより東の山小屋をどこまで見る ことが出来るかを求める – 山小屋iから東向きに順番に調べていき、初めて 見えなくなった山小屋の一つ前まで見える 2014/10/27 21 D問題 アルゴリズム • 例 2014/10/27 22 D問題 アルゴリズム • OK 2014/10/27 23 D問題 アルゴリズム • OK 2014/10/27 24 D問題 アルゴリズム • OK 2014/10/27 25 D問題 アルゴリズム • NG 2014/10/27 26 D問題 アルゴリズム • 3つまで見える 2014/10/27 27 D問題 アルゴリズム • 西側についても同様に求めて最後に足し合 わせる • 各iについてO(N)かかる – 合計でO(N^2) – 部分点(30点)が得られる 2014/10/27 28 D問題 アルゴリズム • • • • 山小屋iから見える範囲 これはiを含むある区間である iに一番近いh[i]より高い山小屋が両端となる 両端をどう求めるか？ – 全探索 – DP – stackをつかう – 二分探索 2014/10/27 29 D問題 アルゴリズム • dp[i] = 山小屋iの東側で見えない山小屋の中で最 も西にあるもの • 先ほどの例でNGにあたる山小屋 2014/10/27 30 D問題 アルゴリズム • NG 2014/10/27 31 D問題 アルゴリズム • 東から順番にdp[i]の値を埋めていく • dp[i] = i+1 • h[dp[i]] > h[i]になるまでdp[i] = dp[dp[i]]という代入 をしつづける 2014/10/27 32 D問題 アルゴリズム • 例 2014/10/27 33 D問題 アルゴリズム • 一番東に無限に高いhをもつ番兵をつくると実装し やすい 2014/10/27 34 D問題 アルゴリズム • dp[i] = i+1から開始 2014/10/27 35 D問題 アルゴリズム • dp[i] = i+1から開始 2014/10/27 36 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 37 D問題 アルゴリズム • dp[i] = i+1から開始 2014/10/27 38 D問題 アルゴリズム • dp[i] = i+1から開始 2014/10/27 39 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 40 D問題 アルゴリズム • dp[i] =i +1から開始 2014/10/27 41 D問題 アルゴリズム • dp[i] =i +1から開始 2014/10/27 42 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 43 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 44 D問題 アルゴリズム • dp[i] =i +1から開始 2014/10/27 45 D問題 アルゴリズム • dp[i] =i +1から開始 2014/10/27 46 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 47 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 48 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 49 D問題 アルゴリズム • dp[i] =i +1から開始 2014/10/27 50 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 51 D問題 アルゴリズム • h[i] ≧ h[dp[i]]なのでdp[i] をdp[dp[ i]]に更新する 2014/10/27 52 D問題 アルゴリズム • dp[i] = dp[dp[i]]という操作を最悪でO(N)回するので 総計算量はO(N^2)？ – 実はO(N) • dp[i] = dp[dp[i]]という操作（先ほどの例では黒い矢 印をたどること）は各矢印についてたかだか1回しか 行われない – 矢印はO(N)個しかないので総計算量はO(N) • 満点が得られる 2014/10/27 53 D問題 アルゴリズム • dp[i] = dp[dp[i]]という操作を最悪でO(N)回するので 総計算量はO(N^2)？ – 実はO(N) • dp[i] = dp[dp[i]]という操作（先ほどの例では黒い矢 印をたどること）は各矢印についてたかだか1回しか 行われない – 矢印はO(N)個しかないので総計算量はO(N) • 満点が得られる 2014/10/27 54 D問題 アルゴリズム • • • • 山小屋iから見える範囲 これはiを含むある区間である iに一番近いh[i]より高い山小屋が両端となる 両端をどう求めるか？ – 全探索 – DP – stackをつかう – 二分探索 2014/10/27 55 D問題 アルゴリズム • stackを用意する • 東から順番に – h[i] が h[ stackの先頭]より大きい限りstackの先頭をpop し続ける – dp[ i] = stackの先頭 – iをstackの先頭にpushする • というふうにやると先ほどと同じdp[i]が得られる • 実質やっていることはDP解と同じ – こちらのほうがO(N)であることがわかりやすい 2014/10/27 56 D問題 アルゴリズム • • • • 山小屋iから見える範囲 これはiを含むある区間である iに一番近いh[i]より高い山小屋が両端となる 両端をどう求めるか？ – 全探索 – DP – stackをつかう – 二分探索 2014/10/27 57 D問題 アルゴリズム • iについて、h[i]より高い山小屋の位置が全てわかっ ていれば、二分探索(Successor)で見える範囲の両 端を求めることが出来る • 高い順に山小屋を追加していき、毎回二分探索す れば良い 2014/10/27 58 D問題 アルゴリズム • 例 2014/10/27 59 D問題 アルゴリズム • 例 2014/10/27 60 D問題 アルゴリズム • 例 2014/10/27 61 D問題 アルゴリズム • 例 2014/10/27 62 D問題 アルゴリズム • 例 2014/10/27 63 D問題 アルゴリズム • 例 2014/10/27 64 D問題 アルゴリズム • 例 2014/10/27 65 D問題 アルゴリズム • 例 2014/10/27 66 D問題 アルゴリズム • 例 2014/10/27 67 D問題 アルゴリズム • 例 2014/10/27 68 D問題 アルゴリズム • 例 2014/10/27 69 D問題 アルゴリズム • h[i]が大きい順にiをset等のデータ構造に追加して いく • 追加する前にiのupper_boundとその前を調べる • 高さが同じ山小屋が複数あるときは、すべてについ て二分探索をした後にsetに追加する • 総計算量は – O(NlogN) 2014/10/27 70 D問題 アルゴリズム • この解法を思いつく人が一番多いと予想される • しかし、挿入と探索が効率的にできるデータ構造を 実装するのはコンテスト時間内では慣れていないと 難しい – set等が予め用意されていない言語だと、この解法は実装 しづらい – そういう時は先程のDPやstackを使った解法を実装すれ ば良い 2014/10/27 71
© Copyright 2024 ExpyDoc
