![満点解法(30+70点)
? この性質をみたすような場合に Opt を求める際、二分探索を用いる
ことができます。
? 例えば、区間 [left,right] (left≦right) の内部に Opt がある
(left≦Opt≦right) とわかっている場合に、left≦half≦right となる half
を考え、
X=half が条件を満たす→ Opt は区間 [half,right] 内にある。
X=half が条件を満たさない→ Opt は区間 [left,half) 内にある。
として区間を狭めていくという方針です。
? half は (left+right)/2 辺りの整数を取ることが多いです。](https://image.slidesharecdn.com/abc023-150509140027-lva1-app6891/85/AtCoder-Beginner-Contest-023-24-320.jpg)
More Related Content
What's hot (20)
Similar to AtCoder Beginner Contest 023 解説 (9)
More from AtCoder Inc. (20)
Recently uploaded (8)
AtCoder Beginner Contest 023 解説
- 1. ABC023 解説
- 2. 問題A – 加算王
- 3. 問題概要 ? 2 桁の正整数が与えられる。 ? 各位の和を計算せよ。 ? 10 ≦ 正整数 ? ≦ 99
- 4. 解法 ? 整数を読み込んで、十の位と一の位を求めて、合計値を計算します。 ? 今回 ? は 2 桁なので、以下の性質が成り立ちます。 ? 十の位は ? を 10 で割った商です。 ? 一の位は ? を 10 で割った余りです。
- 5. 問題B – 手芸王
- 6. 問題概要 ? 文字列 ? について、b→abc→cabca→bcabcab→…と変化させる手順 の何番目 (最初の b は 0 番目とおく) に出てくるか (あるいは出てこ ないか) を計算せよ。 ? 1 ≦ ?(= |?|) ≦ 100
- 7. 解法 ? アクセサリーの名前となりうる文字列は abcabcabc… と a,b,c が順繰 りに出てくる文字列でなければなりません。 ? さらに、長さは奇数長で、中央の文字が b とならなければなりません。 ? これらの条件を満たした場合、(?-1)/2 番目の手順の直後に文字列 ? が名前としてでてきます。
- 8. 注意事項 ? 入力には ? = 1, ? = “b” というケースが存在します。このケースの 答えは 0 となります。 ? 実行時間には余裕があるので、実際に問題文の手順にしたがって アクセサリーの名前を探索するプログラムを作成する方針でも正解 することができます (こちらの方が勘違いによるミスが少なくなるか も?)。
- 9. 問題C – 収集王
- 10. 問題概要 ? R 行 C 列のマス目があり、そのうち ? マスには飴が 1 個ずつありま す。 ? 高橋君はあるマスを起点として、同一の行にあるすべての飴と、同 一の列にあるすべての飴を獲得します。 ? ちょうど ? 個の飴を獲得するような起点マスの総数を求めよ。 ? 1 ≦ ? ≦ 100,000 ? 1 ≦ ? ≦ 100,000 ? 1 ≦ ? ≦ ? ≦ 100,000
- 11. 部分点解法 (30点) ? すべてのマスについて、そのマスに高橋君が移動した場合に何個の 飴を獲得するのかを計算します。 ? 全体の計算量はO(?? ? + ? + ?) になります。
- 12. 満点解法 (30+70点) ? 最初に、元の問題と似た別の問題について考えます。 ? 問題：基本設定は一緒。違うのは、高橋君がいるマスに飴があった 場合は、1 個分 (C 問題元の設定) ではなく 2 個分としてカウントしま す。 ? この問題の場合、高橋君がマス (x,y) に移動したなら、高橋君が獲 得する飴の個数が (第 x 行にある飴の総数) + (第 y 列にある飴の総 数) と等しくなります。
- 13. 満点解法 (30+70点) ? 変形した問題を解くために、最初に各行、各列について飴が何個あ るのかを計算します。 O O O O O 行 列 1 2 0 0 2 1 2 2
- 14. 満点解法 (30+70点) ? 変形した問題を解くために、最初に各行、各列について飴が何個あ るのかを計算します。 ? 次に、飴が X 個ある行(列)が Y 個ある、という情報を行ごと、列ごと にまとめます。 O O O O O 行 列 1 2 0 0 2 1 2 2 飴の個数 0 1 2 3 行の個数 0 1 2 0 飴の個数 0 1 2 3 列の個数 2 1 2 0
- 15. 満点解法 (30+70点) ? すると、(行から i 個の飴)×(列から K-i 個の飴) という組み合わせを i=0,1,…,K について計算して合計することで変形した問題を解くことが できます。 O O O O O 行 列 1 2 0 0 2 1 2 2 飴の個数 0 1 2 3 行の個数 0 1 2 0 飴の個数 0 1 2 3 列の個数 2 1 2 0
- 16. 満点解法 (30+70点) ? 最後に元の問題を、先ほど計算した値 (変形した問題の解) から増 減させることで答えを求めていきます。 ? 起点となるマスに飴がない場合は両方の問題において K 個か否か は変化しません。 ? 一方で起点となるマスに飴がある場合はカウントがずれます。 ?そのようなマスで (行の飴の個数) + (列の飴の個数) = K なら、 余計にカウントしていることになります。 ?一方で和が K+1 ならカウントから除外していたことになります。
- 17. 満点解法 (30+70点) ? まとめると、以下の手順になります。 ?変形した問題で、和が K 個となるマス数を求める。 ?起点に飴があり、和が K 個となるマス数だけ引く。 ?起点に飴があり、和が K+1 個となるマス数だけ足す。 ? 計算量は O(? + ? + ?) となります。
- 18. 問題D – 射撃王
- 19. 問題概要 ? 風船が ? 個ある。 ? 風船 ? は最初に高度 ?? にあり、秒速 ?? で上昇する。 ? 1 秒おきに風船を割っていくとき、一番上がった風船の高さ (ペナル ティ) として考えられる最小値はいくらか。 ? 1 ≦ ? ≦ 100,000 ? 1 ≦ ?? ≦ 1,000,000,000 ? 1 ≦ ?? ≦ 1,000,000,000
- 20. 考察 ? 単に高さ順に割る、速度順に割る、ではうまくいきません。 ? 風船を割る順番をうまく決定するアルゴリズムが欲しいです。 ? 実は、この問題は最小化問題としてそのまま考えるのは大変で、最 小化問題の代わりに、ある高さ X 以下を保ちながら風船を割ること ができるか、という判定問題に変形することで効率的にとくことがで きるようになります。
- 21. 部分点解法 (30点) ? 越えてはならない高さ X が定まっているとします。 ? このとき、風船 ? は (? ? ??)/?? 秒以内に割らなければならないとい うことが分かります (もしも ? < ?? なら、この X では不可能であるこ とが分かります)。
- 22. 部分点解法 (30点) ? 各風船をいつまでに割らなければならないかが分かったならば、実 際に割る方法があるかを判定する際、貪欲法を用いることにより判 定することができます。 ? 具体的には、いつまでに割るかの制限時間が短い風船を優先して 割るという貪欲法です。 ? 部分点解法では風船の個数が少なく、X の候補は およそ 200,000 通りしか無いので、部分点を得ることができます。
- 23. 満点解法(30+70点) ? この問題のすべてのテストケースについて考えた場合、風船の高さ として考えられるものがとても多く、すべての X を仮定することができ ません。 ? 実は、ある値 Opt を基準として、 ? Opt > X ならば、どうやっても達成できない。 ? Opt ≦ X ならば、先ほどの貪欲法アルゴリズムで達成できる。 という性質が成り立ちます。 ? この Opt の値が、求める答えとなります。
- 24. 満点解法(30+70点) ? この性質をみたすような場合に Opt を求める際、二分探索を用いる ことができます。 ? 例えば、区間 [left,right] (left≦right) の内部に Opt がある (left≦Opt≦right) とわかっている場合に、left≦half≦right となる half を考え、 X=half が条件を満たす→ Opt は区間 [half,right] 内にある。 X=half が条件を満たさない→ Opt は区間 [left,half) 内にある。 として区間を狭めていくという方針です。 ? half は (left+right)/2 辺りの整数を取ることが多いです。
- 25. 満点解法(30+70点) ? X を定めたときに、制限時間でソートして判定するので、全体で O(?log? ? log(? + ??)) (ただし ?, ? はそれぞれ、開始時高度の最 大値、速度の最大値) となります。 ? この解法ならば満点を得ることができます。
- 26. 備考 ? 制限時間でソートする際、後の判定で制限時間が ? 秒以上である 風船は一律制限時間が ? 秒であるとしても良い (なぜなら、どの風 船も ? ? 1 秒以内に割られるようにできるため) ので、0 以上 ? 以 下の整数値をソートする問題となります。 ? これはビンソートを用いることにより O( ? ) で実現することができます。 ? 計算量は O(?log(? + ??)) になります。