Hatena::Grouptopcoder

agwの日記 RSSフィード

|

2014-03-10SRM 611 Div II

SRM 611 Div II

07:05 |  SRM 611 Div II - agwの日記 を含むブックマーク はてなブックマーク -  SRM 611 Div II - agwの日記  SRM 611 Div II - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15844

SRM 611 Div Iに参加。戦績は惨憺たるものだった。

SRM終了後に@nico_shindanninさんのTopCoderでプログラムしてみた 第2060回(SRM611 直後放送)を視聴。そこで解説されていた素因数、最小公倍数(LCM)の解説があまりにも明瞭で素晴らしかったため、氏の許可を得てブログにまとめることにした。

さて、Div I 250とDiv II 500は類似した問題であった。Div I 250はDiv II 500の知見を利用すると効率よく解くことができる。そのため、このエントリでは生放送での解説から得られる知見を解説し、Div II 500を解くことを目標とする。

LCMSetEasy

http://community.topcoder.com/stat?c=problem_statement&pm=13040&rd=15844

  • 問題は上記のURLから参照して欲しい
    • 要約すれば、自然数xと自然数の集合Sが与えられる。そのとき、最小公倍数がxとなる集合Sの部分集合が存在するかしないかを答える問題
  • 問題について考える前にまず、約数、最大公約数、最小公倍数について考察してみよう

  • 最大公約数(GCD)や最小公倍数(LCM)を考えるときにまず与えられた数の素因数を考えるのは自然なことだ。与えられた自然数xが600であったとすると、素因数分解したものは以下となる

f:id:agw:20140309140820p:image

  • 生放送で氏はこれを以下のように図示した

f:id:agw:20140309140819p:image

  • 続いて24という数字も考えてみよう。24を素因数分解すると以下となる

f:id:agw:20140309140821p:image

  • これは以下のように図示することができる

f:id:agw:20140309140822p:image

  • さて、この数字は600を割り切る。氏の手法を用いた場合、このように図示することができる

f:id:agw:20140309140823p:image

  • ものすごく分かりやすい...次に70という数字を考えてみよう

f:id:agw:20140309140824p:image

  • 70は600を割り切らない。これは以下のように図示することができる。7がはみ出るのだ

f:id:agw:20140309140826p:image

  • 以下は18を考えた例だ。18も600を割り切らないので、はみ出る

f:id:agw:20140309140827p:image

  • 逆にいえば、はみ出る要素がなければその値は約数であると言えるし、はみ出てしまうのであれば約数ではないと言えることができる

  • 次に最大公約数を考えてみよう。計算機を使って最大公約数を求める場合はユークリッドの互除法を用いるのが一般的だが、氏の手法でも考えてみよう
  • 24と15の最大公約数を考えてみよう。これははそれぞれ、以下のように図示することができる

f:id:agw:20140309140831p:image

  • 最大公約数を考えるには重なった部分のみ抽出すればよい。論理積を取る感覚だ

f:id:agw:20140309140832p:image

  • もう一例挙げておこう。24と900の最大公約数は12だ

f:id:agw:20140309140834p:image

  • 同様に、複数の数値の最大公約数も論理積を取る感覚で考えることができる
    • 15、24、900の最大公約数は3だ

f:id:agw:20140309140835p:image

  • この図を眺めていると、複数の数値の最大公約数は以下のように考えることができることが分かる

f:id:agw:20140309140836p:image

  • また、式を以下のように変形していくと、端から数値を処理すればよいということが分かる
    • これも図からも直感的に得ることができる

f:id:agw:20140309140837p:image

  • さて、最小公倍数も同じように図示することが出来る。先ほどとは違い、論理和を取る感覚だ

f:id:agw:20140309140839p:image

  • 最小公倍数を算出する以下の式と見比べてみると楽しい

f:id:agw:20140309140840p:image

  • 複数の数値の最小公倍数も論理和を取る感覚で考えることができる
    • 例えば、24、105、900の最小公倍数は1800だ

f:id:agw:20140309140841p:image

  • 最大公約数で考えたときと同様に、複数の数値の最小公倍数は以下のように考えることが出来る

f:id:agw:20140309140842p:image

  • 式変形を行うと、最小公倍数に関しても端から数値を処理すればよいということが分かる

f:id:agw:20140309140843p:image


  • ここまでの知識をもとに、SRMの問題を解いてみよう。ある整数xと整数の集合Sが与えられるのであった。例として、xを600、集合Sの数値をS = {8, 12, 15, 18, 105, 300}とする

f:id:agw:20140309140858p:image

  • 集合Sの部分集合の最小公倍数が数値xとなるか判定するにはどうすればよいだろうか?
    • 一先ず、全ての数のLCMを取ってみよう

f:id:agw:20140309140904p:image

  • ...なんとなく600に近い形にはなっているように見えるが、3が一つ、また7がはみ出してしまっている
  • はみ出してしまうのは約数ではないからであった。なので、これらの値は除外してしまってよい。これは、値が整数xを割り切るかどうかで判断できる
  • この例の場合、18、105は除外してしまってよい

f:id:agw:20140309140902p:image

  • 改めて、はみ出さなかった数のみ、つまり約数のみの最小公倍数を考えてみよう

f:id:agw:20140309140855p:image

  • 最小公倍数の数は600となった!
  • そのため、以下の部分集合は最小公倍数がxとなるものの一つであると言える

f:id:agw:20140309150749p:image

  • 最小公倍数が600とならない場合も考えてみよう。先ほどの集合から300を抜いた場合を考えてみる

f:id:agw:20140309140906p:image

  • 先ほどと同様にはみ出す、つまり約数ではない数を除外して、最小公倍数を求めよう。その値は300となり、600には足りないことが分かる

f:id:agw:20140309140907p:image

これを実装すると以下のようになる(システムテストをパスした実装)。

class LCMSetEasy {
public:
  std::string include(std::vector<int> S, int x) {
    long long lcm = 1;

    for (const auto& i : S)
      if (x % i == 0)
        lcm = lcm * i / std::__gcd<long long>(lcm, i);

    return lcm == x ? "Possible" : "Impossible";
  };
};

まとめ

  • @nico_shindaninnさんの生放送での解説を元に約数、最大公約数、最小公倍数の図示を行い、特に複数の値の最大公約数と最小公倍数について考察した
  • この図示手法は大変簡潔で分かりやすい。最大公約数や最小公倍数を考える際、有用なアプローチの一つに成りえる
  • 氏は解説の文書化を快諾くださった。筆者の力量不足であまりよい文章に落とし込むことが出来なかったが、感謝したい

おまけ

@kojingharangさんが大変有用なつぶやきをされていたので抜粋させていただく。

kroton1992kroton19922014/03/10 09:31gcd lcmは指数で考えるとなんかよさ気ですよね。

指数で考えるとlcmはmax, gcdはminですから
a = 2^a2 * 3^a3 * ...
b = 2^b2 * 3^b3 * ...
とおけば
gcd(a,b) = 2^min(a2, b2) * 3^min(a3, b3) * ...
lcm(a,b) = 2^max(a2, b2) * 3^max(a3, b3) * ...
gcd * lcm = 2^(min(a2, b2) + max(a2, b2)) * ...
みたいになってmin(a,b) + max(a,b) = a + bですから
gcd * lcm = 2^(a2 + b2) * 3^(a3 + b3) * ... = a * b
みたいなのも簡単に示せるし、他にもいろいろと知見ありそう。

agwagw2014/03/10 09:48をー、分かりやすい。どうもありがとうございます!

2014-01-14Codeforces # 223 Div. 2

Codeforces # 223 Div. 2

15:10 |  Codeforces # 223 Div. 2 - agwの日記 を含むブックマーク はてなブックマーク -  Codeforces # 223 Div. 2 - agwの日記  Codeforces # 223 Div. 2 - agwの日記 のブックマークコメント

http://codeforces.com/contest/381

Codeforces # 223 Div. 2に参加。ABCが通り、2,492点。94位。部屋(Room 74)でも初めて1位となり、嬉しい回であった。レートは1,621から1,720へ。紫コーダーになった。

今回のエントリではstd::lower_boundおよびstd::upper_boundメソッドを考察するため、C. Seraja and Prefixesのみ記載することにする。

C. Seraja and Prefixes

12:49 |  C. Seraja and Prefixes - agwの日記 を含むブックマーク はてなブックマーク -  C. Seraja and Prefixes - agwの日記  C. Seraja and Prefixes - agwの日記 のブックマークコメント

http://codeforces.com/contest/381/problem/C

  • 与えられたステージの情報から数列を構築し、クエリに答える問題
    • 入力例は以下だ
6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  • ステージの型が1である場合、続く数値を数列に足す
  • ステージの型が2である場合、数列の先頭から続く数値分の長さを切り出し、追加する。さらに続く数値は、追加する回数だ
  • さて、この入力例を処理した結果、数列の要素数は16となる。最後にその全ての要素のクエリを行っている
    • そのため、出力結果は以下となる
1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4
  • 効率よく考察するため、作図した

f:id:agw:20140113210048p:image

  • 白いセルはタイプが1のステージによって追加された要素を表す。同様に灰色のセルはタイプが2のステージによって追加された要素を表している
  • こう見ると、タイプが2のステージは区間であることが分かる
  • さて、この数列に対してクエリを行う
  • クエリの対象が白いセルであれば、要素をそのまま返せばよいことが分かる。例えば以下は、5に対するクエリだ。これは3を返す

f:id:agw:20140113210050p:image

  • クエリの対象が灰色のセルであれば、その要素が参照している元の要素を再帰的にクエリすればよい。例えば、4に対するクエリは以下のようになる。これは2を返す

f:id:agw:20140113210049p:image

  • 7に対するクエリは以下のようになる

f:id:agw:20140113210051p:image

  • 13に対するクエリは以下のようになる。再帰的にクエリをする様子がよく分かる

f:id:agw:20140113210052p:image

  • ここまで考えた結果、タイプが2のステージの情報は「区間のまま」管理するとメモリ効率が良さそうなことが分かってくる

  • さて、再帰するクエリは再帰関数で実装したい。だが、過剰な回数の再帰を引き起こさないだろうか?
  • 再帰の回数が多くなるパターンを少し考えてみよう

f:id:agw:20140113210053p:image

  • 16に対するクエリは以下のようになる。灰色のセルは数列の先頭からの要素のコピーであるため、再帰の回数がそれほど多くなるような感じはしない...

f:id:agw:20140113210054p:image


  • 実装を考えてみよう
  • ステージの数は高々105であるため、全てのステージのタイプが1であった場合でも高々105分の数値を扱えればよい
    • これはあまり問題にならない
  • 問題はタイプが2のステージだ。部分数列の追加は複数回できるため、最終的な数列の要素数はとても大きなものとなるはずだ
    • 単純に数列を構築したらTLEかMLEとなりそうだ。やはり「区間のまま」管理したほうがバランスを維持出来そうに思える
    • また、オーバーフローを防ぐためにクエリの位置や区間の始まる位置をlong longで管理し実装時に細心の注意を払うことにした

  • さて、効率的にクエリを行うために、タイプによって異なるデータ構造を用意することにした
    • タイプが1のステージ
      • 数値が納まる位置と数値自身
    • タイプが2のステージ
      • 区間が始まる位置と幅

  • もう一度記載するが、全てのステージのタイプが1であった場合、数値の数は高々105
    • さほど多くないので、データ構造にはstd::mapを用いることにした
  • ではタイプが2のステージはどうだろう?
    • こちらもタイプが1のステージと同様の考え方を適用できるので、区間の数は高々105であると言える
    • また、区間は重ならない
  • そのため、区間が始まる位置を一次元配列で管理することにした。こうすればクエリの位置を含む区間を二分探索で効率的に探索することができそうだ
  • さらに区間の長さを保持しておけば、クエリの位置と区間の始まる位置から、参照しているセルの位置が算出できる

  • 区間の開始位置の探索方法を具体的に考えてみよう
    • 以下の例で考えてみる(再掲)

f:id:agw:20140113210053p:image

  • 区間の開始位置は2、3、5、9となる

f:id:agw:20140113210055p:image

  • 実際の一次元配列は上記のようなものだ。だが、二分探索を考察するために以下のような作図を行おう

f:id:agw:20140113210056p:image

  • 各セルに対して区間の番号を追加するとさらによい

f:id:agw:20140113210057p:image

  • さて、例えば7の位置に対する問い合わせを行った場合は、2を返したい

f:id:agw:20140113210058p:image

  • 別の言葉で言い表すと、「左閉半開区間の二分探索」とでもいうのだろうか
  • このようなデータ構造において区間(左閉半開区間だ)の二分探索を行う場合、与えられた位置を用いて、以下のように求めることが出来る(配列をa、配列の大きさをsize、与えられた位置をxとしている)
  int n = std::upper_bound(a, a + size, x) - a - 1;
  • ここまでを元に実装を行って、提出。無事システムテストをパスした

  • 区間の二分探索を実装をするとき、いつもstd::lower_boundかstd::upper_boundを用いるか考えてしまう
  • 常々「慣れてなくて危険だなぁ」と考えていた。いい機会なので少し考察する
    • 今回の考察を終えても完全に理解することはできなかったので、先に記載しておく

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

lower_bound - C++ Reference

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

upper_bound - C++ Reference
  • これがさっぱり理解できない
    • 英語が難解だ(compareという単語には苦手意識がある)

・lower_bound()

lower_bound()は、指定した値"以上"の要素が最初に現れる位置を返します。 この位置は、現在のソート済みの状態を崩すことなく、指定した値を挿入できる最初の位置になります。

エラー - Yahoo!ジオシティーズ

・upper_bound()

upper_bound()は、lower_bound()とよく似ています。upper_bound()の場合には、 指定した値より"大きい"の要素が最初に現れる位置を返します。つまり「以上」と「大きい」の違いです。 これは言い換えると、ソート状態を崩さずに値を挿入できる最後の位置を返すということになります。

エラー - Yahoo!ジオシティーズ
  • これらはstd::lower_bound、std::upper_boundを適用した結果をとてもよく言い表している
  • 日本語での説明と英語での説明が随分違うが、以下のように言い表すことができる

  • std::lower_boundは与えられた値以上の値で一番小さいものを返す
  • std::upper_boundは与えられた値より大きい値で一番小さいものを返す

  • なるほど...
  • これらの説明をより理解するために、以下のような実装を行い、実験してみた
  std::vector<int> a = {2, 3, 5, 9};

  std::cout << std::lower_bound(ALL(a), 5) - a.begin() << std::endl;
  std::cout << std::lower_bound(ALL(a), 7) - a.begin() << std::endl;
  std::cout << std::lower_bound(ALL(a), 9) - a.begin() << std::endl;

  std::cout << std::upper_bound(ALL(a), 5) - a.begin() << std::endl;
  std::cout << std::upper_bound(ALL(a), 7) - a.begin() << std::endl;
  std::cout << std::upper_bound(ALL(a), 9) - a.begin() << std::endl;
  • 結果は以下のようになった
2
3
3
3
3
4
  • なるほど、確かに...
    • じっくり考えるためにそれぞれを視覚化した
  • 以下は5に対するstd::lower_boundの結果

f:id:agw:20140113210101p:image

  • 以下は7に対するstd::lower_boundの結果

f:id:agw:20140113210102p:image

  • 以下は9に対するstd::lower_boundの結果

f:id:agw:20140113210103p:image

  • 以下は5に対するstd::upper_boundの結果

f:id:agw:20140113210104p:image

  • 以下は7に対するstd::upper_boundの結果

f:id:agw:20140113210105p:image

  • 以下は9に対するstd::upper_boundの結果

f:id:agw:20140113210106p:image


  • あー
  • 少しすっきりしてきた
  • std::lower_boundとstd::upper_boundは、与えられた値が存在しない場合同じ結果となる
    • これも実装実験を行い、作図した。以下はstd::lower_boundの動作例

f:id:agw:20140113210059p:image

  • 以下はstd::upper_boundの動作例

f:id:agw:20140113210100p:image


  • なるほど、以下のように言い表すこともできそうだ
  • 与えられた数値が存在する場合、
    • std::lower_boundはその要素の位置を返す
    • std::upper_boundはその次の要素の位置を返す
  • また与えられた数値が存在しない場合、std::lower_boundとstd::upper_boundは同じ結果となる

  • これまで考察したことを応用して、区間を右閉半開区間として扱うことを考えてみる
    • 右閉半開区間が二分探索と親和性が高いことは以前考察した。興味があったら参照して欲しい
    • 以下の例で考えてみる(再掲)

f:id:agw:20140113210053p:image

  • 左閉半開区間で区間を処理していた際は区間の開始位置を記録していたが、右閉半開区間を処理するために区間の終了位置を記録することにする

f:id:agw:20140113232343p:image

  • このデータ構造でstd::lower_boundを用いると、うまく行きそうだ
  • 以下は5に対するstd::lower_boundの結果

f:id:agw:20140113231631p:image

  • 以下は7に対するstd::lower_boundの結果

f:id:agw:20140113231632p:image

  • 以下は8に対するstd::lower_boundの結果

f:id:agw:20140113231633p:image

  • 以下は9に対するstd::lower_boundの結果

f:id:agw:20140113231634p:image

  • 右閉半開区間を用いれば、std::lower_boundを用いて以下のように二分探索できる(配列をa、配列の大きさをsize、与えられた位置をxとしている)
  int n = std::lower_bound(a, a + size, x) - a;
  • 探索の全体の様子は以下だ
    • かなりすっきりしている

f:id:agw:20140114103010p:image

  • 終了位置を記録するとデバグのときに混乱しそうではあるが、実装がすっきりしたものとなる可能性がある
    • 例えば、確率密度関数から累積分布関数を構築し、逆関数法を適用する際に応用できる。(0, 1]の範囲で値が単純増加する配列を用意し、std::lower_boundでクエリすれば効率が良い(区間の終了値を保存するのがポイント)
  • またこの問題のように区間の開始位置の情報を用いる場合には使えない(区間の開始位置を使って、次のクエリ位置を算出している)。注意が必要だ

追記

  • 上位コーダーの方々から基調なご意見をいただいたので、引用させていただきます
    • @kinabaさん、@kroton1992さん、どうもありがとうございます

  • std::lower_bound、std::upper_boundの本来の用法はstd::equal_rangeを考える分かりやすいか
    • 値が格納されている範囲を左閉半開区間で見つける
    • 配列に値が存在しないときに意味が分からなくなるのが玉にきず
      • 区間としては空なのだが、位置のことを考えると混乱を招きやすいように思う

  • いつか作図したい応用用例

まとめ

  • 今回のエントリでは、std::lower_boundとstd::upper_boundの動作を考察し、まとめた
  • std::lower_boundとstd::upper_boundを用いる際はここで考察したことを意識して扱うようにしてみたいと思う

おまけ

  • 以下は提出した実装を整理したものだ(システムテストをパスする)
long long l[111111], r[111111];

int q = 0;

std::map<long long, int> map;


int query(long long x)
{
  if (map.count(x))
    return map[x];

  int t = std::upper_bound(r, r + q, x) - r - 1;

  long long o = (x - r[t]) % l[t] + 1;

  return query(o);
}

int main(int argc, char** argv)
{
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);

  int m, n;
  
  std::cin >> m;

  long long p = 1;
  
  for (int i = 0; i < m; i ++) {
    int x, y;

    std::cin >> x;

    if (x == 1) {
      std::cin >> x;

      map[p ++] = x;
    }
    else {
      std::cin >> x >> y;

      l[q] = x;
      r[q] = p;
      
      p += x * y;

      q ++;
    }
  }

  std::cin >> n;

  for (int i = 0; i < n; i ++) {
    long long x;

    std::cin >> x;

    std::cout << query(x) << ' ';
  }
  
  std::cout << std::endl;

  return 0;
}

2013-12-01How To Defeat the Opponent

How To Defeat the Opponent

22:09 |  How To Defeat the Opponent - agwの日記 を含むブックマーク はてなブックマーク -  How To Defeat the Opponent - agwの日記  How To Defeat the Opponent - agwの日記 のブックマークコメント

  • 競技プログラミングのコンテストではゲームを模した様々な問題が出題される
  • 問題の解法は様々だ
    • シミュレーションによる解法
    • 探索による解法
    • グラフの問題に還元する解法
  • コンテスト終了後によく話題になる、確率DP、期待値DPなども解を探索する問題であることが多い
  • このエントリでは特に解を探索する解法について、ゲームを題材とした初歩的な問題を紹介する
  • ゲームを題材とした問題で頻出される「お互いが最善を尽くす」ということについて少し掘り下げて考えるとともに、探索の計算量を減らす方法を紹介する
  • 対象はTopCoderのDiv II中堅〜上位を想像していただければよいと思われる

TheNumberGameDivTwo

  • この問題はSRM 575 Div IIのMedium問題として出題された
    • 同じ問題がDiv IのEasy問題としても出題されたが、その制約の大きさから解法は探索ではなく規則性を利用したものとなっている
  • ゲームのルールは以下だ
    • ある数値がある。これをnとする(n ∈ [1, 1000])
    • プレイヤーは2人(JohnとBrus)
    • プレイヤーは交互に数値の変更を試みる
    • 新しい数値は「nからnの約数を引いた値」とする。ただし、1とnを使ってはいけない
    • 数値を変更できなかったプレイヤーは負ける
  • また、プレイヤー2人がお互い最善を尽くすことを前提としていることを注意すべき点として挙げておこう(原文では"Assume that both players use the optimal strategy while playing the game."としている)
  • ゲームを進行した例は以下のようなものだ
  • nを15とする
  • Johnは15から約数の3を選んで引く。数値は12となる
  • Brusは12から約数の4を選んで引く。数値は8となる
  • Johnは8から約数の2を選んで引く。数値は6となる
  • Brusは6から約数の3を選んで引く。数値は3となる
  • 3の約数は1と3であるが、ルールによりこの値は引けない。そのため、Johnの負けと判定される

  • さて、コンテスト中は限られた時間で問題を把握し、解法の方針を立て、実装、テストを行わなければならない
  • ノートなどに問題のポイントや制約を記載する方は多いのではないだろうか
  • その際、nに小さな(もしくは全体像を把握するのに都合がよい)値を選んで木やグラフなどをノートに書き出すといった手法を取る人は多いと思う
  • 作図をしてこの問題の特徴を考えてみよう

f:id:agw:20131201024636p:image

  • 問題文に記載されており、明らかである特徴を図に盛り込んだ
  • プレイヤーは2人。交互にプレーする
    • 木を描く際に先手(John)の手盤を円型の頂点で、また後手(Brus)の手盤を四角の頂点で示した

  • また、図にすることによって問題文にはっきりと書いていない特徴にも気付くだろう
  • 例えば次の手が同じ手になることはないことに気付く
    • 期待値DPなどは解法の導出途中に同一の状態が無限に続くような探索木を考えなければいけない場合がある。何らかの変形が必要となるが、この問題ではこれを考慮に入れる必要がないということが分かる
  • 他にも木は入力の数値の値が与える印象より大きくなりそうなこと、木は似通った部分木で構成されているようであることなどが挙げられるだろう

  • 先に挙げた例は以下のような経路を取る
    • このように問題文そのものに正解までの道筋の例が記載されているものもある

f:id:agw:20131202001528p:image


  • さて、このように全体図を描くとゲームの流れを初めから追って行きたくなるが、それはあまり得策ではない
  • この規模の木でも、人間が正確に状態を追うことは難しいのだ
    • 実際にルールに従って15の頂点から追い、勝負の行方を考えてみるのもよいだろう(n = 15のゲームは必ず先手の負けとなるゲームである)

  • 人間がゲーム木を正確に追うことを困難にさせている原因はいくつかある。このように2人のプレイヤーが交互に進めるゲームの場合、手盤によって求める答えや利益が入れ替わるのも一因となるだろう(意味合いが交互に反転しているだけにも関わらずこの有様である)

  • 例を挙げよう。以下の進行では最善が尽くされていない(先手がゲームに勝っていることにも注意)。これは何故かすぐ答えられるであろうか?
    • 後手は6の頂点で3の頂点に進むべきであるところを4の頂点に進んでしまっている。これは最善ではない

f:id:agw:20131203145400p:image

  • もう一つ例を挙げよう。以下の進行でも最善が尽くされていない
    • 最善が尽くされていない理由を説明できるだろうか?(情けないことに筆者には説明できない)

f:id:agw:20131203145401p:image

  • 探すのみならず、結果が最善を尽くされていないことを判断するだけでも困難なことが分かる

  • さて、計算機に効率よく勝敗を判定させるにはどうすればよいだろうか
  • 答えは簡単だ。それぞれの頂点(局面)で最善手を選べばよいのだ
  • 15の頂点は先手(John)の手盤を表している。先手は12の頂点を選ぶべきだろうか、それとも10の頂点を選ぶべきであろうか? 選ぶべき頂点をどのように予想したらよいであろうか?
  • 実際に予想することはとても難しい。また、探索すべき頂点数は深さによって指数的に増えるので全探索するのは不可能だ
    • nが大きくなるにつれ木は大きくなる。その大きくなる様は想像以上に急だ。例えばn = 18の木は以下となる(視認できないため数値を省略する - 18の頂点は16、15、12、9を頂点とする木を含むことに注意しよう)

f:id:agw:20131201012549p:image


  • ナイーブな方法では解けなさそうなことは分かった
    • しかしこれは競技プログラミングの問題だ
  • 競技プログラミングで出題される問題の最大の特徴は出題者によって注意深くルールや制約、取りうる状態の総量が設計されていることが挙げられる。そのため、計算方法を工夫することによって解くことが可能となるような問題も多い
  • この問題の場合も、計算方法を工夫することによって全ての状態を探索することが可能となる
  • 全ての状態を知ることが出来るのであれば、最善手を予想するといったアプローチを取る必要はない。全ての出しうる手を計算させてしまってから最善手を選べばよいのだ。

  • では先ほどの疑問に戻って考えてみよう
    • 15の頂点は先手(John)の手盤を表す。先手は12の頂点を選ぶべきだろうか、それとも10の頂点を選ぶべきであろうか?
  • どちらの頂点が先手にとって有利か分からなければ選びようがない
  • ならば、頂点12を根とする部分木と頂点10を根とする部分木を同様の、また別の小さな問題として解いてしまえばよい
  • そして、どちらの頂点が先手にとって有利か明らかになった後で選べば間違いがない

f:id:agw:20131201025925p:image

  • 12の頂点を選ぶと自分が勝つのであればそれを選べばよいし、10の頂点を選んでも勝てるのであればもちろんそれを選んで構わない
    • 部分木からなるゲームの結果はもう計算させてしまっているので、迷いもためらいもなく選ぶことができる
  • また、何れの頂点を選んでも自分が勝つことがないのであれば、その局面でどんな手を施しても相手が勝つと断言できる

  • では12の頂点を根とする部分木はどう考えればよいだろう?
    • 先ほど15の頂点を考えたときと同じ問題であるが、問題の規模(この場合は数値)が小さくなっていることに注意しよう
  • 問題の根本的な難しさは15の頂点を根とする場合と変わらない。ゲームの展開を予想するのは本当に難しい
  • ではどうすればよいか?
  • 答えは明瞭だ。先ほどと同様、小さな部分木に分割しそれぞれ計算させ、結果が出てから改めて自分に有利な手を判断すればよいのだ

f:id:agw:20131201025926p:image

  • さて、これを繰り返すと末端の少しの頂点からなる部分問題とすることができる
  • 頂点が一つからなる木を考えてもあまり意味がない(すぐに負けてしまうのは明らかだ)ので、頂点数が最低でも2つの木を考えてみる
  • 4の頂点を根とする部分木はそのような小さな部分木である
    • 観察すると2種類あることが分かる
    • 先手から始めているか、後手から始めているか
    • ここでは同様に処理をすることにする

f:id:agw:20131201032016p:image

  • これらの部分木の勝負の行方を考えてみよう。先手が勝つ部分木は薄い灰色で、後手が勝つ部分木は濃い灰色で塗り分けてやる

f:id:agw:20131201024724p:image

  • この結果を使って、6を頂点とする部分木の勝負の行方を考えてみよう
    • 6の頂点の勝敗はその子供の4か3の頂点からなる部分木の結果から得ることが出来る
    • 一番左の部分木で考える。この部分木の根、つまり6の頂点が先手番であることに注意すると、
      • 4を頂点とする後手からの部分木では先手が負ける
      • 3を頂点とする後手からの部分木では後手の選択肢がない。先手が勝つ
  • ことが言えるので、先手は3を頂点とする部分木の勝負の結果を迷わず採用するべきである
  • これを反映すると、以下となる。

f:id:agw:20131201024725p:image

  • これを繰り返していく。12を根とする部分木と10を根とする部分木は以下のように調べることが出来た

f:id:agw:20131201024726p:image

  • では改めて12の頂点を根とする部分木を考えよう
    • 根は後手番であるので、後手が勝つ頂点9もしくは8を選べばよい
    • とても簡単
  • 全ての部分木の試行を行い、自分の利益を最大化する手を選ぶ
    • 特にこの問題では部分木の結果が自分にとって有利な結果である場合、すぐに探索を打ち切ることができる
    • 「最善を尽くしている」ということは、「勝てる手があるのであれば、迷わずその手を選ぶ」ということであるため、探索を続行する必要がないと考えてもよい
  • 12の頂点を根とする部分木問題の結果は15の頂点、つまり先手に対して不利な手であることが分かったため、これを選ぶことはできない
  • 同様に15の頂点の右側に位置する10の頂点を根とする部分木問題でも後手が勝っている。そのため15の頂点で先手が勝てることはないのだ
  • 結果、n = 15の場合は後手が勝つのであった

f:id:agw:20131201024812p:image


  • さて、以上が「勝てる手を予想する」のではなく「手を次から次へと試す手法」の解説であった
  • ここからは計算量とメモリ使用量を落とす方法を考えてみよう
  • 前述したが、この探索木は数値が大きくなるにつれ指数的に大きいものとなっていく
  • 以下はn = 18のときの木の規模を図にしたものだ(再掲)

f:id:agw:20131201012549p:image


  • この計算量を落とすのに、「メモ化再帰」「動的計画法(DPテーブル)」という技法を使おう
    • DPに関しては本年のCompetitive Programming Advent Calendar Div2013にて@nico_shindanninさんが「動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる」として寄稿してくださる予定である(12/8予定)。是非合わせてお読みいただきたい

  • さて、n = 15の木をもう一度眺めてみよう(再掲)

f:id:agw:20131201024636p:image

  • 同じ数値の頂点が頻出していることが分かる
  • 同様に、同じような部分木も頻出している
  • 厳密には先手が始める部分木か後手が始める部分木かで結果が違う(反転する)が、同じような計算として括り出してみよう(彩色の意味合いが先ほどと異なることに注意)

f:id:agw:20131201012707p:image

  • 例えば、8の頂点を根とする部分木は3箇所ある
  • これらの計算結果は同じものとなるはずだ
  • そのため、計算した結果を記録しておき、後で使うことで重複した(無駄な)計算を省略することができるはずだ

f:id:agw:20131201012726p:image

  • 計算方法を省略するこの方法はメモ化などと呼ばれている
    • この図は(深さ、数値)のペアを鍵として結果を記録している
    • 正確な木の深さは計算をしてみないと分からないのだけれども、与えられたnがずっと2で割れる数値に変換されると無理矢理仮定したとして、高々500程度だろう
  • 深さが500ほど。また、数値は1,000種類あるので、500,000個ほどの数値が記録できればこの問題は十分に解ける
  • また、数値nの約数の数は高々n/2であることも容易に想像ができる
    • n = 1,000の場合でも500個の約数を試せばよい
    • そのため計算量も500,000 × 500 = 250,000,000
    • 十分間に合う

  • この問題ではもう少し工夫が出来る
  • (深さ、数値)ではなく、(先手番か後手番か、数値)のペアを鍵として結果を記録してみよう
  • 木で表すと以下のようになる

f:id:agw:20131201012728p:image

  • 先ほどの図と比べると、さらに計算すべき頂点の量が減っていることが分かる
  • 先手番か後手番かは2種類。また、数値は1,000ほどであるので、2,000個ほどの数値が記録できれば十分となった
    • 先ほどと同様に計算量を見積もると、2,000 × 500 = 1,000,000

  • さらに掘り下げて考えてみる
  • 先手番の次は必ず後手番であることを考えると、さらに計算量を減らせることが分かる
  • 先手番の手として計算しなければいけない頂点に重複がないことに気付いたであろうか
    • 同じことが後手番にもいえる
  • これを利用してみよう

  • まずさきほどの探索木の垂直方向の配置を変えてみよう

f:id:agw:20131201012730p:image

  • 計算する必要がない要素を省き、揃えてみよう

f:id:agw:20131201012731p:image

  • 随分シンプルな図となってきたが、今ひとつ一貫性がない
  • 水平方向の並びを、数値の大きさで整列してみよう

f:id:agw:20131201012732p:image

  • これも今ひとつ
  • では、水平方向の頂点の位置を数値の大きさと比例するようにしてみよう

f:id:agw:20131201012733p:image

  • 先手と後手の数値の対応が明確になったと共に対象性も見えてきた

  • さてここで、特にプレイヤーが2人のゲームに顕著に表れる特性を利用しよう
  • 先手がある数値nからゲームを始めて勝ったとしよう。後手がその数値nからゲームを始めると当然後手が勝つ
    • つまり、対象性があるのだ
  • 先ほどの図からいくつかの要素を取ると、よりはっきりと対象性が見えてくる

f:id:agw:20131201041538p:image

  • 図から先手番、後手番という概念をなくすと以下のようになる

f:id:agw:20131201012645p:image

  • (先手番か後手番か、数値)ではなく、ただ単に数字を鍵として結果を記録することが出来るようになってしまった
    • これは一次元のDP配列を用いた動的計画法、などと呼ばれる
  • メモリ使用量は数値の数だけ、つまり1,000個ほどで済むようになった
    • 計算量は1,000 × 500 = 500,000
  • メモリ使用量、計算量が減ったとともに、図としてもすっきりしたものとなった
  • ここまで読んでいただいてどうもありがとうございました

まとめ

  • (恐らく)赤コーダー、黄コーダーは問題を読み終えた段階で最後の図が頭に浮かんで来ているのではないかと考える
    • そのため、上位コーダーはこの問題を5〜7分程度で提出する

  • さてゲームを題材とした問題は頻出するが、それぞれ独特の癖があるので苦手意識を持っている人は多いと思う
  • しかし、解法にはある一定のパターンもあるようだし、コツを掴むことによってAC率が上がるのは間違いない
  • コンテスト終了後のTL、ブログエントリ、オンサイトコンテスト、練習会、オフ会、Advent Calendar等々、競技プログラミングのスキルを上げるイベントは盛りだくさんだ。効率のよい練習法を探し出して、スキルアップを目指そう

Competitive Programming Advent Calendar 2013について


2013-10-23SRM 594 Div I (1)

SRM 594 Div I

17:50 |  SRM 594 Div I - agwの日記 を含むブックマーク はてなブックマーク -  SRM 594 Div I - agwの日記  SRM 594 Div I - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15706

前回に引き続き250にはまりにはまり、45分で再提出。Room 17。レートは1308から1341へ。

今回のエントリではSRM後に復習として考察した550のみを記載することにする。

Problem Status Points
250AstronomicalRecordsPassed System Test 87.28
550FoxAndGo3 Opened 0.00
1000FoxAndAvatar Unopened 0.00
  • 250に32分
    • はまりにはまった
    • 提出後、オーバーフローすることが発覚。45分で再提出
    • システムテストをパス。87.28点
    • 方針は合っているので非常にもったいない(2回連続)
  • 550を復習
    • 二部グラフによる解法を理解した後にイメージトレーニングを行った

FoxAndGo3

http://community.topcoder.com/stat?c=problem_statement&pm=12808&rd=15706

  • 一つは最小カットを使った解法
  • 自分には最小カットによる解法は難しく、手が出せていない

  • さて、もう一つの解法は二部グラフの最大安定集合を使った解法だ
  • このエントリではいつもと趣向を変え、@torus711さんのエントリに掲載されている実装を理解した後に行ったイメージトレーニングの過程を記すことにする

  • エントリを読んだ
    • 何やら二部グラフの最大マッチングを利用するらしい
    • しかしグラフの用語に乏しく、さっぱり分からなかった
    • (最大)安定集合とはなんだ...
  • そのため、まずグラフの用語を記したエントリの拡充を試みた
  • をを、なるほど
    • 最大安定集合とは以下のようなものなのか...

f:id:agw:20131018213450p:image

  • 要するに、お互いに隣接しない頂点の集合が安定集合
    • その頂点数が最大である集合を最大安定集合と呼ぶらしい
  • 蟻本によれば、二部グラフの最大安定集合の頂点数は最大マッチングのペア数から求めることができるようだ
  • なるほど
  • だが、この問題でどう最大安定集合に落とし込むかさっぱり分からん
  • (2、3時間ごにょごにょする)
  • なるほど...
  • 理解したぞ...

同時に起こりえない事象同士を接続したグラフの安定集合は同時に起こりえる事象の集合である、ということか…

  • これはとても正しい(はずだ)
  • 正しいはずなのだが、実際にこの問題に適用する方法を思い浮かべる度に迷いが生じる
  • きっとイメトレが足りないのだ
  • よし、もっと考察しておこう
  • まず以下のような盤の状態を考えてみよう(サンプル #0)
    • この状態での空マスの数は4

f:id:agw:20131023000549p:image

  • 空マスには黒玉を置くことができる
  • 白玉は黒玉で挟むと取り除くことができる
    • この状態での空マスの数は3
    • 初期状態より少し成績が悪くなってしまった

f:id:agw:20131023000550p:image

  • 黒玉を置き、白玉を消し、空マスの数を最大化する問題
    • とても難しい
  • そしてこの盤の大きさだと、自分にはすでに大き過ぎる...
  • 問題を簡単にしてみよう

f:id:agw:20131023000551p:image

  • ををを
  • いいぞ
  • 右上は元々空マスである
    • この空マスで得点することを事象1とする

f:id:agw:20131023000552p:image

  • 同様に、左下の元々の空マスで得点することを事象2とする

f:id:agw:20131023000553p:image

  • さて、残る得点方法は黒玉を置き、左上の白玉を取ることだ。これを事象Aとする
    • 事象Aは「左上のマスから白玉を取り除くことによってできる空マスによって得点を得る」事象であることを軽く意識する
    • 違う言い方をすれば、事象Aを「右上と左下に黒玉を置く」事象等とは考えないことがコツだ

f:id:agw:20131023000554p:image

  • 黒玉が事象1と2に被っている
    • つまり、事象Aで得点をする場合は、事象1、2で得点することはできないということだ
  • ここで、事象1、2、Aを頂点としてグラフを作る。このとき、同時に起こりえない事象を表す頂点同士を接続する
    • これを事象グラフと名付ける

f:id:agw:20131023000555p:image

  • この事象グラフの最大安定集合は以下だ。つまり、頂点1、2からなる集合だ

f:id:agw:20131023000556p:image

  • では3x3の盤に戻って考えてみよう。元々の空マスで得点を取る事象を1、2、3、4とする

f:id:agw:20131023000557p:image

  • 白玉を取り除くことで空マスを得る事象をA、B、C、D、Eとする

f:id:agw:20131023000641p:image

  • これを事象グラフに落とし込む
    • 事象Aが起きたときには事象1、2は起こりえない。そのため、頂点Aと頂点1、2を繋ぐ
    • これを繰り返す...

f:id:agw:20131023000655p:image

  • この事象グラフの最大安定集合は以下となる

f:id:agw:20131023000656p:image

  • つまり、全ての空マスに黒玉を置いて全ての白玉を取り除くのが最適解となる、ということだ
  • 図やグラフを注意深くみると、事象1、2、3、4はお互いに独立していることが分かる。そのため、頂点1、2、3、4の間には辺が張られることがない。事象A、B、C、D、Eに関しても同様であるので、このグラフは二部グラフであると言える
  • 事象グラフの頂点を配置し直してみよう

f:id:agw:20131023000657p:image

  • 最大安定集合は以下だ

f:id:agw:20131023000658p:image

  • では実際に最大安定集合の頂点数を得るにはどうしたらよいだろうか?
  • グラフの性質を利用してやればよい
    • 以下は蟻本からの抜粋だ

a. 孤立点のないグラフに対し、|最大マッチング|+|最小辺カバー|=|V|

b. |最大安定集合|+|最小点カバー|=|V|

c. |最大マッチング|=|最小点カバー|

プログラミングコンテストチャレンジブック 第2版
  • bとcより、

|最大安定集合|+|最大マッチング|=|V|

  • そのため、最大安定集合の頂点数は以下のように求めることができる

|最大安定集合|=|V|-|最大マッチング|

  • また、事象グラフは二部グラフだ。二部グラフでは最大マッチングが比較的簡単に得られることも利用できる
  • 以下は最大マッチングを行った結果の一例だ

f:id:agw:20131023000659p:image

  • 最大マッチングのペア数は4である。頂点数9からこれを引くと5。つまり、最大安定集合の数は5であると言える
  • すごい
  • すっきりし始めた

  • もう一度実際の実装を見る。巧妙でクレバーな実装だ
  • まず無条件に頂点を2n2個割り当ててみよう
    • 起こりえない事象を赤く描画している

f:id:agw:20131023000700p:image

  • この場合の頂点数はもちろん2n2

f:id:agw:20131023000706p:image

  • よく観察すると、各マスで起こる事象は最大でも1種類であることが分かる。これを利用して事象をまとめてみよう

f:id:agw:20131023000701p:image

  • 頂点数はn2で収まってしまった

f:id:agw:20131023000703p:image

  • 二部グラフとその最大マッチングは以下のようになる

f:id:agw:20131023000702p:image

  • では、元々黒玉が配置されている場合を見てみよう

f:id:agw:20131023000704p:image

  • この場合2は無効な頂点であるが、どの頂点とも接続しない頂点として残してやるのがポイントだ
    • この場合の二部グラフと最大マッチングを図示すると以下となる

f:id:agw:20131023000705p:image

  • ただし、この場合は孤立点があるため、先の関係をそのまま用いることが出来ない
  • しかし、二部グラフの最大マッチングで孤立点がマッチングとして判定されることはない
  • そのため以下が成り立つ。実装ではこれを巧みに利用している

|V| - |孤立点| - |最大マッチング| = |最大安定集合|

  • すっきり理解した

まとめ

  • 同時に起こりえない事象同士を接続したグラフの安定集合は同時に起こりえる事象の集合である
    • 新しい知見を得られたように思う

  • またいつものように、TLではたくさんのヒントやアドバイスをいただいた
    • 皆様、本当にどうもありがとうございます
  • いつか最小カットでの解法を理解したときのためにタイトルを「SRM 594 Div I (1)」とした
    • SRM 594 Div I (2)」を記載できる日はいつ頃来るんだろうか...

2013-10-11SRM 593 Div I

SRM 593 Div I

05:56 |  SRM 593 Div I - agwの日記 を含むブックマーク はてなブックマーク -  SRM 593 Div I - agwの日記  SRM 593 Div I - agwの日記 のブックマークコメント

http://community.topcoder.com/stat?c=round_overview&er=5&rd=15705

250にはまりにはまり、55分。Room 41。レートは1231から1308へ。

今回のエントリでは、SRM後に復習として考察した450のみを記載することにする。

Problem Status Points
250HexagonalBoard Passed System Test102.09
450MayTheBestPetWin Opened 0.00
1000WolfDelaymasterHardUnopened 0.00
  • 250に55分
    • はまりにはまった
    • 最近、深さ優先探索をすっきり書き上げることができないことが多い
    • 方針は合っているので、もったいない
  • 450を復習

MayTheBestPetWin

http://community.topcoder.com/stat?c=problem_statement&pm=12779&rd=15705

苦手なDPであるようなので、復習、考察を行った。

  • 以下の式変形を行う

f:id:agw:20131008222746p:image

  • Σi∈UAiとΣi∈UBiは定数と考えることが出来るので、DPを用いてΣi∈S(Ai + Bi)が取りうる値を調べる
  • 調べた値で以下を計算し、一番小さいものが求める答えとなる

f:id:agw:20131008183856p:image

  • すごい
    • 式変形を行うことで0-1ナップサックを解く問題になってしまった

以下は式変形を伴ったDPでの実装(システムテストを通る)。

bool dp[1111111];


class MayTheBestPetWin {
public:
  int calc(std::vector<int> A, std::vector<int> B) {
    int AA = std::accumulate(ALL(A), 0);
    int BB = std::accumulate(ALL(B), 0);

    int size = A.size();

    memset(dp, 0, sizeof(dp));
    
    dp[0] = true;

    for (int i = 0; i < size; i ++) {
      int s = A[i] + B[i];

      for (int j = 1e+6; j >= 0; j --)
        if (j - s >= 0)
          if (dp[j - s])
            dp[j] = true;
    }

    int dm = INF;

    for (int i = 0; i <= 1e+6; i ++)
      if (dp[i])
        dm = std::min(std::max(std::abs(i - AA), std::abs(i - BB)), dm);

    return dm;
  };

  • さて、ここからはdr.kenさんの解法をコードリーディングし、考察を行う
    • 氏にはツィッターでの質問に答えていただいたり、またブログを記載することを快諾いただいた
    • @drken1215さん、どうもありがとうございます

以下は@drken1215さんの解法。

bool dp[1100000], tdp[1100000];
 
class MayTheBestPetWin {
public:
    int calc(vector <int> A, vector <int> B) {
        memset(dp, 0, sizeof(dp));
        
        int SMax = 0, SMin = 0;
        for (int i = 0; i < A.size(); ++i) {
            SMax += max(A[i], B[i]);
            SMin += min(A[i], B[i]);
        }
        
        dp[550000] = 1;
        for (int i = 0; i < A.size(); ++i) {
            memset(tdp, 0, sizeof(tdp));
            for (int j = 0; j < 1100000; ++j) {
                //if (dp[j]) cout << i << ", " << j-550000 << endl;
                
                if (!dp[j]) continue;
                int lo = min(A[i], B[i]), up = max(A[i], B[i]);
                if (j + up < 1100000) tdp[j+up] = true;
                if (j - lo >= 0) tdp[j-lo] = true;
            }
            for (int j = 0; j < 1100000; ++j) {
                dp[j] = tdp[j];
            }
        }
         
        int res = 0;
        for (res = 550000; res < 1100000; ++res) {
            if (dp[res] && SMax-SMin <= (res-550000)*2) break;
        }
        
        return res - 550000;
    }
};
  • 何やらDPっぽいことは分かる
    • だが、先に挙げた式変形を経たDPとは本質的に違う気がした
  • 明確な理由はないが今の自分が理解すべき重要な実装に思えたので、コードリーディングと考察を行った

  • 前処理を前半、DPによる処理を中盤、値を探索しているらしい部分を後半と呼ぼう
  • 前半はAiとBiの合計を取っている
    • std::minとstd::maxを取っているが、制約から必要がない。これは実装時のノリのようなものだろう
    • この値は後半まで使われない

f:id:agw:20131011140019p:image

  • 全体の集合をUとしていることに注意
    • SはUの部分集合であり、Tをその補集合として定義している

f:id:agw:20131011114702p:image

  • では中盤を読み進める
    • 550,000分シフトさせてDPを行っているようだ
    • つまり、大体[-550,000, 550,000]までの範囲の値を扱っていると考えられる
    • また、tdpは値の一時置き場として使っているようだ。毎反復の最後でdpを更新している
  • では内側の反復を見てみよう
  • さっぱり理解できない
  • と言ってても始まらないので、読み進める
  • 前回までに訪れたことがある値から、lo、up分ずれた値に訪れているようだ
    • loとupの算出にstd::minとstd::maxを用いているが、制約から必要がない。これも実装時のノリのようなものだろう
  • つまり、以下のようなグラフの探索を行っていると言える(ブラウザによっては縮小されて表示されています。オリジナルの解像度のものを見るには、画像をクリックしてください)

f:id:agw:20131008183919p:image

  • んー
  • つまりは以下の取りうる値を全て調べているのか

f:id:agw:20131011120750p:image

  • 取りうる値の集合をXとすると以下のような感じ

f:id:agw:20131008183903p:image

  • やっぱりさっぱり分からん
  • 分からないものは分からないので、一先ず最後まで流し読みしてしまおう。最後は以下の条件を満たす値を探しているようだ

f:id:agw:20131008184026p:image

  • なんだこれは
  • 何故割り算が出てくるのだろう...?
  • さっぱり分からん
  • ここまでをつぶやきながら、@drken1215さんにお話を伺ったりしたのだけれども、よく分からなかった...(エントリ最後に掲載)
  • (半日ほど試行錯誤する)
  • あー、分かった
  • 伺った内容とは違うような気がするが、すっきり理解できた
  • では、自分の理解を記載しよう

  • 以下が求めるmaxdiff(S, T)の定義だ(再掲)

f:id:agw:20131008183856p:image

  • この式はとても扱い辛い
  • 絶対値が邪魔をしているんだ
  • ならば、絶対値を取ってしまえばいいじゃないか

f:id:agw:20131011172009p:image

  • また、制約から以下は明らかだ

f:id:agw:20131008183858p:image

  • これは直感から分かるんだけれども、ちゃんと証明しておこう。制約から、以下が言える

f:id:agw:20131011165911p:image

  • したがって、

f:id:agw:20131008183859p:image

  • であるので、

f:id:agw:20131008183900p:image

  • となる。これを変形すると、先に直感から求めた式を証明できた

f:id:agw:20131008183901p:image

  • これを使って、maxdiff(S, T)を整理しよう

f:id:agw:20131011172010p:image

  • すっっっごくすっきりした
    • maxを取っている両方の値ともΣB_i - ΣA_iという形になった
  • つまり、全てのSとTの分け方について、Σi∈SBi - Σi∈TAiを列挙していることが分かる。これを集合Xと置く(再掲)

f:id:agw:20131008183903p:image

  • また、これを視覚化すると以下となる(再掲)

f:id:agw:20131008183919p:image

  • さて、整理したmaxdiff(S, T)は以下のようなものであった

f:id:agw:20131008183933p:image

  • S、Tと分けた場合とT、Sと分けた場合の結果は対の関係になっていそうだ。直感から、集合Xの値はある値を境に線対称になっているのではないかと推測できる
  • つまり、以下の集合Xから、

f:id:agw:20131008183934p:image

  • 対となる集合X'が算出出来るのではないだろうか

f:id:agw:20131008183935p:image

  • ここで以下を考えてみよう

f:id:agw:20131008183936p:image

  • 同様に、

f:id:agw:20131008183937p:image

  • これより、

f:id:agw:20131008183938p:image

  • したがって

f:id:agw:20131008183939p:image

  • つまり、集合Xの値の分布は直線x = (Σi∈UBi - Σi∈UAi) / 2で線対称となっていると言える
  • 視覚化してみよう
    • 確かにそれぞれの値に線対称になっている対の値があるようだ

f:id:agw:20131008183951p:image

  • つまり、求めるmaxdiff(S, T)の値は必ず集合の値の中央値以上の値となる

f:id:agw:20131008183933p:image

  • そのため、以下の条件を満たす値を探せばよい(再掲)

f:id:agw:20131008184026p:image

  • うおぉぉぉ
  • 頭超すっきりした

  • すっきり理解したので、自分なりに実装してみよう
    • エントリとしては冗長だが、自分としては大事な行為なので、お許し願いたい

以下の実装はシステムテストを通る。

#define ZERO 550000


class MayTheBestPetWin {
public:
  int calc(std::vector<int> A, std::vector<int> B) {
    std::vector<bool> curr(1111111, false), next(1111111, false);

    int AA = std::accumulate(ALL(A), 0);
    int BB = std::accumulate(ALL(B), 0);

    curr[ZERO] = true;

    for (int i = 0, size = A.size(); i < size; i ++) {
      std::fill(ALL(next), false);

      for (int j = - AA; j <= BB; j ++)
        if (curr[j + ZERO])
          next[j - A[i] + ZERO] = next[j + B[i] + ZERO] = true;

      curr.swap(next);
    }

    for (int i = (BB - AA + 1) / 2; ; i ++)
      if (curr[i + ZERO])
        return i;

    // The code never reaches here.
    return -1;
  }
};
  • 一回システムテストを落とした
    • 後半の反復の開始値を(BB - AA) / 2としていたからだ
    • @drken1215さんの実装では、これをきっちり回避している。すごい
  • また、探索範囲は以下としている

f:id:agw:20131011120234p:image

  • こちらも間に合うので、配列で確保している値の範囲分、全部探してしまっても良さそうだ
  • 大変勉強になった

まとめ

  • SRM 593 Div II 450の式変形による解法と、@drken1215さんの解法のコードリーディングと考察を行った
  • 式変形は機械的で「おぅ」と唸るものだったが、今の自分には@drken1215さんの解法がすんなり出てくるかどうかが重要な気がする
  • 恐ろしく充実した復習であった
  • @drken1215さん、どうもありがとうございました

おまけ

@drken1215さんにいただいたアドバイスをまとめた。

twitter:387297350990823424:detail

|