![B問題 問題概要
? 演算子op(+,*)と1桁の数字A,B,Cがある
? A (演算子1) B (演算子2) C
を最大化するように演算子を割り当てる．
ただし演算子の優先順序はなく左から計算
[例] (A,B,C)=(1,2,3)のとき，
「1 → + → 2 → × 3」で答え9となり最大](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-6-320.jpg)
![F問題 解法
? DP[i] = i文字目までの正しい区切り方の個数
? 例 (X=“dkdkdkdk”, S=“dk”, T=“dkdk”)
d k d k d k d k
1 0 1 0 2 0 3 0 5DP:](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-19-320.jpg)
![F問題 解法
? DPの遷移
? if i文字目からの|S|文字が S と一致していたら
DP[i+|S|] += DP[i]
? if i文字目からの|T|文字が T と一致していたら
DP[i+|T|] += DP[i]
? modを取るのを忘れないように！](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-20-320.jpg)
![H問題 問題概要
? 長さ2～20の英単語がNコある
? それらのみを使ってしりとりをする
? 単語を反転して使用することができる
? 一度使った単語は使用不可
? 最初の単語は自由に選べる
? 全部使いきって終了したいが，できない場合があるので，
適当に英単語を追加して全部使いきれるようにしたい
? 追加する必要がある英単語の最小値を答えよ
? 1<=N<=100000
? [例]{ab,cb,xx} : 単語”cx”を追加しab→bc(反転)→cx→xx](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-27-320.jpg)
![H問題 考察(1/4)
? アルファベットを頂点とし，単語を辺(単語の先頭と末
尾のアルファベットを結ぶ辺)としたグラフを考える
? 単語は反転できるという性質から，無向辺になる
? [例]{ab,cb,xx} cxを追加
a
b
x
c
xx
ab
cb
cx](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-28-320.jpg)
![H問題 考察(2/4)
? これらを適当な頂点から始めて，辺を一筆書きできれ
ばOK → 無向オイラー路が存在するかどうか？
? 無向オイラー路：無向グラフですべての辺を
一度ずつ使用する経路 さっきの例→
? 無向オイラー路が存在する
必要十分条件は，
– グラフが連結かつ
– 次数(頂点から伸びてる辺の数)が奇数の点が2コ
– または全てが偶数の点(閉路)
[例]
a
b
x
c
xx
ab
cb
cx
偶 偶
偶
偶 奇
偶
奇
OR
偶 奇
奇
奇
奇](https://image.slidesharecdn.com/thanks2014b-150623063355-lva1-app6892/85/CODE-THANKS-FESTIVAL-2014-B-29-320.jpg)
CODE THANKS FESTIVAL 2014 B日程 解説
- 1. CODE THANKS FESTIVAL 2014 B日程 解説 AtCoder株式会社 代表取締役 高橋 直大 2015/6/23 1
- 2. ?AtCoder Inc. All rights reserved. 2 A問題 朝食 2015/6/23 2
- 3. A問題 問題概要 ? 朝食の準備をする – コーヒーを淹れるのに A 分かかる – トーストを焼くのに B 分かかる ? 同時に準備を始めると、準備が完了するのは何分 後？ 2015/6/23 3
- 4. A問題 解法 ? 準備を同時に始めるので、遅い方の準備が終わっ たときに全体の準備も完了する ? A と B のうち大きい方が答え 2015/6/23 4
- 5. ?AtCoder Inc. All rights reserved. 5 B問題 電卓ゲーム 2015/6/23 5
- 6. B問題 問題概要 ? 演算子op(+,*)と1桁の数字A,B,Cがある ? A (演算子1) B (演算子2) C を最大化するように演算子を割り当てる． ただし演算子の優先順序はなく左から計算 [例] (A,B,C)=(1,2,3)のとき， 「1 → + → 2 → × 3」で答え9となり最大
- 7. B問題 解法 ? 全通り割り当てを試す(4通り) ? その中の最大値を出力 ? 具体的には， Max ( A+B+C， (A+B)×C， A+B×C, A×B×C ) を出力
- 8. ?AtCoder Inc. All rights reserved. 8 C問題 人気投票ゲーム 2015/6/23 8
- 9. C問題 問題概要 ? N 個の地域で人気投票が行われた – i 番目の地域の総投票数は Vi – i 番目の地域の「きつね派」の得票数は Fi ? 「きつね派」が過半数の票を獲得した地域数は？ ? 注意: ちょうど半分の得票は過半数ではない 2015/6/23 9
- 10. C問題 解法 ? Vi が全部入力されてから Fi が入力されるので、 Vi を読み込んだら配列に記憶しておきましょう ? 過半数の判定方法の考え方はいろいろ – 2 倍したら総投票数を超える: 2 × Fi > Vi – 「うさぎ派」の得票数より多く得票: Fi > Vi - Fi – Fi > Vi / 2 では切り捨てに注意 2015/6/23 10
- 11. ?AtCoder Inc. All rights reserved. 11 D問題 足ゲーム 2015/6/23 11
- 12. D問題 問題概要 ? N個のボタンをT秒間決められたタイミングで踏みた い ? ボタンiはAi秒の間隔で踏まなければならない ? 同時に踏むボタンの数と同じ数の足が必要 ? 足は何本必要？
- 13. D問題 解法 ? T秒分の配列をとって0で埋めておき、 Ai,2Ai,3Ai,…の場所に+1していく ? 配列の中の最大の値が答え ? 注意点 ? 要素 T までアクセスするので、 配列のサイズは T では足りません
- 14. ?AtCoder Inc. All rights reserved. 14 E問題 マスゲーム 2015/6/23 14
- 15. E問題 問題概要 ? R×Cの二次元盤面がある ? いくつかの長方形区間を黒く塗りつぶした後， 黒塗りのマスのみを辿ってスタート地点からゴール 地点に辿り着けるかどうかを判定する
- 16. E問題 解法 ? まず愚直に黒塗り操作をシミュレーションする – (一回の操作でO(RC)かかるがO(NRC)で余裕) ? 次に，盤面上を深さ優先探索なり幅優先探索なりを 行い可達判定 ? 座標の扱いに注意(どっちがどっちの軸に対応して いるか等) ? 境界条件に(長方形区間の塗る範囲) ? 配列外参照に注意(探索時)
- 17. ?AtCoder Inc. All rights reserved. 17 F問題 太鼓ゲーム 2015/6/23 17
- 18. F問題 問題概要 ? 画面に文字列 S が表示されていたら太鼓の真ん中 を、文字列 T が表示されていたら太鼓のふちを叩く ゲームがある ? 画面には S と T がいくつか一列に並んで表示されて いるが、間隔が狭すぎてどこで区切られているのか 分からない ? 画面に表示されている長い文字列 X を S または T に区切る方法は何通り？
- 19. F問題 解法 ? DP[i] = i文字目までの正しい区切り方の個数 ? 例 (X=“dkdkdkdk”, S=“dk”, T=“dkdk”) d k d k d k d k 1 0 1 0 2 0 3 0 5DP:
- 20. F問題 解法 ? DPの遷移 ? if i文字目からの|S|文字が S と一致していたら DP[i+|S|] += DP[i] ? if i文字目からの|T|文字が T と一致していたら DP[i+|T|] += DP[i] ? modを取るのを忘れないように！
- 21. ?AtCoder Inc. All rights reserved. 21 G問題 石取りゲーム 2015/6/23 21
- 22. G問題 問題概要 ? 石取りゲームをする – 最初は N 個の石がある – 先手は 1 手目に 1～P 個の石をとれる – それ以降は直前にとられた石の個数 + 1 個までの石を 1 手でとれる ? 先手必勝？後手必勝？ 2015/6/23 22
- 23. G問題 解法(1/3) ? (N, P) で「石が N 個で、最初に P 個までとれる」とい う設定のゲームを表すとする ? (N, P) から先手が k 個の石をとったとき – 残った石は N - k 個 – 次にプレーヤーがとれる石は k + 1 個まで ? (N – k, k + 1) で先手と後手が入れ替わったような ゲームになった！ 2015/6/23 23
- 24. G問題 解法(2/3) ? 問題文に書かれている重要事実 – 「N, P の値が決まればどちらかが必勝」 ? W(N, P) := 「ゲーム (N, P) で必勝なプレーヤー」とし て、これを計算することを考える ? 先ほどの考察より、 W(N, P) は W(N-k, k+1) から計算できそう？ 2015/6/23 24
- 25. G問題 解法(3/3) ? W(N, P) を計算するとき、k (1 ≦ k ≦ P) について ? W(N-k, k+1) = 後手、となるような k があれば W(N, P) = 先手 – 最初に k 個とれば相手には勝つ術がないということ – 1 手進めると先手と後手が逆になっていることに注意する ? そのような k がなければ W(N, P) = 後手 – どのようにとっても相手に必勝法がある 2 人ゲームの必勝判定を探索するときの典型パターン 2015/6/23 25
- 26. ?AtCoder Inc. All rights reserved. 26 H問題 模様替え 2015/6/23 26
- 27. H問題 問題概要 ? 長さ2～20の英単語がNコある ? それらのみを使ってしりとりをする ? 単語を反転して使用することができる ? 一度使った単語は使用不可 ? 最初の単語は自由に選べる ? 全部使いきって終了したいが，できない場合があるので， 適当に英単語を追加して全部使いきれるようにしたい ? 追加する必要がある英単語の最小値を答えよ ? 1<=N<=100000 ? [例]{ab,cb,xx} : 単語”cx”を追加しab→bc(反転)→cx→xx
- 28. H問題 考察(1/4) ? アルファベットを頂点とし，単語を辺(単語の先頭と末 尾のアルファベットを結ぶ辺)としたグラフを考える ? 単語は反転できるという性質から，無向辺になる ? [例]{ab,cb,xx} cxを追加 a b x c xx ab cb cx
- 29. H問題 考察(2/4) ? これらを適当な頂点から始めて，辺を一筆書きできれ ばOK → 無向オイラー路が存在するかどうか？ ? 無向オイラー路：無向グラフですべての辺を 一度ずつ使用する経路 さっきの例→ ? 無向オイラー路が存在する 必要十分条件は， – グラフが連結かつ – 次数(頂点から伸びてる辺の数)が奇数の点が2コ – または全てが偶数の点(閉路) [例] a b x c xx ab cb cx 偶 偶 偶 偶 奇 偶 奇 OR 偶 奇 奇 奇 奇
- 30. H問題 考察&解法(3/4) ? 英単語長は十分大きいのでどんな辺でも追加できる とみなせる(英単語が枯渇しない) ? まずとにかく，全ての連結成分を連結にさせることを 考える(以下，次数が奇数の頂点を奇点?偶数の点を偶点と呼ぶ) ? 奇点を偶点にして損をすることがない (※逆で損をすることはあるかもしれない) ? したがって連結成分の個数が1つになるまで以下の ような戦略を繰り返す – 奇点を持つ2つの連結成分がある→適当な奇点同士をつなぐ – 奇点を持つ連結成分が1つしかない→奇点と，奇点を持たない連結成 分の適当な偶点を結び連結に – 奇点を持たない連結成分しかない→仕方ないので偶点同士を結ぶ
- 31. H問題 考察&解法(4/4) ? 最終的に連結グラフになったあと，そのグラフに辺を 追加してオイラー路の条件を満たすようにしたい – 奇点が2個以下になるまで，奇点同士を貪欲に結んでいけ ばよい (※)奇点が奇数個あることはありえないことに注意 ? 一連の操作で追加した辺の数が答え． ? 次のページに操作例 (※)グラフに1つ辺を追加するとグラフ全体の次数の総和は2増えるはずであり， 総和は必ず偶数．一方，奇数個の奇点が存在すると仮定すると，次数の総和が奇数と なり，矛盾する．したがって奇数個の奇点を持つグラフは存在しない．
- 32. H問題 ? 以下の3つのグラフを連結にする 偶 偶 偶 偶 奇 偶 奇 偶 奇 奇 奇 奇 偶 偶 偶 偶 奇 偶 偶 偶 奇 偶 奇 奇 偶 奇 偶 偶 奇 偶 偶 偶 奇 偶 奇 偶 偶 偶 偶 偶 奇 偶 偶 奇 偶 偶 偶 偶 偶 偶 偶 完成！
- 33. H問題 計算量 ? 辺の入力でO(N) ? 答えを求めるパートについて， 構築されるグラフの頂点数は26以下であることから， どんなやり方をしてもすぐ終わるはず
- 34. ?AtCoder Inc. All rights reserved. 34 おわり！ 2015/6/23 34