keyword n進数 C++ 概要 x(|x| 分からなかったので実験。あるビット数以下で表せる数は連続であることに気づく。したがってビット数がn本以下のときの上限と下限を知っておけば、上からビットを立てるべきか立てないべきか判定できる。

keyword 二項係数 C++ 約数 概要 二項係数(n,k)(k,n 階乗使った方の定義で、分子と分母が約数に2をいくつ含めるか求めればよい。2のべきで割り算するだけ。

keyword シミュレーション C++ 概要 マインスイーパのボードを復号する問題。書くだけ。

keyword 素因数分解 C++ 概要 xが与えられるとき、x=b^pとなる最大のpを求める問題。 約数の個数の最大公約数を求めるだけだろう、ということはすぐに分かった。素因数分解でなぜかxのルートまで調べればよいだろうと勘違いしてWA。修正したけど通らない。??…

keyword BruteForce C++ 概要 ボード(15*15以下)が与えられて、各セルは黒か白である。あるセルを選ぶとそのセル及び隣接するセルがフリップする。フリップの回数が最小のものを出力せよ。最小回数のものが複数あるときは辞書順最小のものを答えよ。 よくあ…

keyword C++ 概要 六角格子のセルに海or陸が割り振られている。海と陸の境界線の個数を求める問題。 すぐに思いつく方法は2通り。1つは各陸に対して隣が海かどうかを調べる方法。2つ目は各辺に対してそれを挟むセルが異なるかどうかを調べる方法。偶奇に注意…

keyword 数列 C++ 概要 長さnの数列が与えられる。隣接する要素の差を列挙したとき1,…,n-1が全て出現するかどうかを求める問題。 愚直に書くだけで良い。配列使って書くときはsegmentation faultに注意。

keyword シミュレーション Java 概要 列車を2つに分割し、分割したそれぞれを反転させても良いし、前後を入れ替えて連結してもよい。全部で何種類のパターンができるか求める問題。 サイズが小さいので全パターンを列挙すればよい。易しめの実装ゲー。

keyword シミュレーション 幾何 C++ 概要 前に同じ問題解いたことがあるなあ、と思ったらAOJじゃなくてPKUで2398:Toy Storageというのがあった。出力形式がちょっと違うだけで後は殆ど同じ。ちょっとテストケースが重くなっている程度の違いしかない。前解い…

keyword Union-Find C++ 概要 n匹の番号が振られた虫と、交配した虫のペアの情報が与えられる。このとき、両性の虫が確実に存在するかどうかを求める問題。 自力では思いつかなかったがI先生にUnion-Findで一発じゃん、と言われる。親の番号に符号をつけるな…

keyword 幾何 対象 C++ 概要 2次元平面上のユニークな点がn( 幾何はICPCで自分の担当なので復習の意味も込めて丁寧に書く。 対象点が分かれば判定するのは楽なので、対象点を探す方法を考える。重心であることに気が付けば問題は解けたも同然(点がユニークで…

keyword 動的計画法 C++ 概要 数列a_iが与えられる。a_1にa_2,...,a_nを足すか引くかする。その和をkで割りきるようにすることができるか判定する問題。n k固執してしまってはいけないというよい教訓になった。 動的計画法でやる方がよい。m番目までの和(mod…

keyword Greedy C++ 概要 n( しばらく考えて見るけど同じビンに2つまでしか入らないという制約から貪欲方で良さそう。つまり、長いものから詰めていって余裕があるなら残りに詰められる中で最長のものを詰めればよい。2分探索したいのでmultisetで実装(今考…