DDPC 2016 予選 解説

40 %
60 %
Information about DDPC 2016 予選 解説

Published on January 30, 2016

Author: chokudai

Source: slideshare.net

1. DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 解説 AtCoder株式会社 3/19/15

2. A: DISCO presents ディスカバリーチャンネル プログラミングコンテスト 2016

3. 問題概要 • DiscoPresentsDiscoveryChannelProgrammingContest2016 という文字列を W 文字ごとに改行して出力せよ

4. 解法 • 問題文に書かれている通り 1 行に W 文字までしか 出力しないようにすればよい • for文などを用いて実装すればよい – 余分な改行や空白文字をつけないように注意すること

5. B: ディスコ社内ツアー

6. 問題概要 • 一方通行の環状道路のような N 頂点の有向グラフが 与えられる • 頂点には 1 から N のインデックスがついている • 頂点 i にはある整数 Ai が書かれたスイッチがあり 一度だけ押すことができる • 頂点 1 から出発し,各頂点にあるスイッチ全てを 押した状態で頂点 1 に戻る – その際,スイッチに書かれた整数を,押した順序で並べた 数列が広義単調増加列になるようにしたい • 最低何周必要か?

7. 部分点1 ( N ≦ 100, Ai は重複しうる) • それぞれの頂点にある整数たちを並べた数列をソート することにより i 番目に訪れることになる頂点が持つ 値が分かる • 愚直に頂点を移動して何周必要か求めればよい – 計算量は O(N2)

8. 部分点2 (与えられる数列が順列) • N が最大 105 と大きいので愚直に試すことはできない • 与えられる数列が順列なので,今見ている値が x なら 次の値は x + 1 である • pos(x)をAi = x であるような頂点の位置としたとき, pos(x + 1) > pos(x) のとき,頂点 1 を通過しなくては ならない • 計算量は O(N)

9. 満点 ( N ≦ 105 , Ai は重複しうる) • 順列の場合では次の位置が簡単に求められた – 各頂点が持つ値に重複や抜けがある場合はどうか? 1 2 3 4 5 6 1 5 3 5 1 3

10. 満点 ( N ≦ 105 , Ai は重複しうる) • 順列の場合では次の位置が簡単に求められた – 各頂点が持つ値に重複や抜けがある場合はどうか? • 1 周目: 1, 5, 6 番目の頂点のスイッチを押す 1 2 3 4 5 6 1 5 3 5 1 3

11. 満点 ( N ≦ 105 , Ai は重複しうる) • 順列の場合では次の位置が簡単に求められた – 各頂点が持つ値に重複や抜けがある場合はどうか? • 1 周目: 1, 5, 6 番目の頂点のスイッチを押す • 2 周目: 3, 4 番目の頂点のスイッチを押す 1 2 3 4 5 6 1 5 3 5 1 3

12. 満点 ( N ≦ 105 , Ai は重複しうる) • 順列の場合では次の位置が簡単に求められた – 各頂点が持つ値に重複や抜けがある場合はどうか? • 1 周目: 1, 5, 6 番目の頂点のスイッチを押す • 2 周目: 3, 4 番目の頂点のスイッチを押す • 3 周目: 2 番目の頂点のスイッチを押す 1 2 3 4 5 6 1 5 3 5 1 3

13. 満点 ( N ≦ 105 , Ai は重複しうる) • 目的となる数列は{1, 1, 3, 3, 5, 5}になる • 訪れる順序は以下のようになる – 1 の始点は頂点 1 , 1 の終点は頂点 5, – 3 の始点は頂点 6 , 3 の終点は頂点 3 – 5 の始点は頂点 4 , 5 の終点は頂点 2 • Ai の値ごとに数列を分けることを考える 1 2 3 4 5 6 1 5 3 5 1 3

14. 満点 ( N ≦ 105 , Ai は重複しうる) • Ai の値ごとに数列を分けることを考えると, – Ai = 1 で調べる必要がある頂点は 2 つ 1 2 3 4 5 6 5 5 3 3 1 1

15. 満点 ( N ≦ 105 , Ai は重複しうる) • Ai の値ごとに数列を分けることを考えると, – Ai = 1 で調べる必要がある頂点は 2 つ – Ai = 3 で調べる必要がある頂点は 2 つ 1 2 3 4 5 6 5 5 3 3 1 1

16. 満点 ( N ≦ 105 , Ai は重複しうる) • Ai の値ごとに数列を分けることを考えると, – Ai = 1 で調べる必要がある頂点は 2 つ – Ai = 3 で調べる必要がある頂点は 2 つ – Ai = 5 で調べる必要がある頂点は 2 つ 1 2 3 4 5 6 5 5 3 3 1 1

17. 満点 ( N ≦ 105 , Ai は重複しうる) • 愚直に周回してもそれぞれの頂点を調べる回数は 定数回で済む! 1 2 3 4 5 6 5 5 3 3 1 1

18. 満点解法まとめ • 各頂点を Ai の値ごとに振り分ける – バケットソートにより O(N) で行うことが可能 • Ai = x であるような頂点たちに対し,最後に訪れた 位置を覚えておいて,始点を検索 + シミュレーション – このとき,それぞれの頂点を訪れるのは定数回で済む – よって計算量は O(N) で抑えられる • 全体の計算量はO(N) 1 2 3 4 5 6 5 5 3 3 1 1

19. C: アメージングな文字列は、 きみが作る!

20. 問題概要 • 文字列 S にちょうど K 回以下の操作を行った文字列 のうち、辞書順最小のものを求めよ – S の好きな位置に一文字挿入する – S の好きな位置にある文字を一文字削除する – S の好きな位置にある文字を別の文字に置換する

21. 部分点1: ( |S| ≦ 10, K ≦ min(|S| – 1 , 4)) • どのような編集を行うか全て試す – 深さ優先探索などを用いればよい – ただし,辞書順最小の定義より,置換と挿入は以下の 2 種類のみ考慮すればよい • a 以外の文字を a に置換する • a を挿入する • b や z などの文字を使うより明らかに辞書順で小さくなる – |S| も K も小さいので十分間に合う

22. 部分点2: ( |S| ≦ 200) • 先ほどの解法を動的計画法を用いて状態を減らす • dp(i, j) を S の i 文字目まで見て残り j 回編集可能な ときに作ることが可能な辞書順最小の文字列とする • 現在の状態を dp(i, j) としたとき,遷移は以下の4種類 – 今見ている文字をそのまま使用(dp(i + 1, j)へ) – 今見ている文字を削除する(dp(i + 1, j + 1)へ) – 今見ている文字の前に一文字挿入する(dp(i + 1, j + 1)へ) – 今見ている文字を置換する(dp(i + 1, j + 1)へ) • 状態数が O(|S|2),文字列の比較に O(|S|) かかるので, 全体の計算量は O(|S|3)

23. 考察1 • S = abcacb のときを考える • K = 0: abcacb • K = 1: aabcacb • K = 2: aaaacb • K = 3: aaaaab • K = 4: aa • K = 5: a

24. 考察1 • 辞書順最小の定義より,以下の性質が分かる – K 回以下の操作で,S を文字 a だけからなる文字列にする ことが可能ならば⾧さを最小にするのがよい – そうでない場合は,先頭から連続する文字 a の個数を最大 にするのがよい

25. 考察1 • 辞書順最小の定義より,以下の性質が分かる – K 回以下の操作で,S を文字 a だけからなる文字列にする ことが可能ならば⾧さを最小にするのがよい • S に含まれる文字 a の個数と K の和が |S| 以上か調べればよい – そうでない場合は,先頭から連続する文字 a の個数を最大 にするのがよい • K = 2の例のように S 中に含まれる a を使うことで, a の挿入より a への置換の方が先頭から連続する a の個数を増やせることがある

26. 考察2 • 先頭から連続する a の個数の最大値が,置換操作でも 挿入操作でも変化しないとき,どうするか? • S = cacbxbyzzzz, K = 4 について考える – 一文字目を a に置換することで,先頭から連続する a の 個数は最大 5 にすることが可能 – 残り 3 回,どのように置換,挿入を行うか?

27. 考察2 • 先頭から連続する a の個数の最大値が,置換操作でも 挿入操作でも変化しないとき,どうするか? • S = cacbxbyzzzz, K = 4 について考える – 一文字目を a に置換することで,先頭から連続する a の 個数は最大 5 にすることが可能 – 残り 3 回,どのように置換,挿入を行うか? • 3 文字目の c を a に置換,その後先頭に a を 2 回挿入するのが最適 1 2 3 4 5 6 7 8 9 10 11 c a c b x b y z z z z c b x b y z z z z b x b y z z z z x b y z z z z

28. 考察2 • 先頭から連続する a の個数の最大値が,置換操作でも 挿入操作でも変化しないとき,どうするか? • S = cacbxbyzzzz, K = 4 について考える – 一文字目を a に置換することで,先頭から連続する a の 個数は最大 5 にすることが可能 – 残り 3 回,どのように置換,挿入を行うか? • 3 文字目の c を a に置換,その後先頭に a を 2 回挿入するのが最適 • 候補となる i (3≦i≦5) 文字目を先頭とする接尾辞のうち 辞書順最小のものを選ぶのが最適ということ 1 2 3 4 5 6 7 8 9 10 11 c a c b x b y z z z z c b x b y z z z z b x b y z z z z x b y z z z z

29. 部分点 3: ( |S| ≦ 1,000) • 文字 a だけからなる文字列が作れるならば 可能な限り削除を行い⾧さ最小の文字列を作る • 先頭から連続する文字 a の個数が最大になるように, 先頭から a 以外の文字を a に置換する • 先頭から連続する文字 a の個数が同じになるような 範囲では,選べる接尾辞のうち最小のものを選ぶ • 文字列の比較に O(|S|),最大 O(|S|) 回比較を行うので, 全体の計算量は O(|S|2)

30. 満点: ( |S| ≦ 300,000) • 文字列 S の接尾辞たちの辞書順における位置を高速に 求めたい • 接尾辞配列(suffix array)と呼ばれるデータ構造が存在 – これは S の接尾辞たちの開始位置を要素とする配列を, 接尾辞について辞書順に並び替えて得られる配列 – O(|S|)で構築することが可能

31. 満点解法まとめ • 文字 a だけからなる文字列が作れるならば 可能な限り削除を行い⾧さ最小の文字列を作る • 先頭から連続する文字 a の個数が最大になるように, 先頭から a 以外の文字を a に置換する • 先頭から連続する文字 a の個数が同じになるような 範囲では,選べる接尾辞のうち最小のものを 接尾辞配列に従って選ぶ • 全体の計算量は O(|S|)

32. D: DDPC特別ビュッフェ

33. 問題概要 • N 個の非負整数からなる数列 A と M 個の非負整数 からなる数列 B が与えられる • A の要素 1 つと B の要素 1 つを交換する操作を ちょうど K 回行ったときの ΣA ΣBを最大化せよ

34. 部分点1: (K = 1) • 交換する組み合わせを愚直に全て試せばよい • 計算量は O(NM)

35. 考察1 • A と B の要素の総和は常に一定 – ΣA = ΣBのとき,ΣAΣBが最大となる – A から B へ移動した要素の総和を a, B から A へ移動した要 素の総和を b とすると,交換したあとの得点は (ΣA – a + b)(ΣB – b + a)で表せる • K 回の交換操作で出来る限り ΣA とΣB を近づけたい

36. 考察2 • A から B へと移動した要素が k 個のとき, B から A へと移動した要素は常に k 個 – そうでないとすると,交換という操作に矛盾 • K 回の操作で, A から B へ何個移動させられるか? – K = 1: 1 – K > 1: 0, 1, 2, …, min(N, M, K) • K > 1のとき, 0 以上 min(N, M, K) 以下の任意の個数を移動可能 • 交換操作は以下の 3 種類で考えればよい – もともと A にあった要素を新たに 1 個移動させる – もともと A にあった要素を B から A へ 1 個移動させる – もともと A にあった要素同士を交換する • N = 1, M = 1 のときは成り立たないが,あまり気にしなくてよい

37. 部分点2: (max(Ai, Bj) ≦ 55) • 動的計画法を用いる – ΣA が定まると ΣB も定まることに着目する – dp(i, j) = B から A に i 個移動させる必要がある時の A の 要素の総和が j であるような操作はあるか? • 典型的なナップサック問題 – A の要素を詰め終わったあと, i > min(N, M, K) である dp(i, j) を全て偽にする • min(N, M, K) より多くの要素を交換することは出来ない – B の要素を詰めたあと,dp(0, x) が真である x について x(C – x) の最大値を調べればよい • ここで C はΣA + ΣB とする • 計算量はO((N + M)2max(ΣA))

38. 満点: (max(Ai, Bj) ≦ 22,222) • bool 値を返すようなDPは状態数を削減可能なことが ある • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • 部分点解法のdp(i, j) の i が取りうる値の集合(1, 2, 3, …, min(N, M, K))が 返り値になっている • i 番目のbitが 1 ならば部分点解法の dp(i, j) が真であることに対応 • min(N, M, K) ≦ 55 より 64 bit符号付き整数の範囲に収まる

39. 満点: (max(Ai, Bj) ≦ 22,222) • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • bit演算を用いて状態遷移を行う • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 の例を示す • はじめ,A から 1 つも移動させないという状態のみが真 ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0000 0000 0000 0000 0001 0000 0000 0000 0000

40. 満点: (max(Ai, Bj) ≦ 22,222) • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • bit演算を用いて状態遷移を行う • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 の例を示す • はじめ,A から 1 つも移動させないという状態のみが真 • 遷移は dp(x) を 1 bit左にシフトしたものとの論理和で表現可能 – dp(x – Ai) = dp(x – Ai) or (dp(x) << 1) で表せる • A0 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0000 0000 0000 0010 0001 0000 0000 0000 0000

41. 満点: (max(Ai, Bj) ≦ 22,222) • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • bit演算を用いて状態遷移を行う • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 の例を示す • はじめ,A から 1 つも移動させないという状態のみが真 • 遷移は dp(x) を 1 bit左にシフトしたものとの論理和で表現可能 – dp(x – Ai) = dp(x – Ai) or (dp(x) << 1) で表せる • A0 を移動させるかどうかで遷移させる • A1 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0000 0000 0100 0010 0001 0000 0000 0000 0000

42. 満点: (max(Ai, Bj) ≦ 22,222) • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • bit演算を用いて状態遷移を行う • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 の例を示す • はじめ,A から 1 つも移動させないという状態のみが真 • 遷移は dp(x) を 1 bit左にシフトしたものとの論理和で表現可能 – dp(x – Ai) = dp(x – Ai) or (dp(x) << 1) で表せる • A0 を移動させるかどうかで遷移させる • A1 を移動させるかどうかで遷移させる • A2 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 1000 0100 0010 0100 0010 0001 0000 0000 0000 0000

43. 満点: (max(Ai, Bj) ≦ 22,222) • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • bit演算を用いて状態遷移を行う • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 の例を示す • はじめ,A から 1 つも移動させないという状態のみが真 • 遷移は dp(x) を 1 bit左にシフトしたものとの論理和で表現可能 – dp(x – Ai) = dp(x – Ai) or (dp(x) << 1) で表せる • A0 を移動させるかどうかで遷移させる • A1 を移動させるかどうかで遷移させる • A2 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 1000 0100 0010 0100 0010 0001 0000 0000 0000 0000

44. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • A の要素を詰め終わったあと, i > min(N, M, K) であ る dp(i, j) を全て偽にする,という操作をbit演算で 表現したい ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 1000 0100 0010 0100 0010 0001 0000 0000 0000 0000

45. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • A の要素を詰め終わったあと, i > min(N, M, K) であ る dp(i, j) を全て偽にする,という操作をbit演算で 表現したい • 下から min( N, M, K ) + 1 個のbitが 1 であるマスクと 論理積をとってやればよい! – この例だと dp(x) = dp(x) and 0111 で表せる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0100 0010 0001 0000 0000 0000 0000

46. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • B の要素を詰める遷移を A のときと同様に行う ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0100 0010 0001 0000 0000 0000 0000

47. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • B の要素を詰める遷移を A のときと同様に行う • 遷移は dp(x) を 1 bit右にシフトしたものとの論理和で表現可能 – dp(x + Bi) = dp(x + Bi) or (dp(x) >> 1) で表せる • B0 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0101 0010 0001 0000 0000 0000 0000

48. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • B の要素を詰める遷移を A のときと同様に行う • 遷移は dp(x) を 1 bit右にシフトしたものとの論理和で表現可能 – dp(x + Bi) = dp(x + Bi) or (dp(x) >> 1) で表せる • B0 を移動させるかどうかで遷移させる • B1 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0111 0011 0011 0001 0000 0000 0000

49. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • B の要素を詰める遷移を A のときと同様に行う • 遷移は dp(x) を 1 bit右にシフトしたものとの論理和で表現可能 – dp(x + Bi) = dp(x + Bi) or (dp(x) >> 1) で表せる • B0 を移動させるかどうかで遷移させる • B1 を移動させるかどうかで遷移させる • B2 を移動させるかどうかで遷移させる ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0111 0011 0011 0001 0011 0001 0001

50. 満点: (max(Ai, Bj) ≦ 22,222) • A = {1, 1, 3}, B = {1, 2, 4}, K = 2 • 全ての遷移を完了した – このとき 最下位bitが 1 ならば,そのような交換が存在する – そのような全ての x について x(C – x) の最大値を調べれば よい • ここで C はΣA + ΣB とする ΣA 0 1 2 3 4 5 6 7 8 9 dp(ΣA) 0000 0100 0010 0111 0011 0011 0001 0011 0001 0001

51. 満点解法まとめ • bool 値を返すようなDPは状態数を削減可能なことが ある • dp(j) = A の要素の総和が j であるような, B から A に 移動させる必要がある個数の集合,とする • 部分点解法のdp(i, j) の i が取りうる値の集合(1, 2, 3, …, min(N, M, K))が 返り値になっている • i 番目のbitが 1 ならば部分点解法の dp(i, j) が真であることに対応 • bit演算を使ってDPを行うことで全ての i について まとめて計算を行うことで高速化が可能 • 計算量は O((N + M)max(ΣA))

Add a comment

Related pages

DDPC 2016 予選 · GitHub

DDPC 2016 予選. Skip to content. All gists; GitHub; Sign up for a GitHub account Sign in. Create a gist now. Instantly share code, notes, and snippets ...
Read more

JOI 2015/2016 予選 問題文・採点用入出力・解説

予選は,2015年12月 ... 文・データ・解説 ... 日本委員会作 『 第 15 回日本情報オリンピック joi 2015/2016 予選 ...
Read more

JOI 2015-2016 予選 問題5 解説

第15回日本情報オリンピック 予選5 ... 解説. この問題の解法は 2 つの段階からなる.1 つ目は危険な町を列挙 ...
Read more

EURO2016予選|海外リーグ|スカパー ...

uefa euro 2016予選。強豪国を中心に毎節5試合を生中継で放送!サッカー中継ならスカパー!日本最大の多チャンネル ...
Read more

DDPC | ディスカバリーチャンネル

昼食(ddpc 特別 ... 2016年度(2017年3月)卒業見込 ... 予選・本戦の最中に、問題に関する言及、解答ソースコードの ...
Read more

2016年F1タイヤ規約詳細解説: フリー走行と ...

・ 2016年の規約も昨年までと同様、チームは週末の間タイヤ ... 予選パート1 ... 2016年f1タイヤ規約詳細解説
Read more

DISCO presents ディスカバリーチャンネル ...

2016-02-08. DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 D - DDPC ...
Read more

アジアカップ2015日程/グループ/決勝 ...

予選 グループa1位: 2 ... 、サッカー、テニス、野球、バスケなどスポーツ別で賭け方・オッズの解説 ... ユーロ2016 ...
Read more