mayoko’s diary

プロコンとかいろいろ。

POJ

POJ 1741: Tree

POJ

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

POJ 3074: Sudoku

POJ

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

POJ 2559: Largest Rectangle in a Histogram

POJ

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

POJ 3709: K-Anonymous Sequence

POJ

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

POJ 2187: Beauty Contest

POJ

蟻本奴です。 問題 2187 -- Beauty Contest2 次元平面上に N 個の点が与えられる。最も遠い位置関係にある2つの頂点間の距離の二乗の値を求めよ。 解法 蟻本の p233 に書いてあるやつです。ふたつ目の解法でやりました。ひとつ目の解法では「凸包の頂点数は…

POJ 2932 Coneology

POJ

蟻本の練習です。 問題 2932 -- Coneology二次元平面上に N 個の円がある。これらの円は互いに交差しないことが保証されている。 「他の円の内部にない」という条件を満たす円を列挙せよ。 解法 蟻本 p231 の問題です。平面走査で解けます。x 軸の小さい順に…

POJ 2217: Secretary

POJ

蟻本ツアーです。これ KMP(table を作る部分) で解けそうですがせっかくなので suffix array で解きました。 問題 2217 -- Secretary 解法 S += T とやって2つの文字を合体させた後, lcp テーブルを作ります。で, S の前半側と S の後半側で一致する文字数…

POJ 3581: Sequence

POJ

suffix array まわりの問題をあんまり解いたことがないので解いてみました。蟻本のやつです。 問題 3581 -- Sequence 解法 蟻本 338 ページに書いてある通りです。最初の区切りは「一番大きい数が一番前にある」という制約から, 数列を逆順に見た時の接尾辞…

POJ 1990 MooFest

POJ

問題 1990 -- MooFest 解法 まず考え方ですが, v(i) が小さい順に牛を並べていく, というふうに考えた場合, i 番目の牛の volume threshold が v(i) 以下の牛と対をなしてつくられるコストは, v(i) * (それぞれの牛との距離)というようになります。また, そ…

POJ 2104 K-th Number その 2

POJ

蟻本に書いてあるから別に解説は書きませんがとりあえずメモ。 問題 2104 -- K-th Number 解法 はい。 const int ST_SIZE = (1<<18)-1; const int MAXN = 100010; int N, M; int A[MAXN]; int nums[MAXN]; vector<int> dat[ST_SIZE]; void init(int k, int l, int</int>…

POJ 2104 K-th Number

POJ

実は蟻本の平方分割のところから読んでなかったので読んでます。 問題 2104 -- K-th Number 解法 蟻本通り。ただ B = 1000 だと TLE して, 900 だと通りました。 const int MAXN = 100010; const int B = 900; int N, M; int A[MAXN]; int nums[MAXN]; vector<int></int>…

POJ 2991 Crane

POJ

昔蟻本読んだ時「は???」ってなってたところを読み返したら理解できたので書いておきます。 問題 2991 -- Crane 解法 蟻本のとおりですが, 若干説明がわかりにくいので図を載せておきます。 ある区間のクレーンの集合を左側と右側に分けることを考えます…

POJ 3046 Ant Counting

POJ

この解法 TLE すると思ってたので「は?」と言わざるを得ない。 問題 3046 -- Ant Counting 解法 dp[n][t] = (n 種類目まで見ている時点で, セットの大きさが t 以下になるような集合の数)とします。 すると, dp[n][t] は, n 種類目まででセットの大きさが t…

POJ 3280 Cheapest Palindrome

POJ

今では典型ですね。 問題 3280 -- Cheapest Palindrome 解法 典型なので略。 const int INF = 1e9; int dp[2020][2020]; int cost[26][2]; string s; int dfs(int l, int r) { if (l >= r) return 0; int& ret = dp[l][r]; if (ret != -1) return ret; ret =…

POJ 3616 Milking Time

POJ

dp の練習で蟻本のやつを解いてみました。これは簡単。 問題 3616 -- Milking Time 解法 まずスタートの時間ごとにソートする。dp[m] = (m 番目から最後までの milking time だけで最大化しようとした場合の最大値)として, 適当に dp する。 struct Milk { i…

POJ 3691 DNA repair

POJ

蟻本の文字列の章読んでたら出てきたので解きました。POJ めっちゃ久しぶりや… 前やった SRM の問題に似てます。SRM 519 div1 med:RequiredSubstrings - mayoko’s diarymayokoex.hatenablog.com 問題 3691 -- DNA repair 解法 蟻本に書いてあるとおり。 cons…