2017-09-01から1ヶ月間の記事一覧
CS Academy 050 Div.2 E. Min Swaps CS Academy 感想 見掛け倒しな感じがある。 解法 まず値が大きいものと小さいものが順に現れるように順列を作れば、なんとなく条件を満たしそうなことから、そのように並べてみる。その数列が小さいものからスタートする…
CS Academy 050 Div.2 Check Square CS Academy 感想 色々やり方がありそうだけど、頂点を見る順番で全探索した。 解法 4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合…
Codeforces Testing Round 1 C. Circular RMQ Problem - C - Codeforces 感想 区間加算、区間最小値を処理する遅延セグメント木をライブラリに追加したので、貼るだけの問題で試しておいた。 解法 貼るだけ。ただし入力が親切じゃないので、getlineで入力を…
CS Academy 048 D. Dominant Free Sets CS Academy 感想 アルゴリズムの正当性を証明していたにも$\ AC\ $できず......。結局FenwickTreeのクエリ処理時にMODをとっていなかっただけだった。 解法 まず$\ x\ $に関してソートしておき、その列の上で順に$\ y\…
Atcoder Grand Contest 002 F. Leftmost Ball F: Leftmost Ball - AtCoder Grand Contest 002 | AtCoder 感想 前半の考察はできたが、あとはなにも手を動かせなかった。 順序制限のある組み合わせの問題であることから、各数を頂点と見たグラフに落とし込み…
Atcoder Grand Contest 012 D. Colorful Balls 感想 前半の考察はできたのに、ほとんど同じの後半の発想がなぜかできなかった。 解法 まずすべての色が等しければ、答えは$\ 1\ $となる。以下は2種類以上の色があるものとする。操作1では色の配置を変えるこ…
CS Academy 46 Div. 1.5 C. Set Subtraction CS Academy 感想 ちょっと応用できそう。 解法 まず数列はソートしておく。そして$\ X\ $について全探索する。全探索といっても$\ X \leq A_{n - 1}\ $ですべて試していると間に合わないので、$\ X\ $の候補とし…
