狠狠撸

狠狠撸Share a Scribd company logo

CODE FESTIVAL 予選B 解説

?Download as PPTX, PDF?
?
A
AtCoder Inc.

CODE FESTIVAL 予選B 解説

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

More Related Content

CODE FESTIVAL 予選B 解説