keyword DFS C++ 概要 ボード(1000*80以下)が与えられる。各セルは牧草地であるかそうでないかの2種類。牧草地が繋がっているのをひとまとめにして考えるとき、最大のクラスタの大きさを求める問題。 よくある探索の問題。書くだけなのにWAくらってびっくり…

keyword BruteForce C++ 概要 飼っているN( 病気の種類が少ないので全探索する。計算量は最大でも(15,7)*1000なので余裕。

keyword C++ 概要 整数の足し算をするとき繰り上がりが何回起こるかを求める問題。 書くだけ。これで丁度250問達成。ようやく目標の半分に達したけど、200~250は割とスムーズに進んだと思う。

keyword 幾何 外心 C++ 概要 平面上の3点が与えられたとき、外接円の方程式を出力する問題。 既にライブラリがあったが、sin2A, sin2B, sin2Cの重み付き平均を利用したものだったせいか誤差死。ググってみると面積をつかって求める方法発見。実装してみてsub…

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で実装(今考…

keyword 幾何 C++ 概要 点M_0とA_0,A_1,…,A_(n-1)が与えられる。このとき点列M_iをA_(i-1 mod n)に関してM_i-1と対象な点として定めるときM_jの座標を求める問題(n jが大きいので、きっとMは周期を持つか回転をするんだろうなと予測。とりあえずサンプルで点…

keyword シミュレーション C++ 概要 コンテスト(複数)の結果が与えられる。各コンテストでは1位から順にp[i]ポイントが与えられる。ここでポイント、1位の回数、2位の回数、…で順位付けしたときのトップと1位の回数、ポイント、2位の回数、…で順位付けしたと…

keyword グラフ 有向グラフ C++ 概要 n個の都市と有向の辺があり、環状に繋がっている(向きは考慮しない)。各辺の向きを逆にするのに必要なコストが与えられる。任意の都市から別の任意の都市まで行けるようにするには最小でどれだけのコストが必要か求める…

keyword 多項式 行列 分割統治 C++ 概要 行列A(30*30以下)とk( kが大きいのでO(log k)は必須。まさか公式一発ということもないだろう。そう考えると分割統治の発見は容易で、{A+…+A^(k/2)} + A^(k/2){A+…+A^(k/2)}で求まりそう。分割統治はなかなか書けない…

keyword シミュレーション C++ 概要 金額と、金利と毎年の手数料の組と年数が与えられる。決められた年数で最大お金がどれだけ増やせるかを求める問題。 問題文が長いけど、ひねりは無い。読めたら後は書くだけ。調べるの面倒で変数名にtanriとかhukuriとか…

keyword シミュレーション C++ 概要 長方形のケーキを何度かに分けて切った。各ピースの面積を小さい順に出力する問題。 入力の渡され方がとても面倒くさいけど基本的には実装ゲー。毎回番号を振りなおすというよく分からないことをしているのでmultisetで何…

keyword 二分木 C++ 概要 根が(1,1)の二分木があり、(a,b)の左の子は(a+b,b)、右の子は(a,a+b)である。(x,y)が与えられたとき、根から左右にそれぞれ何回落ちたらその頂点にたどり着けるかを求める問題。 TopCoderのSRMだったかTCOだったかで似たような問題…

keyword 互除法 Nim C++ 概要 2つの数a,bがある。プレイヤーはaとbの大きい方から小さい数の何倍かを交互に引いていく。最初に数を0にした方が勝つ。最善を尽くしたとき先手と後手のどちらが勝つか求める問題。 ユークリッドの互除法でgcd(x,y)を呼んだときx…

keyword 最短経路 BFS BruteForce C++ 概要 地図とゴミの位置とロボットの初期位置が与えられる。ロボットがゴミを拾うのに最短で歩く距離を求める問題。ゴミの位置は10以下。地図は20*20以下。 前処理として各ゴミと初期位置間の距離をBFSとかで計算してお…

keyword MST Kruskal Union-Find C++ 概要 問題文は読んでないけど図だけ見てMSTだと決め打ち。連結性だけ確認して実装にかかる。改行コードの処理とかで手間取ったけどMST自体は最近よく書くのですんなり書けた。

keyword 探索 DFS C++ 概要 w*h(w,h

keyword ソート 標準入力 区切り文字 C++ 概要 文字列と数の混合の配列が与えられる。文字列と数の位置関係はそのままに文字列と数をそれぞれソートする問題。数値が出現した番号を覚えておけばソートするだけ。入力が,で区切られるので区切り文字を使うとち…

keyword 連想配列 C++ 概要 選挙の候補者と政党のリスト、投票結果が与えられる。当選した人の所属する政党を出力する問題。 連想配列が使えれば(使えなくても)実装するだけ。それでも中々スマートに書くのは難しい。