解法 1文字づつやるだけ。

keyword A* RMQ BIT C++ 問題概要 ノード数V( 解法 ノード番号とコストを組にしてDijkstraすればよさげ。今回は、コストを気にしなかった場合の最小値が楽に計算できるのでA*で組んだ。また、ノード番号とコストの組を全部考えると計算量が怪しいので枝刈り…

アルゴリズムまわり 拡張ダイクストラ(そもそも意味が分かっていない。普通のダイクストラと何が違うんだろう)。 素数関連。具体的にはミラーラビンとポラードロー。できれば離散対数も。 幾何全般のライブラリの組み直し。平面幾何はcomplexで、立体幾何はs…

keyword グレイコード C++ 問題概要 整数N,a,b(N 解法 こういう数列にはグレイコードという名前が付いているらしい。調べるとa_i = i ^ (i>>1)で生成できるらしい。ちょっと考えるとN=1,2のときは解がないとわかる(もちろんa,bのハミング距離が1のとき)。そ…

keyword 集合 C++ 問題概要 0~N-1(N 解法 0~N-1から2つ選んで同じかどうかUnion Findで管理する。計算量O(N^2 * M) (実際の実装はsetで手抜きしている分log Nがかかる)。各要素がどのS_jに含まれるかで管理する方法もあって、これだと計算量O(N*M)。

keyword 平面幾何 C++ 問題概要 2次元平面上に3つの点がある。点は半径R以内にある点と連結する。全ての点が連結しているかどうか判定する問題。 解法 3つのペアの内2組以上が繋がっていたらOK。 感想 codechefにも登録してみた。アカウント作る際に入力必須…

keyword 整数 ピタゴラス数 C++ 問題概要 長さN( 条件: 2頂点の値をa,bとする。このとき、∃c in Z s.t. a,b,cの置換x,y,zが原始ピタゴラス数。 解法 10^7以下のピタゴラス数は全列挙できるかも知れない。原始ピタゴラス数はm,nを互いに素で偶奇の異なる整数…

keyword 整数 最大公約数 最小公倍数 C++ 問題概要 ノード数V( 解法 lcm(a,b)=a*b/gcd(a,b)なのである頂点間についてはa*bの値が分かる。なのである頂点の値(a*b = gcd*lcm の約数)を固定すればその頂点を含む連結成分については他の頂点の値を全て決定でき…

keyword 深さ優先探索 C++ 問題概要 10*10*10の立体で、あるマスからflood fillする問題。 感想 座標系が分かりにくくて困った。サンプルも例によって貧弱だから確認できないし。

問題概要 N( 解法 hintが与えられる度に入ってないことが確定したマスを更新する。計算量O(N*M)。区間で処理したらもっと速くなるかもしれないけど、これで十分。

keyword 2部グラフ 最小点被覆 C++ 問題概要 W*H(W,H 解法 板を置くのは連続した部分の左端か上端になる。全ての泥があるマスに対して、連続した左端のノード(in A)と上端のノード(in B)を繋いで2部グラフを作る(A群とB群は別)。あとは最小点被覆なので、例…

解法 編集距離を求めるだけ。テストケースが実は複数ある。stdio.hをincludeしなくてもEOFは-1らしい。

keyword Greedy Java 問題概要 N*N(N 解法 Greedyにやってみたら上手くいった。上手くいった理由は分からない。

keyword BruteForce C++ 問題概要 N(バイスがある。それぞれのデバイスはM( 解法 Bについて全探索する。データ構造を工夫してBを決めたらB/Pの最大値をO(N * log M)で計算できる様にする。全体の計算量はO(N^2*M*log M)。

keyword メモ化再帰 C 問題概要 dequeに配列(長さN 解法 Greedyでは駄目らしい。のでメモ化再帰して解く。memo[from][to]は[from, to)が残ったときに得られる最大値。計算量O(N^2)。

解法 蟻本を参考にして解いた。ソース略。

keyword 最小全域木 BruteForce Java 問題概要 ノード数V( 解法 下限に対して全探索する。下限さえ決めてやれば普通に最小全域木を求めると目的関数の値が計算できる。計算量O(|E|^2)。 感想 最初は下限に関して二分探索してたけどよく考えたら単調性はなか…

解法 二分探索するだけ。

keyword 有理数 グラフ C++ 問題概要 A:B = n:mという情報がN( 解法 A:B = n:mならばA->Bの重みがm/nであるようなグラフを作る。グラフは木になるので適当な点からスタートして掛け合わせながら進んでいけば良い。わざわざ有理数クラスをつくらなくても、m/n…

keyword C++ 問題概要 W*H(W,H 解法 2次元累積和で各長方形に含まれる文字を列挙しようとするとO(26*(W*H)^2)で解けない。各マスについてそれを含む長方形がいくつあるか数え上げれば良い。 感想 累積和の発想から抜けだすのに時間がかかった。

keyword 幅優先探索 C++ 問題概要 サイズ5*5のボードが与えられ、そのうちN( 解法 全状態が(25,5)通りしかないので探索が間に合う。書くだけ。 感想 最初はN(vector突っ込んでも間に合うと思う。あと相変わらず実装が遅すぎる。

keyword シミュレーション 確率 C++ 問題概要 ロボットが東西南北の方向にある確率で移動する。n( 解法 nが小さいのがどう見ても怪しい。普通にDFSしたとき、既に訪ねたところには移動しないので最大でも分岐は3つ(初手を除く)。なのでシミュレーションして…

keyword メモ化再帰 C++ 問題概要 ミッションがN( 解法 memo[知性][体力]としてメモ化再帰で解く。ただし、素朴にやるとO(M^2 * (M+N))となってTLEする。ここで、知性や体力を中途半端に割り振る必要がないことに着目して、座標圧縮風に知性か体力のどっちか…

keyword 整数 10進数 C++ 問題概要 整数N( 解法 素因数分解したとき10以上の素数があれば不可能。そうでないときは、桁数を縮めるように8,9,6,4の順で割っていく。

keyword 整数 C++ 問題概要 Y, Dが与えられたときR=Y%Dに対してR*P=0 (mod D)を満たす最小のP(>0)を求める問題。 解法 RとDが互いに素ならP=Dが答えになることは自明。なのでRとDを最大公約数で割ってやる。もちろん問題の読解が一番難しい。

keyword シミュレーション C++ 問題概要 (0,0)の地点に北を向いた人がいる。C=1とする。その人はK( 向きにしたがってCだけ歩き、右を向く。 C = digitRoot(C*multi)とする。 最終的な座標を求める問題。 解法 状態は向きとCで考えても9*4通りしかないのでル…

keyword 平面幾何 二分探索 C++ 問題概要 2次元平面上にN(=0)を求める問題。 解法 答えに関して二分探索する。できるかどうかの判定は、自分の解き方だとx_i(t)-x_j(t)が二分探索中の値に等しくなるような時刻を求めて、その時刻で他の点が含まれているかど…

keyword 期待値 Greedy C++ 問題概要 数列0,1,...,N-1(NK-1が自分の手元に来るようにしたい。最善を尽くしたとき、いくつ得ることができるの期待値を求める問題。 解法 期待値の問題ではお馴染みの線形性を使う。置換をS回シミュレートして、数字jがi_1, i_2…

keyword 最小全域木 Java 問題概要 ノード数N( 解法 接続次数が2の時点で環状になることが分かる。部分的な最小全域木は重み最大の辺を1本だけ辺を取り除いたものになる。なので重み最大の辺がいくつあるか数えるだけ。グラフの探索にDFSをやるとstack overf…

2分探索するだけ。