ABC 071 C問題 Make a Rectangle - おふとん王国のコードと同じで，各数の個数を前から数えていくコードがシンプルじゃない感じになっています．解説に書いてある実装を復習する．
シンプル解で，配列ではなくsetとかに情報を持たせれば，計算量的に間に合うということもわかってはいましたが，setをそんなに使ったことがなかったのでやめました．蟻本を読み返す．

2018-07-07

ABC 072 C問題　Together

問題

C - Together

考察の流れ

ある $X$ を選んだとき， $a_i =X$ となる $i$ の個数を最大化する．

まず， $X$ を固定した場合． $a_i =X$ となる $i$ の個数を最大化するには，数列中の全ての $X-1$ に+1，全ての $X+1$ に-1してあげればいい．

そして， $X$ として何を選べば $a_i =X$ となる $i$ の個数を最大化できるかについては， $X$ として考えられる値を全て調べてあげればいい．各 $X$ に対し，数列中の $X-1$ ， $X$ ， $X+1$ の個数の和を出してあげてそれが最大となる $X$ を探す．数列中の $X-1$ ， $X$ ， $X+1$ の個数の和を出す処理は，数列をあらかじめソートしておいて二分探索することでO(log N)で可能となる．

また， $X$ として考えるべきなのは，数列の値の範囲内のみで問題ない（0 $\leq$ $X$ <10⁵）．

以上より全体としての計算量はO(10⁵ log N)なので間に合わせることができる．

コード

Submission #2760497 - AtCoder Beginner Contest 072

1発AC　20 minくらいで解いた．

反省

カッコよく二分探索をキメたつもりでいたけど， $X$ を列挙するループ内で毎回二分探索をする必要はない（最初に各数の個数を調べておけばよかった）．これで計算量を落とすことができる．
とはいえ確実に行けるかつ間に合うやり方で通せたのは良かった．

2018-07-06

ABC 069 C問題　4-adjacent

なるべく一日一題を目標に…（三日坊主になってしまいそうですが）

問題

C - 4-adjacent

すぬけくん登場！

考察の流れ

となりあった要素をかけたら全部4の倍数になるようにうまく並べ替える方法があるか？

数列の各数を「奇数」「2の倍数だが4の倍数でない」「4の倍数」の3つに分類したとき，奇数と隣り合う数は絶対4の倍数でないとだめであるため，それらを前から詰めていくことを考える．

奇数がある場合

(奇数の個数)+1 <(4の倍数の個数)なら，前から奇数と4の倍数を交互につめればいい．
(奇数の個数)+1 = (4の倍数の個数)ときうまく並び替えられるのは (奇数の個数)+(4の倍数の個数)=(数列のサイズ)になる場合．もし，(奇数の個数)+(4の倍数の個数)<(数列のサイズ)になる場合は，奇数と4の倍数を交互に詰めていったとき，「奇数」「2の倍数だが4の倍数でない」という並びができてしまい，実現不可能．

奇数がない場合

全て偶数なため，どんな並べ方をしても，隣り合う要素をかければ4の倍数となる

というわけで，「奇数」と「4の倍数」の個数を入力受取時にカウントすれば，ループを回さなくてもO(1)で解くことができる！

コード

Submission #2794671 - AtCoder Beginner Contest 069

1発AC　所要時間20minくらい

反省

Cなのに400点問題なので解けるか不安でしたがなんとか1発ACをいただきました．O(1)解にたどり着くことができてよかった．
場合分けのところで本当にこれで網羅できてるのかな？と混乱してしまいました．サンプルのテストケースを見てパターンを導き出した感じですが，場合分けの力は磨いていきたいところです．特に解説を読むとよりシンプルな場合分けをしています．

2018-07-05

ABC 071 C問題　Make a Rectangle

かかった時間：30min 1発AC

考察の過程

面積を大きくしたいので長い棒から貪欲にとっていけばいい．

ただ長方形でなければいけないので，同じ長さの棒が2本以上あるところからとらなければならない．

また，4本以上同じ長さのものがあったらそこから4本とって正方形にしてしまえばいい．

ソートして長い方から見ていけばいいので，計算量はO(N logN)となる．

コード

https://beta.atcoder.jp/contests/abc071/submissions/2760584

反省

同じ長さの棒の本数を数える→長方形の辺にするかの判定をするところが3分岐していてややこしい感じになってしまっている．
他の人のコードなどを見ると，すべての棒を見ていき，同じ長さの棒が2本あったら1セットとしてリストなどに放り込む→全て放り込んだ上で，それを長い方から見ていって2セットとったのが答え，としている．こういうシンプルな考え方ができるようにならなければいけない．アルゴリズムがややこしくて間違えそう，なときはシンプルに考えられないか？を常に問いかけること（自戒）．

2018-07-05

ABC 070 C問題　Multiple Clocks

競技プログラミング

競技プログラミングの問題解いた振り返りを残していくといいとどこかで聞いたので，恥さらしを始めてみます．

かかった時間：25min 1発AC

考察の過程

T_i　（1≦i≦N）　の最小公倍数が答えになる．

愚直解としては，答えは10¹⁸以下であることがわかっているので1以上10¹⁸以下の範囲の整数をすべて試して，それらがすべてのT_i　（1≦i≦N）で割り切れるか判定すればいいけど，O(10¹⁸ × 100)で間に合わない．

では，最小公倍数を求められるもっと計算量の小さいアルゴリズムはないか？約数問題で軽いアルゴリズムといえばユークリッドの互除法（整数aとbの最大公約数の計算量はO(log max(a,b)) ）→最大公約数を使って最小公倍数を求めていけないか？

→lcm(i)をT_1〜T_iの最小公倍数とする．lcm(i+1)=lcm(i)×T_i / (lcm(i)とT_iの最大公約数)　なのでiを1〜Nまで動かしていけば，計算量がO(N log(max(T_i)))

という感じで考えました．

コード

Submission #2791105 - AtCoder Beginner Contest 070

反省

計算量から解法を考えられるようになったのは成長した．
ユークリッドの互除法を思い出すことができた．
はじめ，lcm(i+1)=lcm(i)×T_i / (lcm(i)とT_iの最大公約数)の計算で桁あふれすることを考慮してなくておかしな結果になってなんでだろ〜？となり時間がかかってしまった…どうも，大きな数同士の計算の桁あふれに鈍感な傾向にあるので，今後の気をつけるポイント．
コードを見返すとlcm(i)とT_i のmax，minを取るという無駄な処理をしている…
とはいえ少し前までは解法すら思い浮かばなかったと思うのでこれでも進歩しているのです．