問題概要 循環小数が与えられる。ただし循環の単位は分からない。分母が最小になるように有理数で表す問題。 解法 反復単位がどうなってるか全探索する。制約がよく分からなかったので多倍長で。

問題概要 長さQ( 解法 いろいろ解き方があるらしい。 自分のやり方は、各区間をpriority queueに突っ込んで、貪欲っぽく選んでいく。ただし計算量はよく分かっていない。 蟻本にはsegtreeやバケット法を使う問題として取り上げられていた。(よく分からない) …

問題概要 ある数aがb個ある。それぞれの数を分割する作業を繰り替えした結果が与えられる。aとして考えられる最小値を求める問題。 解法 探索で頑張る。 長い順に調べた方が枝刈りしやすそうであることは直感的に分かる。 最初は、長い順に元はどの木片であ…

問題概要 長さL[i]の棒がN( 解法 長さの順にソートしておいて、短い2辺を全探索する。三角形が作れないような第3辺がいくつあるかは二分探索で求めることができる。

問題概要 長さL( 解法 rotateさせる系の問題は同じものをつなげるのが定石。このときsuffix arrayを構築してやればよい。複数あるとき最小のものを答えたいので末尾に大きい値を加えておく。

問題概要 Suffix Arrayを構築する。 スコア制で、速いO(N)だと満点がとれる。自分のは蟻本準拠のO(N * log^2(N))で60点だった。ソートをバケットソートで書き直してもはやくならなかった。

問題概要 数独を解く。 解法 蟻本の解説通り分岐の少ないものから決定する。

問題概要 X[i], Y[i], Z[i]が与えられる。各iについて、初項X[i]、公差Z[i]、末項Y[i]以下の最大のもの、について出現回数を数えると、全て偶数orどれかひとつだけ奇数になっているという。ひとつだけ奇数のものがあればその数と出現回数を求める。 解法 出…

問題概要 子供がK( 解法 W個の指定されたものによって円ができてよいのはK個全てが出現したときだけ。それ以外のときは直線が集まったものなら残りを適当につなげて円を作ることができる。連結なグラフが直線である条件は最低次数が1で最高次数が2以下である…

問題概要 ノード数V( 解法 まず根付き木の場合を考える。 頂点vを根とした部分木にハッシュ値f(v)を割り振る。f(v)は子の部分木のハッシュ値の集合から生成するようにする。この際ローリングハッシュ的な生成方法だと何故か頻繁に衝突してしまうことに注意。…

問題概要 x=0からx=L( 解法 蟻本p.73に載ってる問題。今までに通過した補給所のうちもっとも燃料の多いところを利用することにすれば良い。 ソース略。

問題概要 N( 解法 トポロジカルソートするだけ。辞書順最小とかはあらかじめ降順にソートしておけば良い。

問題概要 素数を1文字ずつ変化させてある素数からある素数への距離を求める問題。 解法 BFSで行けるはずだけど、何故か当時の自分はDijkstraしてた。それでも十分間に合う。

問題概要 長さN( 解法 2回出てくる数が打ち消されるような操作をすれば良い。もう少し具体的には、自分自身が自分自身の逆元となるような演算を決めて、単位元に加えつづければ良い。そのような操作は、例えばxorで実現できる。

問題概要 長さN(過半数回以上出現する値があればそれを出力する問題。 解法 各数が何回出現したかを数えておくだけ。

問題概要 N*N(N行列式をMOD p(0 解法 基本的には三角化で求める。ただし三角化の際逆元を求める必要があるのでそこで工夫する必要が出てくる。 pが素数の時は逆元を簡単に求めることができる。 pが合成数の時はpを素因数分解して、MOD q^kで求める問題に帰着…

問題概要 最初にN個の箱がある。そのうち任意個数の空箱を選んで、箱の中にK個の新しい箱を詰める。このような作業をT回繰り返した結果、空の箱がF個ある。全ての箱の個数を求める問題。数字はいずれも10^6以下。 解法 式一発で求められる。非空の箱の個数さ…

問題概要 二人であるゲームをする。今数xがあって、各プレイヤーは交互にxに含まれる数字(10進数表記の下)で0でないものを選び、xから引く。xを0にしたプレイヤーの勝ちとなる。両者が最善を尽くしたとき勝つのがどちらか判定する問題。先手が勝つ場合は初手…

問題概要 集合Sが与えられる。要素数N( 考えたこと 一目は半分全列挙。 a*b+cの組み合わせを全部列挙して、d*(e+f), d!=0の組み合わせも列挙して、掛け合わせて足せば良い。 mapを使って実装するもTLE。 equal_range + distanceを使って実装しなおしたらギリ…

keyword RMQ C++ 問題概要 長さN(区間で最頻値が何度表れるかというQ( 解法 まず、数列が単調なので連続する同じ数を調べる。例えば、{-1,-1,1,1,1,1,3,10,10,10}は新しい数列x={2,4,1,3} に変換する。そしてxの累積和も持っておく。クエリp,qに対して、p,q…

問題概要 N( 解法 Stirlingの近似公式を使う。小さい部分ではΓ関数を使った。

解法 ゲームと言いつつプレイヤーに選択の余地が無い。

解法 やるだけ。

問題概要=解法 (a+b,a)=a+bとなるのはa=1 or b=1のときのみ。

解法 動的計画法の練習問題というか入門問題。

解法 入力読み取るのが面倒。問題自体はやるだけ。

解法 縦を固定して数え上げるだけ。

解法 mod 10の世界でやるだけ。

解法 どんな方法でやっても通ると思う。

解法 やるだけ。ただし入力は馬鹿みたいに大きい。