うーん, 気づけば簡単だなぁ… 問題 TopCoder Statistics - Problem Statement 解法 基本的に, dp[n] = (問題文中の Z) というようにして, これを上手いこと部分問題に落としこむ, というように考えます。例えば, n 個のうち下の図のような真ん中らへんの頂点…

やっぱ div2 hard も練習しないとダメですね(easy でごまかせたと思ったらこの問題で死んだ)。 問題 TopCoder Statistics - Problem Statement 解法 木に関するメモ化再帰的 dp をします。狙いとしては,v 以下の部分木で移動回数が L に制限された時に最大で…

SRM 666 の練習です。本番でなくて良かった…(easy すらものすごい時間かかった) 問題 TopCoder Statistics - Problem Statement 解法 「基本的に一直線にある頂点に向かって行くけど, 別の頂点に訪れるために寄り道をすることもある」というように考えます。…

寝オチして参加できなかった yukicoder。 問題 No.274 The Wall - yukicoder 解法 貪欲で解けます。まず, 左端のブロックが一番左に寄るようにします。そのためにブロックを回転させるかさせないかを選びます。で, ブロックは一番左端のブロックの座標が小さ…

Codeforces Round #202 (Div. 1) の練習会に参加しました。冴えてたというかなんと言うかで ABD を解けました。 問題 Problem - 348B - Codeforcescodeforces.com 解法 発想としては非常に単純です。dp[v] = v 以下の部分木でバランスされている場合に, その…

問題 TopCoder Statistics - Problem Statement 解法 とりあえず 1 * 1 = 1 なので 答えは a+b+c-3 に抑えることが出来ます。また, a A の値をとある一つの値に決めた時, あと B と C の値を決定する必要がありますが, c に合わせるほうが得です(b に合わせ…

今日から忙しくなるので解ける問題が少なくなりそうです。 問題 TopCoder Statistics - Problem Statement 解法 ソースコードを見ればわかりますが, 実は s[0] == 'A' または s[n-1] == 'A' なら Alice が勝ち, それ以外は Bob が勝ちます。Alice が勝つ場合…

B より正解者が少ないという。 問題 Problem - 571A - Codeforcescodeforces.com 解法 0 条件を満たすかを考えずに長さを割り振ると, その割り振り方は 通りあります。ここから条件を満たさないような場合の数を引いていきます。例えば, a, b, c の 3 辺の中…

Codeforces Round #317 [AimFund Thanks-Round] (Div. 1) (長い) に参加しました。 前考えていた通り B から解いてみたところ, B だけ正解してレートが上がりました。 A は解けなくてもレート上がるんや！ 問題 Problem - 571B - Codeforcescodeforces.com …

うーむ, もうちょっと時間があれば… 問題 TopCoder Statistics - Problem Statement 解法 まず N が 3*K-1 以下の場合を考えます。この場合, ボールが入っている区間の左端がどこかを特定すれば良いですが,左端の候補は N-K+1 個あり, これはたかだか 2*K な…

TCO15 Round 2D に参加しました。easy 解くのが遅すぎてひどかったですが, チャレンジを 1 回成功させたおかげでレート微増してくれました(challenge のありがたみをはじめて感じた)。もちろん Round 3 には進めませんでした。 問題 TopCoder Statistics - P…

勉強になりました。 問題 No.270 next_permutation (1) - yukicoder 解法 next_permutation の実装で, swap されるものをメモしておいて, 変化した分を適当に足しこんでいけば良いです。 next_permutation の実装は以下を参考にしましょう。英語ですがそんな…

感動しました。 問題 No.269 見栄っ張りの募金活動 - yukicoder 解法 想定解法とアイデアは変わりませんが, 計算量的に怪しい解法で通しました。一番大事なアイデアは, 「n 人目の人が前の人に比べて i 円支払うお金を増やしたら, それ以降の人はその i 円の…

問題 Problem - 557E - Codeforcescodeforces.com 解法 まず dp[i][j] = (i 文字目からの j 文字が半回文になっているかどうか)を適当に求めます。 で, sum[i][j] = (i 文字目から j 文字以上使う文字列の中で 半回文になっているものの数)とします。これを…

問題 Problem - 558D - Codeforcescodeforces.com 解法 まず ans = 1 のものを集めて範囲を絞ります。 その後に ans = 0 のものを集めて範囲を狭めていきます。 const int MAXQ = 100010; int H[MAXQ]; ll L[MAXQ], R[MAXQ], ans[MAXQ]; int main() { int h,…

問題 Problem - E - Codeforcescodeforces.com 解法 毎回のクエリでは, 区間内に存在する文字数を記録し, その文字数ごとにそれぞれの文字を区間に並べなおす, ということをします。 例えば abababbba という文字列で 2 6 1 というクエリが渡された場合, 区…

問題 Modular Query | Aizu Online Judge 解法 配列 c をソートしておき, 各クエリ q について, c[n-1] から余りを求めていくと考えます。このとき, c[i] を q で割った余りが p であるとすると, c[i]-p から c[i] までの数字は, 余りが p よりも小さいこと…

なるほど… 問題 Problem - 346C - Codeforcescodeforces.com 解法 kmjp さんの解法を参考にしました。Codeforces #201 Div1. C. Number Transformation II - kmjp's blogkmjp.hatenablog.jp int main() { cin.tie(0); ios::sync_with_stdio(false); int n; c…

昔流行ってたのかな…最近よく見る文字列の状態遷移問題。 問題 Problem - 346B - Codeforcescodeforces.com 解法 上で書いたように, まず virus の状態遷移をはっきりさせます。蟻本の 4 章に書いてある文字列テクニックを使います。で, そしたらdp[x1][x2][…

Codeforces Round #201 (Div. 1) の練習会に参加しました。結果は AB 正解でそこそこです。よく考えたらこどふぉレートあげたいんだったら B 解けるかどうかで判断すれば良い気がしてきた。 問題 Problem - 346A - Codeforcescodeforces.com 解法 d を a[1] …

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

蟻本に書いてあるから別に解説は書きませんがとりあえずメモ。 問題 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>…

実は蟻本の平方分割のところから読んでなかったので読んでます。 問題 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>…

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

なんとなく方向性わかっても実装できない… 問題 Problem - 570E - Codeforcescodeforces.com 解法 基本的には左上からと右下から同時に攻めて行く感じです(同じ文字だったら進軍可能)。で, これを求めるために dp で解きます。最初に考えたのは dp[x1][y1][x…

問題 TopCoder Statistics - Problem Statement 解法 4 本の辺を全探索します。もちろん全部調べていたら (10^8)^4 で間に合わないので, 出てきた x 座標, y 座標についてのみです。4 本の辺を決めて, その 4 本の辺に囲まれた頂点のみが正方形に囲まれると…

SRM 521 の練習会に参加しました。もうちょっとで med も解けそうだったんですか残念ながら easy だけしか通してないです。 問題 TopCoder Statistics - Problem Statement 解法 '(' と ')' の対応を見るためにスタックで管理するだけ。 class MissingParent…

SRM div1 med っぽい雰囲気。 問題 D: 引っ越し - AtCoder Regular Contest 043 | AtCoder 解法 スライド通り。 AtCoder Regular Contest 043 解説 from AtCoder Inc. www.slideshare.net const int MAXM = 1010; const ll INF = 1ll<<60; int P[MAXM]; int …

本番中解法全く思い浮かばなかったのは問題だけど, 朝からちょくちょくデバッグして 15 時にようやく AC する程度に実装力がないので解けなかった気がする。 問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder 解法 スライド通りです。 AtCoder Reg…

問題 Problem - 570D - Codeforces 解法 質問のクエリだけがやってくるので先に質問を全部読んでおきます。で, 各クエリについて, query_v[v] は頂点 v に関するクエリ番号の集合を表し, query_h[i] はクエリ番号 i の質問では高さがいくつの頂点について聞…