agwの日記

SRM 611 Div II

SRM 611 Div II

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であったとすると、素因数分解したものは以下となる

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

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

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

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

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

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

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

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

次に最大公約数を考えてみよう。計算機を使って最大公約数を求める場合はユークリッドの互除法を用いるのが一般的だが、氏の手法でも考えてみよう

24と15の最大公約数を考えてみよう。これははそれぞれ、以下のように図示することができる

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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さんが大変有用なつぶやきをされていたので抜粋させていただく。