問題 codeforces.com文字列 s が与えられる。この文字列を以下のルールにしたがって区切る。 まず s の最初の 5 文字以上の文字を作る。 その後は, 長さを 2 か 3 にしながら区切る。区切る時, 直前に区切ってできた文字列と同じになってはならない。 この時…

問題 No.368 LCM of K-products - yukicoder 解法 最小公倍数は, 各素因数が最大のものを組み合わせたものになります。よって, 各素因数を調べて, p の素因数を考える場合は p の指数が多い順に K 個取ってくる, というようにやれば OK です。 const int MAX…

問題 No.367 ナイトの転身 - yukicoder 解法 2*H*W の頂点を作って適切に辺を貼ってダイクストラすれば良いです。 int knightX[] = {2, 1, -1, -2, -2, -1, 1, 2}; int knightY[] = {1, 2, 2, 1, -1, -2, -2, -1}; int miniX[] = {1, -1, -1, 1}; int miniY[…

問題 1741 -- Tree木グラフが与えられる。距離が K 以下の頂点の組の個数を求めよ。 解法 蟻本に書いてあるとおり重心分解します。vectorvector > G でやってると TLE するので注意しましょう。 const int MAXN = 10010; const int INF = 1e9; struct Edge {…

問題 3074 -- Sudoku数独を解け。 解法 蟻本に書いてある通りだと思ったんですが, 3076 が遅すぎて解けない…下のコードではいろいろ定数倍高速化してるんですが, これでやっと 700ms くらいです。 __builtin_popcount を使う数が 1 列で既に使っている数を r…

問題 s8pc-2.contest.atcoder.jp 解法 文字列が共通している場合, i1 からスタートする文字列 i2 からスタートする文字列 が一致している, というようになっているはずです。S[i1:N), S[i2:N) に共通文字列がある場合, それらの文字は辞書順的に連続である, …

問題 TopCoder Statistics - Problem Statementx(1 以上の整数) 人の有権者が n 人の候補者に投票をする。n 人の票獲得率(a 人から票を獲得した場合 a/x*100 )を四捨五入した一覧が与えられるので, x としてあり得る最小値を求めよ(ない場合は -1)。 解法 10…

問題 TopCoder Statistics - Problem StatementH*W の盤面があり, それぞれのセルには 0 か 1 が書かれている。これを以下の操作を繰り返すことでセルに書かれた数をすべて 0 にしたい。操作：盤面の辺を通る経路で, 左上から右下まで最短経路で行く。最短経…

問題 www.hackerearth.com 解法 mayokoex.hatenablog.com これとほとんど同じです。 struct ST { vector<int> seg, lazy; int size; ST(int n) { size = 1; while (size < n) size *= 2; seg.resize(size * 2); lazy.resize(size * 2); } void push(int k, int l,</int>…

一度で三度おいしい。 問題 s8pc-2.contest.atcoder.jp 解法 すぎむ先生に教えてもらいました。クエリで平方分割する方法です。@mayoko_ 反転クエリの両端 l, r を multiset S へ突っ込んでいくと、質問クエリに O(|S|) で答えることができます。|S| が √Q …

平方分割でも解けたので紹介しようかなと。 問題 s8pc-2.contest.atcoder.jp 解法 bit[i] = (i 番目の bit がどうなっているか) flag[i] = ([i*B, (i+1)*B) 番目の bit は bit[i] から反転させたものになっているか, cnt[i] = ([i*B, (i+1)*B) で立っている …

問題 s8pc-2.contest.atcoder.jp 解法 遅延評価セグメント木で解きました。update で [l, r) の区間を反転させ, query で [l, r) の 1 の数を求めるような機能を実現します。lazy 配列には「今考えている区間は後で反転させるつもりか」というのを覚えておき…

問題 s8pc-2.contest.atcoder.jp 解法 なんか調べると b^(a-1-i) に掛け算される係数は 1/i! * c*(c+1)*...*(c+i) になります。なのでそれを実装すれば OK です。調べ方ですが, b^3 あたりの列を調べると, b^0 の項が 1, 4, 10, ... となっています。b^2 で…

面白かったです。 問題 s8pc-2.contest.atcoder.jp 解法 「どの数で割られるか」で 2^q の場合分けをします。i1, i2, ..., im 番目の数で割られて 1 になる場合, 元の数は q[i1] * a[i2] * ... * a[im] です。 これが本当に i1, i2, ..., im でのみ割られる…

問題 s8pc-2.contest.atcoder.jp 解法 「約数 多い」で調べると, 高度合成数という言葉が出てきます。 高度合成数 - Wikipedia結局この問題ではこれを求めろ, ということなのですが, 高度合成数には次のような特徴があるようです。高度合成数は という形で素…

問題 jag2016-domestic.contest.atcoder.jp 解法 候補になる直線は, 有権者と障害物の頂点を結んだ直線ですが, これを何本も引くことを考えると結局考えるべき頂点は「有権者と障害物の頂点を結んだ直線」同士の交点であることがわかります。この点を列挙し…

誤読死しました。 問題 jag2016-domestic.contest.atcoder.jpわからなくてここを読みに来てる人はとりあえず問題文を読みなおすことをオススメします。 解法 スタックに積まれるカード群は必ず [l, r) と言った区間的になることに注目します。これに気づくと…

JAG Contest 2016 Domestic に参加しました。チーム戦楽しいですね。もう全部チームで参加したい。 問題 jag2016-domestic.contest.atcoder.jp 解法 愚直にやりました。 A, B の文字列から木を構成(dfs) 2 つの木の情報から目的の木を構成(dfs2) 目的の木を…

問題 TopCoder Statistics - Problem Statement2 行 n 列の文字群が与えられる。文字を適当に並び替えて, 「隣り合った文字同士は異なる」という性質を満たすように出来る場合, その例を一つ示せ。 解法 一種類の文字の並べ方を考えると, これは (a を並べる…

問題 TopCoder Statistics - Problem Statement地点(0, 0) から 地点(n, L) まで移動したい。ただし, 地点 (i, y) と地点 (i+1, y) は距離 w[i] だけ離れている。 移動の仕方としては 2 通りの移動の仕方がある。 (i, l1) から (i, l2) まで速度 walk で歩い…

問題 TopCoder Statistics - Problem StatementL から R までの xor を取った整数の値を求めよ。 解法 各桁ごとに bit が立っているかを調べます。 2^i の桁が立っているかどうかを調べる時は, i 桁目の bit は 2^(i+1) 周期ごとに現れたり消えたりすること…

問題 Twin book report | Aizu Online Judge 解法 本を読む時間を最短にしないといけないことに注目します。とりあえず感想を書かなければならないことは忘れて, 読むことだけを考えましょう。ある一冊の本(A とする)を読むのにかかる時間が, 他のすべての本…

問題 No.359 門松行列 - yukicoder 解法 門松列は結局数同士の大小関係で定義されますが, 大小関係が逆転する可能性があるのは, この後並べようとしている竹の高さが既に配置されている竹より大きくなる時か, 小さくなる時だけと考えられます。実はあと x > …

問題 No.362 門松ナンバー - yukicoder 解法 calc(x) = (x 以下の門松ナンバーがいくつあるか) というのがある程度高速に求められたとすると, x に関する二分探索をやれば良いです。ということで, calc 関数が欲しいですが, これは桁dp をやれば良いです。dp…

問題 TopCoder Statistics - Problem Statement同じ長さ L の文字列が n 個与えられる。これを辞書順にソートするのだが, ソートの仕方が少し特殊で, 長さ L の順列 p が与えられて, p[0] 番目の文字, p[1] 番目の文字, ..., p[L-1] 番目の文字, という順番…

蟻本めぐりです。4-4 は本当に全然読んでないことがわかりました。 問題 2559 -- Largest Rectangle in a Histogramn 個の幅 1, 高さ h1, h2, ..., hn の長方形が順番に並んでいる。この中に含まれる長方形の面積の最大値を求めよ。 解法 よくあるスタックの…

問題 No.361 門松ゲーム2 - yukicoder 解法 grundy 数やるだけです。 pekempey さんの記事がわかりやすいのでそれを参考にしましょう。今回使ったのは「山が分裂する場合の Grundy 数」です。 pekempey.hatenablog.com const int MAXL = 555; int g[MAXL], D…

蟻本の練習です。前出た convex hull trick ですね。 ていうかこの問題だと convex hull を構成するアルゴリズムと全然関係ないですね。 問題 3709 -- K-Anonymous Sequence長さ n の単調非減少数列 a が与えられる。1 回の操作で数列の 1 つの項の値を 1 だ…

問題 www.hackerrank.com 解法 まず基本的な解法ですが, 全部同じ値になったらそれが最適 そうでない場合は, 最大のものと最小のものを選択し, それぞれ -1, +1 する というのが最適です。この貪欲法を素直にやると 10%, map でやって少し工夫すると 30% の…

問題 TopCoder Statistics - Problem Statement点(x1, y1) から点(x2, y2) への距離を |x2-x1|+|y2-y1| と定義する。0 A, B, C の x の値は異なる。 A, B, C の y の値は異なる。 A -> B -> C -> A と一周する長さは minT 以上, maxT 以下でなければならない…