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…

keyword 幾何 C++ 概要 2次元平面上の格子点が3つ与えられる。その三角形の内部にある格子点の個数を求める問題。 ピックの公式。計算量はgcdがボトルネックでO(log X_RANGE)。

keyword 動的計画法 RMQ 平方分割 C 概要 2部グラフの完全マッチング(2部グラフの頂点数2V(V 2部グラフを1次元配列asで表現する。iを小さい順から増やすことにして、bs[ as[i] ]を、辺i->as[i]を使ったときに、その辺より上側で取れる最大の個数+1とする。そ…

keyword C 概要 連立1次方程式を解く問題。 どう見てもやるだけなのに単純なミスと入出力に対する不信感とデバッグ出力の消し忘れで大量にWAをもらってしまった。あと題名は何かの冗談だとおもう。計算量O(strlen)。

keyword Trie C++ 概要 10桁以下の数字列がN( 色々やりかたはあると思うけど最近書いたTrieを復習がてら書いてみた。newしたりdeleteする部分で時間をとられていたらしくTLEしたので、必要な領域は予め確保しておいた。計算量O(N*MAX_LEN)。

keyword 整数 素因数分解 級数 C++ 概要 a,b( 約数の和は素因数分解してΠa_i^f_iとなるときΠ(Σa_i^k)で与えられる。約数の個数は高々log a個だし、素因数分解はO(√a)でできるので問題ない。後は等比級数の和を計算する部分だが、蟻本を参考にして解いた。計…

keyword 最小全域木 C++ 概要 2次元平面上にN( 既に連結している情報をunion-findで持っておけば、あとは普通の最小全域木と同じ問題。計算量O(N^2 log N)。

keyword メモ化再帰 C 概要 (,),[,]の組み合わせからなる文字列(長さN memo[始点][終点]として再帰的に解く。A,Bが正しい文字列だとすると()A、A()、(A)、ABのパターンしかないからその全てを考えてやる。ABのパターンを忘れて時間を取られた。計算量O(N^3)。

keyword C 概要 コインがN( 数が小さいのでやるだけ、なんだけど妙に引っかかってしまった。

keyword 整数 Greedy C 概要 整数N(5 数列の長さを稼いだ方が良い。なので、2+3+...+mがNを越えないような最大のmを求めて、余った分は数列の大きいほうから足していけば良い。余りは√Nを越えないので、計算量はO(√n)。

keyword 強連結成分分解 C 概要 ノード数V(下流)に含まれる全ての要素を出力する問題。 強連結成分分解するだけ。計算量O(V+E)。

keyword 有理数 C 概要 分子、分母が1桁の整数の足し算、引き算をする問題。 やるだけ、としか…。

keyword 文字列処理 C 概要 Java風な書き方(hogePiyo)とC++風な書き方(hoge_piyo)を相互に変換する。 実装するだけ。なんだけどコーナーケースやgetsの改行云々でミスを重ねた。計算量O(N)。

keyword 2分探索 Greedy C 概要 これからN(

keyword 平面走査法 座標圧縮 C++ 概要 横に長いボードがある。ポスターがN(

keyword BFS C++ 概要 A( 状態が100*100しかないので幅優先で調べる。経路復元も定石通り直前の状態を記憶しておく。計算量はO(A*B)。

keyword 最小全域木 C++ 概要 連結なグラフ（辺に重みがある）が与えられる。最小全域木が一意であるかどうか判定する問題。 基本的には普通にKruskalで書く。同じ辺の重みがあるときに、既に確定してる辺を通じて連結になっていない頂点同士の辺を取りあえ…

keyword 幾何 C 概要 2次元平面上の点がN(

keyword 半分全列挙 C++ 概要 濃度N a+bの組み合わせを全列挙して全てのd-cの組み合わせに対して2分探索をかける。でも重複云々が想像以上に厄介で困った。要素が正なら簡単なんだけど、負の場合があるのでa

keyword しりとり C 概要 N( 一筆書きを簡単にしたようなもの。先頭の文字と末尾に出てくるアルファベットを勘定して、先頭に現れる回数=末尾に出てくる回数+1のアルファベットがあればそこをスタートにして、先頭に現れる回数=末尾に出てくる回数-1のアルフ…

keyword C 概要 13:24:35とかを01:24:35pmとかに置き換える問題。

keyword 文字列処理 C 概要 文章中のyouをweに置き換える問題。行頭や行末にくると処理が若干面倒なので番兵を置いた。