狠狠撸

狠狠撸Share a Scribd company logo

AtCoder Beginner Contest 008 解説

?
?
A
AtCoder Inc.

AtCoder Beginner Contest 008 解説

1 of 43
Downloaded 59 times
AtCoder Beginner Contest 008 解説 AtCoder株式会社 ?AtCoder Inc. All rights reserved. 1
?AtCoder Inc. All rights reserved. 2 競技プログラミングを始める前に ?競技プログラミングの基本的なこと(標準入出力など）は過去の ABC の解説にも描 かれてあります。 ?特に ABC004 のものが詳しく書かれてあります。 ?過去問を学ぶことは有益なことですので、積極的に活用しましょう。
?AtCoder Inc. All rights reserved. 3 A問題 アルバム
?AtCoder Inc. All rights reserved. 4 A問題 問題概要 ? 2 つの整数 S,T が与えられます。 ? S 以上 T 以下の整数の個数を計算してください。 ? 1 ≦ S ≦ T ≦ 1,000
?AtCoder Inc. All rights reserved. 5 A問題 入出力 ? 標準入力から 2 つの整数を読み込んで、答えを計 算して、1 つの整数を出力してください。 ? 出力の末尾には改行を入れてください（改行コード の種類に注意すること）。 ? 標準入出力の使い方等に関しては、過去の ABC 解説や練習ページに詳しい説明があります。 ? 練習ページ: http://practice.contest.atcoder.jp/
?AtCoder Inc. All rights reserved. 6 A問題 計算 ? S 以上 T 以下の整数は、S に 1 つずつ数を足して いって、T に等しくなるまでに足した回数に 1 を加 えた値 (S 自身) が答えとなります。 ? 1 つずつ数え上げなくても、T-S+1 という式を計算 することでも求めることができます。
?AtCoder Inc. All rights reserved. 7 A問題 計算の補足 ? 前者のアルゴリズムは O(T-S)、後者のアルゴリズ ムは O(1) ということができます。 ? このような計算量の考え方は、アルゴリズムの設計 において役に立つことがあるので、余裕があれば 是非とも習得してください。 ? 今回の問題ではどちらの方針でも解くことができま す。
?AtCoder Inc. All rights reserved. 8 B問題 投票
?AtCoder Inc. All rights reserved. 9 B問題 問題概要 ? 整数 N と、N 個の名前が与えられます。 ? 最も多く重複して現れる名前を出力してください。 ? 条件を満たす名前が複数ある場合は、そのうちど れでも構いません。 ? 1 ≦ N ≦ 50 ? 1 ≦ (それぞれの名前の長さ) ≦ 50
?AtCoder Inc. All rights reserved. 10 B問題 ステップ ? この問題には 2 つの重要な点があります。 1. ループ処理について 2. 文字列の処理について
?AtCoder Inc. All rights reserved. 11 B問題 ステップ 1 1. ループ処理について ? この問題では入力によって読み込む回数が変わる ので、ループ関数などを用いて読み込みを行うこと になります。 ? 後述する文字列についても、ループ関数が密接に 関わってきます。 ※言語によっては実装の方針などが変わる場合があ ります。その場合はその言語に対応したプログラムを 用いてください。
?AtCoder Inc. All rights reserved. 12 B問題 ステップ 2 2. 文字列の処理について ? 文字列の処理は、言語によって様々な仕様があり ます。 ? 予め文字列の問題を幾つか解いておいて、文字列 をどのように扱えばいいのかを学んでおきましょう。 ? ライブラリ関数 (C だと strcmp とか) を使用すると 実装が容易になることがあります。 ? 原理を知っておくのが望ましいです。
?AtCoder Inc. All rights reserved. 13 B問題 解法 ? まず、N個の文字列を、配列に格納します。 ? 各文字列ごとに、その文字列と完全に一致する他 の文字列の個数を計算し、配列等に格納 ? 要するに、２重ループで計算をする ? １つめのループは、最初に選ぶ文字列 ? ２つ目のループは、その文字列と一致する文 字列がいくつあるか調べるために、各文字列 を参照するもの ↓Javaだとダメ！ ? if(st[i] == st[j]) count[i]++みたいにする
?AtCoder Inc. All rights reserved. 14 B問題 解法 ? 最大の要素が格納された場所を調べ、その場所に 対応する文字列を出力します。 ? 文字の長さの最大値を S とおいたとき、O(SN^2) で 計算することができます。
?AtCoder Inc. All rights reserved. 15 B問題 補足 ? 言語によっては、文字列を比較したつもりでも、実 際は文字列のポインタ同士の比較になってしまう場 合などがあります。注意しましょう。 ? 特にJavaなどの時に注意！ ? 別解として、文字列同士の比較の代わりにハッシュ 関数同士の比較を用いた解法もあります。ただしこ の場合はハッシュの衝突に注意する必要がありま す。 （Hash(“abc”) -> 12648917 みたいな。）
?AtCoder Inc. All rights reserved. 16 B問題 補足 ? 計算量を削減する方法（おまけ 解るひとだけ） ? 適当なデータ構造を使って上手い事計算する！ ? C++のSTLにあるmapや、他の言語の TreeMap, HashMap, Dictionaryなどのデータ 構造を使ってあげると高速に計算可能 ? LL系の言語の連想配列でももちろんＯＫ ? Map[st[i]]++;みたいにカウントした後に、 foreachで値を取り出す、みたいなことをする。
?AtCoder Inc. All rights reserved. 17 C問題 コイン
?AtCoder Inc. All rights reserved. 18 C問題 問題概要 ? N 枚のコインを無作為に一列に並べます。 ? 左端から順に、そのコインよりも右側にある、そのコ インに書かれた数の倍数が書かれたコインをすべ てひっくり返す動作をします。 ? 最終的に表を向いている(偶数回反転した)コインの 枚数の期待値を計算してください。 ? 1 ≦ N ≦ 100
?AtCoder Inc. All rights reserved. 19 C問題 浮動小数点について ? この問題では浮動小数点が出てきます。 ? 文字列同様、浮動小数点の扱いにも慣れておきま しょう。 ? 整数型と浮動小数点型間の移行などの際には注 意してください。
?AtCoder Inc. All rights reserved. 20 C問題 解法その 1 ? N ! 通り全てを試す方法（総当たりによる99点解法 ? 順列の全探索には、幾つか数え方があります。 ? C++, Pythonにおけるnext_permutation ? 配列を予め入れておいて、do-whileで回し てあげると、自動的に順列が取り出せる ? 深さ優先探索などでも簡単にかける。 ? 使った数字を記録しながらN回再帰する
?AtCoder Inc. All rights reserved. 21 C問題 解法その 1 ? N ! 通りのすべての組み合わせを作り、実際に実験 してみようと考えます。 ? N ≦ 8 であれば、計算量が O(N!) でも大丈夫なこ とが多いです（今回も、この方針で 99 点を得ること ができます）。 ? 残り 1 点を得るには N ≦ 100 の制約に対処する 必要があります。
?AtCoder Inc. All rights reserved. 22 C問題 解法その 1 ? もしも、N ! 通りのすべての組み合わせを N=100 に おいて計算しようとなると、それにはとてつもない時 間がかかることになります(2 sec の時間制限は大 幅に超えてしまう)。 ? より高速に動作するアルゴリズムを設計する必要 があります。
?AtCoder Inc. All rights reserved. 23 C問題 数学の時間 ? 期待値の性質を用いることで高速に解くためのア プローチが得られます。 ? 求める期待値は、すべての組み合わせのうちそれ ぞれにおいて表を向いているコインの枚数の総合 計を N! で割ったものとして計算できます。 ? コインの枚数の総合計について考えます。
?AtCoder Inc. All rights reserved. 24 C問題 数学の時間 ? コインの枚数の総合計は、組み合わせごとに区 切って数えても、各コインが全組み合わせのうち何 通りの組み合わせで表を向くのかという数え方で数 えても一致します。よって、それぞれのコインにつ いて、そのコインが、何通りの並べ方で表を向くの かという方針で計算することにします。
?AtCoder Inc. All rights reserved. 25 C問題 数学の時間(補足) ? 補足として、全体を足しあわせてから N! で割った 結果と、それぞれの要素を N! で割ったものの合計 は等しくなります。 ? それぞれのコインごとに、表を向いている組み合わ せ数を N! で割った値は、そのコインが表を向いた 状態で終了する確率に等しくなります。 ? 今回の場合、この確率の足し合わせが期待値にな ります。
?AtCoder Inc. All rights reserved. 26 C問題 解法その 2 ? あるコインについて、このコインに書かれた数を C としたとき、どのような条件を満たせばこのコインが 最終的に表を向いているかを考えます。 ? このコインよりも左側にあるコインに書かれた数の うち、C の約数となっているものの枚数が奇数枚な ら裏、偶数枚なら表となります。
?AtCoder Inc. All rights reserved. 27 C問題 解法その 2 ? 全コインのうち、目標のコインと、それ以外の中で C の約数 となっているコイン(S 枚あるとする)の並びについて考えま す。 約 数 約 数 目 標 約 数 他 他
?AtCoder Inc. All rights reserved. 28 C問題 解法その 2 ? 全コインのうち、目標のコインと、それ以外の中で C の約数 となっているコイン(S 枚あるとする)の並びについて考えま す。 ? C の約数でないコインの並びは関係なく、純粋に目標のコ インより左に何個 C の約数があるかを考えます。 約 数 約 数 目 標 約 数 他 他
?AtCoder Inc. All rights reserved. 29 C問題 解法その 2 ? 目標のコインについて、そのコインが左から何番目にあった としても、C の約数内では S! 通りの並べ方があります。 ? つまり、左から 1 番目、2 番目、… (S+1) 番目のいずれも 当確率で出てくることになります。 ? より左側に偶数枚ということは、左から奇数枚目にある確率 が、目標のコインが表を向いている確率に等しくなります。 約 数 約 数 目 標 約 数 約 数 約 数
?AtCoder Inc. All rights reserved. 30 C問題 解法その 2 ? この確率は、S が奇数なら 1/2 , S が偶数なら (S+2)/(2S+2) の確率になります。 ? それぞれのコインごとに、上記の確率を求め、足し合わせる ことで答えが得られます。 ? 計算量は O(N^2) となり、高速に答えを計算することが出来 ます。
?AtCoder Inc. All rights reserved. 31 D問題 金塊ゲーム
?AtCoder Inc. All rights reserved. 32 D問題 問題概要 ? N 個の装置と W×H 個の金塊についての情報が与 えられます。 ? 最適に装置を動かして、できるだけ多くの金塊を 取ってください。 ? 1 ≦ N ≦ 30 ? 1 ≦ W ≦ 10^6 ? 1 ≦ H ≦ 10^6
?AtCoder Inc. All rights reserved. 33 D問題 解法その 1 ? C 問題同様、N ! 通りのすべての組み合わせをシ ミュレーションする解法があります。 ? 計算量は O(R×C×N!) で、この方針で 80 点を得 ることができます。 (N≦8, 1≦W,H≦80) ? DFSとかで、装置の起動順序を全探索 ? さらに高い点数を得るためにはこの問題について の考察が必要になります。
?AtCoder Inc. All rights reserved. 34 D問題 考察 ? ある装置を稼働させた後の状態を考える。 M
?AtCoder Inc. All rights reserved. 35 D問題 考察 ? ある装置を稼働させた後の状態を考える。 ? 下図のように、1 つの長方形領域が最大 4 つの長方形領 域に分かれる。 M
?AtCoder Inc. All rights reserved. 36 D問題 考察 ? ある装置を稼働させた後の状態を考える。 ? 下図のように、1 つの長方形領域が最大 4 つの長方形領 域に分かれる。 ? これらの領域同士は互いに干渉しないので、独立に最適解 を求めて、それらの合計を用いれば元の解が求まる。 M
?AtCoder Inc. All rights reserved. 37 D問題 考察 ? このように、ある大きさにおける最適解を求める際 に、より小さい部分の最適解を求めてその値を用 いて元の最適解を求める手法一般を動的計画法と 言います。 ? この問題では動的計画法を用いて効率的に解くこ とができます。
?AtCoder Inc. All rights reserved. 38 D問題 解法その 2 ? dp[i][j][k][l]=(左下を(i,j), 右上を(k,l) とした長方形領 域が残った際の最適解) ? とおくことにより、O(W^2×H^2) の空間計算量、各 dp で O(N) 通りの選択と適用により計算できるの で、全体で O(N×W^2×H^2) となります。(99点)
?AtCoder Inc. All rights reserved. 39 D問題 考察 ? こんな感じ！ M M M M M M M M M これらの 最大値をとることによって、 最適解が得られる！ (I,j) (k,l) M
?AtCoder Inc. All rights reserved. 40 D問題 補足 ? 動的計画法を実行する際には、今回の場合、長方 形の面積が小さい順から行います。 ? また、今回の場合、参照される長方形のうち最初 のもの以外のすべてはある装置がつくる 2 辺を用 いるので、実際は状態数は少ないです。
?AtCoder Inc. All rights reserved. 41 D問題 解法その 3 ? W と H が大きい場合は、これまでの方法では状態 が多すぎて間に合いません。 ? しかしながら、直線が連続する区間とかは圧縮して 計算できそうです。 コンパクトにまとめる
?AtCoder Inc. All rights reserved. 42 D問題 補足 ? テクニック 座標圧縮！ ? 例えば、いくつかの点があります。 ? (x ,y) -> (13, 25), (7, 3), (11, 38) (4, 50) ? xの値 -> 13, 7, 11, 4 -> 4, 7, 11, 13 ? この4,7,11,13を、0,1,2,3に変換！ ? (x, y) -> (3, 1), (1, 0), (2, 2), (0, 3) ? 整数の最大値が小さくなった！大小関係 は変わらず！
?AtCoder Inc. All rights reserved. 43 D問題 補足 ? 今回の問題では、 →動的計画法: 座標圧縮で節約 →メモ化探索: 余計な状態を生成しない という方針で対策することができます。 ? この方針であれば 100 点を得ることが出来ます。 ? メモリ制限には注意してください！

More Related Content

AtCoder Beginner Contest 008 解説

  • 1. AtCoder Beginner Contest 008 解説 AtCoder株式会社 ?AtCoder Inc. All rights reserved. 1
  • 2. ?AtCoder Inc. All rights reserved. 2 競技プログラミングを始める前に ?競技プログラミングの基本的なこと(標準入出力など）は過去の ABC の解説にも描 かれてあります。 ?特に ABC004 のものが詳しく書かれてあります。 ?過去問を学ぶことは有益なことですので、積極的に活用しましょう。
  • 3. ?AtCoder Inc. All rights reserved. 3 A問題 アルバム
  • 4. ?AtCoder Inc. All rights reserved. 4 A問題 問題概要 ? 2 つの整数 S,T が与えられます。 ? S 以上 T 以下の整数の個数を計算してください。 ? 1 ≦ S ≦ T ≦ 1,000
  • 5. ?AtCoder Inc. All rights reserved. 5 A問題 入出力 ? 標準入力から 2 つの整数を読み込んで、答えを計 算して、1 つの整数を出力してください。 ? 出力の末尾には改行を入れてください（改行コード の種類に注意すること）。 ? 標準入出力の使い方等に関しては、過去の ABC 解説や練習ページに詳しい説明があります。 ? 練習ページ: http://practice.contest.atcoder.jp/
  • 6. ?AtCoder Inc. All rights reserved. 6 A問題 計算 ? S 以上 T 以下の整数は、S に 1 つずつ数を足して いって、T に等しくなるまでに足した回数に 1 を加 えた値 (S 自身) が答えとなります。 ? 1 つずつ数え上げなくても、T-S+1 という式を計算 することでも求めることができます。
  • 7. ?AtCoder Inc. All rights reserved. 7 A問題 計算の補足 ? 前者のアルゴリズムは O(T-S)、後者のアルゴリズ ムは O(1) ということができます。 ? このような計算量の考え方は、アルゴリズムの設計 において役に立つことがあるので、余裕があれば 是非とも習得してください。 ? 今回の問題ではどちらの方針でも解くことができま す。
  • 8. ?AtCoder Inc. All rights reserved. 8 B問題 投票
  • 9. ?AtCoder Inc. All rights reserved. 9 B問題 問題概要 ? 整数 N と、N 個の名前が与えられます。 ? 最も多く重複して現れる名前を出力してください。 ? 条件を満たす名前が複数ある場合は、そのうちど れでも構いません。 ? 1 ≦ N ≦ 50 ? 1 ≦ (それぞれの名前の長さ) ≦ 50
  • 10. ?AtCoder Inc. All rights reserved. 10 B問題 ステップ ? この問題には 2 つの重要な点があります。 1. ループ処理について 2. 文字列の処理について
  • 11. ?AtCoder Inc. All rights reserved. 11 B問題 ステップ 1 1. ループ処理について ? この問題では入力によって読み込む回数が変わる ので、ループ関数などを用いて読み込みを行うこと になります。 ? 後述する文字列についても、ループ関数が密接に 関わってきます。 ※言語によっては実装の方針などが変わる場合があ ります。その場合はその言語に対応したプログラムを 用いてください。
  • 12. ?AtCoder Inc. All rights reserved. 12 B問題 ステップ 2 2. 文字列の処理について ? 文字列の処理は、言語によって様々な仕様があり ます。 ? 予め文字列の問題を幾つか解いておいて、文字列 をどのように扱えばいいのかを学んでおきましょう。 ? ライブラリ関数 (C だと strcmp とか) を使用すると 実装が容易になることがあります。 ? 原理を知っておくのが望ましいです。
  • 13. ?AtCoder Inc. All rights reserved. 13 B問題 解法 ? まず、N個の文字列を、配列に格納します。 ? 各文字列ごとに、その文字列と完全に一致する他 の文字列の個数を計算し、配列等に格納 ? 要するに、２重ループで計算をする ? １つめのループは、最初に選ぶ文字列 ? ２つ目のループは、その文字列と一致する文 字列がいくつあるか調べるために、各文字列 を参照するもの ↓Javaだとダメ！ ? if(st[i] == st[j]) count[i]++みたいにする
  • 14. ?AtCoder Inc. All rights reserved. 14 B問題 解法 ? 最大の要素が格納された場所を調べ、その場所に 対応する文字列を出力します。 ? 文字の長さの最大値を S とおいたとき、O(SN^2) で 計算することができます。
  • 15. ?AtCoder Inc. All rights reserved. 15 B問題 補足 ? 言語によっては、文字列を比較したつもりでも、実 際は文字列のポインタ同士の比較になってしまう場 合などがあります。注意しましょう。 ? 特にJavaなどの時に注意！ ? 別解として、文字列同士の比較の代わりにハッシュ 関数同士の比較を用いた解法もあります。ただしこ の場合はハッシュの衝突に注意する必要がありま す。 （Hash(“abc”) -> 12648917 みたいな。）
  • 16. ?AtCoder Inc. All rights reserved. 16 B問題 補足 ? 計算量を削減する方法（おまけ 解るひとだけ） ? 適当なデータ構造を使って上手い事計算する！ ? C++のSTLにあるmapや、他の言語の TreeMap, HashMap, Dictionaryなどのデータ 構造を使ってあげると高速に計算可能 ? LL系の言語の連想配列でももちろんＯＫ ? Map[st[i]]++;みたいにカウントした後に、 foreachで値を取り出す、みたいなことをする。
  • 17. ?AtCoder Inc. All rights reserved. 17 C問題 コイン
  • 18. ?AtCoder Inc. All rights reserved. 18 C問題 問題概要 ? N 枚のコインを無作為に一列に並べます。 ? 左端から順に、そのコインよりも右側にある、そのコ インに書かれた数の倍数が書かれたコインをすべ てひっくり返す動作をします。 ? 最終的に表を向いている(偶数回反転した)コインの 枚数の期待値を計算してください。 ? 1 ≦ N ≦ 100
  • 19. ?AtCoder Inc. All rights reserved. 19 C問題 浮動小数点について ? この問題では浮動小数点が出てきます。 ? 文字列同様、浮動小数点の扱いにも慣れておきま しょう。 ? 整数型と浮動小数点型間の移行などの際には注 意してください。
  • 20. ?AtCoder Inc. All rights reserved. 20 C問題 解法その 1 ? N ! 通り全てを試す方法（総当たりによる99点解法 ? 順列の全探索には、幾つか数え方があります。 ? C++, Pythonにおけるnext_permutation ? 配列を予め入れておいて、do-whileで回し てあげると、自動的に順列が取り出せる ? 深さ優先探索などでも簡単にかける。 ? 使った数字を記録しながらN回再帰する
  • 21. ?AtCoder Inc. All rights reserved. 21 C問題 解法その 1 ? N ! 通りのすべての組み合わせを作り、実際に実験 してみようと考えます。 ? N ≦ 8 であれば、計算量が O(N!) でも大丈夫なこ とが多いです（今回も、この方針で 99 点を得ること ができます）。 ? 残り 1 点を得るには N ≦ 100 の制約に対処する 必要があります。
  • 22. ?AtCoder Inc. All rights reserved. 22 C問題 解法その 1 ? もしも、N ! 通りのすべての組み合わせを N=100 に おいて計算しようとなると、それにはとてつもない時 間がかかることになります(2 sec の時間制限は大 幅に超えてしまう)。 ? より高速に動作するアルゴリズムを設計する必要 があります。
  • 23. ?AtCoder Inc. All rights reserved. 23 C問題 数学の時間 ? 期待値の性質を用いることで高速に解くためのア プローチが得られます。 ? 求める期待値は、すべての組み合わせのうちそれ ぞれにおいて表を向いているコインの枚数の総合 計を N! で割ったものとして計算できます。 ? コインの枚数の総合計について考えます。
  • 24. ?AtCoder Inc. All rights reserved. 24 C問題 数学の時間 ? コインの枚数の総合計は、組み合わせごとに区 切って数えても、各コインが全組み合わせのうち何 通りの組み合わせで表を向くのかという数え方で数 えても一致します。よって、それぞれのコインにつ いて、そのコインが、何通りの並べ方で表を向くの かという方針で計算することにします。
  • 25. ?AtCoder Inc. All rights reserved. 25 C問題 数学の時間(補足) ? 補足として、全体を足しあわせてから N! で割った 結果と、それぞれの要素を N! で割ったものの合計 は等しくなります。 ? それぞれのコインごとに、表を向いている組み合わ せ数を N! で割った値は、そのコインが表を向いた 状態で終了する確率に等しくなります。 ? 今回の場合、この確率の足し合わせが期待値にな ります。
  • 26. ?AtCoder Inc. All rights reserved. 26 C問題 解法その 2 ? あるコインについて、このコインに書かれた数を C としたとき、どのような条件を満たせばこのコインが 最終的に表を向いているかを考えます。 ? このコインよりも左側にあるコインに書かれた数の うち、C の約数となっているものの枚数が奇数枚な ら裏、偶数枚なら表となります。
  • 27. ?AtCoder Inc. All rights reserved. 27 C問題 解法その 2 ? 全コインのうち、目標のコインと、それ以外の中で C の約数 となっているコイン(S 枚あるとする)の並びについて考えま す。 約 数 約 数 目 標 約 数 他 他
  • 28. ?AtCoder Inc. All rights reserved. 28 C問題 解法その 2 ? 全コインのうち、目標のコインと、それ以外の中で C の約数 となっているコイン(S 枚あるとする)の並びについて考えま す。 ? C の約数でないコインの並びは関係なく、純粋に目標のコ インより左に何個 C の約数があるかを考えます。 約 数 約 数 目 標 約 数 他 他
  • 29. ?AtCoder Inc. All rights reserved. 29 C問題 解法その 2 ? 目標のコインについて、そのコインが左から何番目にあった としても、C の約数内では S! 通りの並べ方があります。 ? つまり、左から 1 番目、2 番目、… (S+1) 番目のいずれも 当確率で出てくることになります。 ? より左側に偶数枚ということは、左から奇数枚目にある確率 が、目標のコインが表を向いている確率に等しくなります。 約 数 約 数 目 標 約 数 約 数 約 数
  • 30. ?AtCoder Inc. All rights reserved. 30 C問題 解法その 2 ? この確率は、S が奇数なら 1/2 , S が偶数なら (S+2)/(2S+2) の確率になります。 ? それぞれのコインごとに、上記の確率を求め、足し合わせる ことで答えが得られます。 ? 計算量は O(N^2) となり、高速に答えを計算することが出来 ます。
  • 31. ?AtCoder Inc. All rights reserved. 31 D問題 金塊ゲーム
  • 32. ?AtCoder Inc. All rights reserved. 32 D問題 問題概要 ? N 個の装置と W×H 個の金塊についての情報が与 えられます。 ? 最適に装置を動かして、できるだけ多くの金塊を 取ってください。 ? 1 ≦ N ≦ 30 ? 1 ≦ W ≦ 10^6 ? 1 ≦ H ≦ 10^6
  • 33. ?AtCoder Inc. All rights reserved. 33 D問題 解法その 1 ? C 問題同様、N ! 通りのすべての組み合わせをシ ミュレーションする解法があります。 ? 計算量は O(R×C×N!) で、この方針で 80 点を得 ることができます。 (N≦8, 1≦W,H≦80) ? DFSとかで、装置の起動順序を全探索 ? さらに高い点数を得るためにはこの問題について の考察が必要になります。
  • 34. ?AtCoder Inc. All rights reserved. 34 D問題 考察 ? ある装置を稼働させた後の状態を考える。 M
  • 35. ?AtCoder Inc. All rights reserved. 35 D問題 考察 ? ある装置を稼働させた後の状態を考える。 ? 下図のように、1 つの長方形領域が最大 4 つの長方形領 域に分かれる。 M
  • 36. ?AtCoder Inc. All rights reserved. 36 D問題 考察 ? ある装置を稼働させた後の状態を考える。 ? 下図のように、1 つの長方形領域が最大 4 つの長方形領 域に分かれる。 ? これらの領域同士は互いに干渉しないので、独立に最適解 を求めて、それらの合計を用いれば元の解が求まる。 M
  • 37. ?AtCoder Inc. All rights reserved. 37 D問題 考察 ? このように、ある大きさにおける最適解を求める際 に、より小さい部分の最適解を求めてその値を用 いて元の最適解を求める手法一般を動的計画法と 言います。 ? この問題では動的計画法を用いて効率的に解くこ とができます。
  • 38. ?AtCoder Inc. All rights reserved. 38 D問題 解法その 2 ? dp[i][j][k][l]=(左下を(i,j), 右上を(k,l) とした長方形領 域が残った際の最適解) ? とおくことにより、O(W^2×H^2) の空間計算量、各 dp で O(N) 通りの選択と適用により計算できるの で、全体で O(N×W^2×H^2) となります。(99点)
  • 39. ?AtCoder Inc. All rights reserved. 39 D問題 考察 ? こんな感じ！ M M M M M M M M M これらの 最大値をとることによって、 最適解が得られる！ (I,j) (k,l) M
  • 40. ?AtCoder Inc. All rights reserved. 40 D問題 補足 ? 動的計画法を実行する際には、今回の場合、長方 形の面積が小さい順から行います。 ? また、今回の場合、参照される長方形のうち最初 のもの以外のすべてはある装置がつくる 2 辺を用 いるので、実際は状態数は少ないです。
  • 41. ?AtCoder Inc. All rights reserved. 41 D問題 解法その 3 ? W と H が大きい場合は、これまでの方法では状態 が多すぎて間に合いません。 ? しかしながら、直線が連続する区間とかは圧縮して 計算できそうです。 コンパクトにまとめる
  • 42. ?AtCoder Inc. All rights reserved. 42 D問題 補足 ? テクニック 座標圧縮！ ? 例えば、いくつかの点があります。 ? (x ,y) -> (13, 25), (7, 3), (11, 38) (4, 50) ? xの値 -> 13, 7, 11, 4 -> 4, 7, 11, 13 ? この4,7,11,13を、0,1,2,3に変換！ ? (x, y) -> (3, 1), (1, 0), (2, 2), (0, 3) ? 整数の最大値が小さくなった！大小関係 は変わらず！
  • 43. ?AtCoder Inc. All rights reserved. 43 D問題 補足 ? 今回の問題では、 →動的計画法: 座標圧縮で節約 →メモ化探索: 余計な状態を生成しない という方針で対策することができます。 ? この方針であれば 100 点を得ることが出来ます。 ? メモリ制限には注意してください！