A - Two Choices (ARC115)

問題リンク

atcoder.jp

感想

茶difだができなくてすごい落ち込んだ。そもそも問題文の意味理解にかなり苦戦した（１０分ぐらい...しかも結局誤読した）。
M=20と反射的にBIT演算でやろうとしたがうまくいかず。そこから思考停止に近い感じになってしまった。
この最初の方針で崩れた時に別の解放にスイッチができていないの致命的なので演習通して直していきたい。

自分の方針

まず、いつものforでbitの0,1で問題の正解を全列挙していく。その中で各N人の回答を比較して正解数をメモし、最後に全員の回答数が違うかどうかを判断する（listで各正解数を格納し、最後にset->len(list)みたいに）。
しかし、計算量がこの方針だとO(2^M * N)となり制限時間内に間に合わない。しかも、bit管理していると0000としたいところが0となってしまうなどのコレジャナイ感がすごいする。「何とかNを外して高速化できないかな？」みたいな錯誤してたら30分ぐらいたち、心が折れて解説ページに一目散。
ここで気づく、あくまで数え上げるのは組み合わせであったと。（「みんなの正解数がことなる正解セットを数えよ」という誤読をしていた。実際は「正解数を合わせることができない二組の個数を数えよ」であった。）

解法

シンプルに比べるとO(N*N)で到底間に合わないので工夫したいが、まず純粋に二組の正解数をどのように計測すればよいかを考える。まずは同じ回答をしている部分は取り除いても構わないので除外する（どうやっても二組の正解数の差には影響しないので）。
考えるべきは異なる回答をした部分についてだが、回答が異なるということは今回2値であることから必ずどちらかが正解するということはわかる。そこを考慮すると、どのような正解セットを用意しても、奇数個異なる回答をした場合は同じ正解数にはできないというところまではいける。まだこの時点で計算量は変わらずN**Nであるからもう少し考察を挟む。

ここで一歩引いて、「異なる部分が奇数個異なる」ということはどういうことか。二組をA,Bとする。

1. (1,0) OR (0,1)の部分が奇数個ある**(【AのI番目の回答、ＢのI番目の回答】)という表現
2. A,Bのすべての回答の１と０の偶奇が異なる

2については、上記の考察を踏まえていると自然に気づきそうではある。奇数個違う文字列に同じ組み合わせを付けたところで全体の偶奇が変わらないはず。
すると、「どんな回答が来ても正解数が同じものにならない二組」は1と0の偶奇が異なるものを選ぶ組み合わせの数を求めればよい。
なので、全体の1の回答数の偶奇を調べて、最後に（１が偶数個の人数）*（１が奇数個の人数）を出力すればACとなる。

まとめの感想

いや、むずくないか。これ本当に茶色diffなの...?今緑だがしっかりわからなかったし、解説聞いてもちゃんとコンテスト中に通せる自信がない。
あり本の典型だけでなく、このように自分で考察して解くみたいな問題ができないと水色には一生上がらなさそう。

浮動小数点 なぜ誤差が起こるのか

今更も今更、小数計算でなぜ誤差が起こるのか。そして、その対策って何すればいいのだろうかというお話です。

そもそも小数は「正確」に表現できていない。

まず、コンピュータは数字を二進数で保持しているかと思います。
たとえば、56だと

56 =  111000

となり、この導出としては「56から2で割り、商を２で割り続け、商が0になったら余りを降順にして並べる」というもの。

56 / 2  = 28 + 0
28 / 2  = 14 + 0
14 / 2  = 7 + 0
7 / 2 =  3 + 1
3 / 2 = 1 + 1
1 / 2= 0 + 1

ここまでは、イメージしやすいかと思います。
では、話を小数に戻しましょう。
そもそも、小数を二進数に置き換える処理ってどのような処理をはさんで行われるかご存知ですか（恥ずかしながら、エンジニアになるまで僕は知りませんでした）
その処理とは「小数部分を2をかけ続け、一の位を取り出しながら0になるまで繰り返していく」というもの。

0.875  * 2 = 1 + 0.750
0.750 * 2 = 1 + 0.500
0.500 * 2 = 1 + 0.000
* 一の位を昇順でとっていく。

となります。
きれいに111となりましたが、実は小数でこのようなきれいな値になるほうが稀有です。
0.1~0.9の中で（小数第一位まで）、このような値になるものは0.5のみとなります。
それ以外はすべて循環小数となっており、正確な値にはなっておらず、わずかながら誤差が生まれます。

上記の理由から、小数計算については正確さを求められる場合は慎重にならなくてはいけません。

対策としては、「文字」として分けて処理をする。

ここで、今のところ私がとっている対策としては、各桁を一文字ずつ計算していくという対応です。
＊コードは別のコードに載せます。。。ここでは覚書のみとさせていただきます。

二項係数（ｎCｒ）について

高校数学ではさらっと習ったぐらいですが、まさか大人になってこんなに苦しむことになるとは思いませんでした「二項係数」
こちらをコードベース、競技プログラミングで使われている方法をまとめます。
＊こちらも自分のメモ用です。

奇数・偶数個の組み合わせ数の裏技

これは初見〇しだと思っているのですが以下のような場合

nC0 + nC2 + nC4 +...   （偶数個取り出す場合）
nC1 + nC3 + nC5 +...　（奇数個取り出す場合）

は、上式も下式も

2**(n-1)

と一発で求めることができるのです。
。。。へぇ～

さて、感覚的ですがなぜこの算出でいいのかについてちょっとした補足を。
まず、

nC0 + nC1 + nC2 + nC3 + nC4 + ... = 2**n

としたときにこれを「半分ずつ分けましょう！」とすると2**(n-1)=(1/2)*2**nとなるのはわかりますよね。
これを偶奇に二つにしたものが上記の算出になるのですが、どうですかね？めちゃくちゃな算出ですが（笑）
さすがに乱暴すぎますかね。。。

もうちょっと踏み込むと、例えば偶数個選んでいると式は以下になります。

nC0 + nC2 + nC4 +...   （偶数個取り出す場合）

まず、nC0について「ｎ個から０個選ぶ」組み合わせですが、選択する個数を一つ増やすと「ｎ個から１個選ぶ」奇数個取り出す組み合わせになるのはわかるかなと。
同様に偶数個の組み合わせ数について調べていくと、偶数個の組み合わせ数各値が、一対一で奇数個の組み合わせ数に対応しているという状況になります。
なので、全体の場合の数を半分にしたものを偶奇に当てはめて使えるといったぐあいです。
どうですかね？感覚的にもつかめたら幸いです。

ユーグリッド互除法について

競技プログラミングでよく最大公約数がらみの問題が出てそのたび解けずにおります。なので、ここらでいっちょ自分で簡単にまとめていこうかなと。
ではいきます。
＊どんどん追記していく自分用メモになります。

~~ユーグリッド互除法の簡単な証明と忘れがちな定理

まず、簡単な説明・証明から

自然数a,bについて。aをbで割った商をq,余りをrとおくと、aとbの最大公約数とbとrの最大公約数は等しい

（念のため式）

a = b * q + r

・証明（チョー丁寧）

a,bの最大公約数をG、q,rの最大公約数をgとおく。
a = b * q + r 
であるので、右辺はgで割り切れる（[右辺]＝g (b*q' + r')）-  ①
なので左辺、つまりaも割り切れるということなので、Gはgの約数となる。
①の式よりG,gの大小関係は
　　　　G >= g - ②
となる。

次に、与式を次のように変形する。
a - b * q = r
上記と同様に考える。
右辺はGで割り切れるので、gもGで割り切れ、(a' - b' * q)G = gより
　　　　g  >= G - ③
である。
②、③より
G = g であることが証明されました。
〼

一応コードも書いておきます。

long long GCD(long long x, long long y) {
    if(x<y) swap(x,y);
    if(y==0)return x;
    return GCD(y,x%y);
}

以降、上記のアルゴリズムをGCDと表記していきます。

ここから詰まったものを書き留めていきます。

最小公倍数

求め方自体は以前から知っていたのですが、少しためになるものも見つけたのでメモ。
まず、A,Bの最大公約数をG,最小公倍数をＬとすると、

G * L = A *B 

が成り立つというもの。これは以前から知っていたので最小公倍数を求めるときは

A * B / G

と反射で計算。しかし、ここでA * Bがオーバーフローする可能性は十分ありますね。そんな時は。。。

A / G * B

とするとその可能性をつぶせます。このテクは押さえておかないといつか痛い目を見るなと思ったのでメモ。

~A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

さてもう一度

A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

何回見ても？？？となってしまいます。
でも、文にするとわかるんですよね。

AをXで割った余り　＝　BをXで割った余り
とは、つまり
A = X * S + T 
B = X * S' + T

とすると、まんま冒頭で示したユーグリッド互除法なので「当たり前じゃん」となります。

そう思いまよね？ではもう一度。。。

A≡B(mod X ) の時　GCD(A,X) = GCD(B,X)となる。

。。。は？

まあ、これができると何がいいかというと

GCD(A,X) = GCD(A-X,X)

となるので、差をとる問題では「最大公約数使えねえかな？」なんてアンテナを張れるのです。（この式がうまく引き出せるようになっていればよさげ）