keyword 探索 C++ 概要 nに対するaddition chainとは次を満たす数列である。a_0 = 1, a_m = n, a_0 問題文中に探索しろって書いてあったから探索した。答えが小さいので実際は埋め込みした。以下のソースは埋め込み用に使ったもの。計算量は謎。

keyword 数列 2分探索 C++ 概要 長さN( A[i]をコピーしてソートし、A[i]が上位Kに入っているかどうかは2分探索で判定すれば良い。時間計算量O(N * log N)、空間計算量O(N)。

keyword 整数 素因数分解 C++ 概要 正整数Xに対してX-factor chainを1=x_0 素因数分解したときの指数だけが問題になる。指数の部分を1ずつ増やしていけば良いので最大値は指数の和。組み合わせの数は多項定理のアレ。計算量は素因数分解のO(√X)。

keyword 動的計画法 C 概要 少女がN(疲労度があり、開始時は0である。少女は1分毎に走るか休むかを選択する。時刻iに走るとD_i(疲労度が1増える。休むと疲労度が1減る。ただし負にはならない。また、一度休むと疲労度が0になるまで走ることは出来ない。また…

keyword 文字列処理 C++ 概要 L(

keyword 文字列処理 C++ 概要 数字の英語表現が与えられるので数値に変換して出力する問題。 再帰で書いた。自分にしては珍しくイテレータを引数にとる書き方で書いたけど結構便利かもしれないと思った。計算量O(N^2) (Nは単語の数、厳密にはこれに単語の長…

keyword 幾何 C++ 概要 2次元平面上にN( 座標が小さいので傾き全てを覚えておけばよい。計算量O(N^2 + |R|^2)。R^2は初期化に必要な時間。

keyword 探索 文字列処理 C 概要 テストケースはN( A,B,Cのそれぞれ今何文字目を見ているか、の情報を持って探索する。ただし、一度調べた状態を繰り返し調べないように工夫が必要。そうしないと、A=a...a, B=a...a, C=a...abでTLEになってしまう。計算量は…

keyword 探索 嘘解法 C++ 概要 p,q( そんなに簡単な問題に見えないけど何故か正答数が多くてTLEも少ない。もしやと思って何の工夫もないDFSで書いてみて投げたら通ってしまった。今まで解いたことのある問題のなかでもっとも入力が甘い問題だと思う。計算量…

keyword 強連結成分分解 概要 これも蟻本に載っていた問題。強連結成分分解はもうミスせずにかけると思う。ソース略。

keyword 2分探索 Greedy C++ 概要 蟻本に載っていた問題。殆ど解き方も同じなのでソース略。

keyword Trie C++ 概要 N( トライを構築するとき、ノードを辿る度にカウンタを増やす。こうすれば1度しか訪ねていないノードが分かるので、再び訪ねたときその様なノードに辿り着いたらその場で値を返してやれば良い。詳細はソース参照のこと。1回目のsubmit…