ようやく修論発表も無事（？？？）終わり、少し余裕が出来たのでARC017に参加。今回こそはCを解くと意気込んでいました。 A - 素数、コンテスト、素数 N(17≤N≤1,000,000)が与えられるので、Nが素数かどうか判定する。コピペをやるだけ。 始めsqrt(1,000,000)…

CodeChefのMay Challenge 2013に挑んだ時に解けなかったWitua and Mathを解いてみました。 Witua and Math 整数Nが与えられる（2 オイラーのtotient関数をφとするとき、φ(i)/iを最大とするi(2 totient関数のWikipediaを見ると、この問題は「N以下で最大の素…

グラフ理論において、切断点(cut vertex, articulation point)とは無くす事でグラフの連結成分の数が増える頂点のことをいい、橋(bridge)とは無くす事でグラフの連結成分の数が増える辺のことをいいます。 グラフの頂点集合に対してDFSを行うと森（木の集ま…

前から最大流問題を解いてみたいなーを思っており、蟻本を購入したのをきっかけに、この前参加したFacebook Hacker Cup 2013 Round 1の2問目「Security」が二部マッチングの問題だったので解いてみました。 Security {a, b, c, d, e, f}からなるキー k があ…

ちょっと二分探索について分からないことがあったのでメモっておこうと思います。二分探索は探索空間を半分にしていくことでnの大きさの空間をO(logn)で探索出来る代表的なアルゴリズムです。地球上の人類70億人から1人を見つけるのも33回で出来ます（ちょっ…