問題 arc051.contest.atcoder.jp 解法 rng さんの解説放送を聞いて解きました。やっぱり解説放送聞くとスッと理解しやすいですね。 rng さんが書いてたコード↓ arc051.contest.atcoder.jpまずひとつのクエリを O(WH) で処理することを考えます。長方形の形を…

問題 TopCoder Statistics - Problem Statementいつもの様に valid な括弧列を定義する(stack で上手くいく〜ってアレ)。 ある括弧列 s が与えられ, これを valid な括弧列にしたい。s に対して行える操作は l, r で特徴づけられ, 次のことを順番に行う。 [l…

問題 arc051.contest.atcoder.jp 解法 問題見た瞬間 KitayutaMart に似てると思ったんですけど Twitter 見る感じあんまりそういう感想を持った人がいなかったようです。 mayokoex.hatenablog.comただ, この問題の発想のベースは使えます。数列 a を小さい順…

問題 Dashboard - Round 1A 2016 - Google Code JamN 人の人がいる。それぞれの人 i には一人特別な存在の人がいて, BFF[i] がそれである。いま, m 人からなる以下の条件を満たすサイクルを作りたい。 サイクルをなす各人 i の左右いずれかに BFF[i] がいる …

問題 Dashboard - Round 1A 2016 - Google Code Jam行列が以下の条件を満たしている。 各行について, 要素が左から右に狭義単調増加 各列について, 要素上から下に狭義単調増加 各行, 各列単位で見るとそれぞれ N 個の要素がある。これらのうち, 2*N-1 個の…

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

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

問題 TopCoder Statistics - Problem Statementstring X に対して, f(X) = W+X+A+X+D と定義する(+ は文字列をつなぎ合わせることを表すオペレータ)。 また, f^k(X) = f(f^(k-1)(X)) と定義する。f^k(S) の中に, 文字列 F が何回現れるかを数えよ。 解法 「X…

問題 TopCoder Statistics - Problem Statement蟻が N 匹 xy 平面上にいる。それぞれの蟻の座標は (xi, yi) で, 向いている向きは direction[i](dx=1, dy=1, dx=-1, dy=-1 のいずれか) である。蟻は同時に同速度で動き始める。同時に複数匹に蟻が出会った場…

これ全然むずかしくないし 250 くらいで良いのでは…？ 問題 Off Balance | Aizu Online Judge 解法 言われたとおりやるだけです。ブロックを上から調べていき, それが地面にどれだけくっついているのかを調べます。 また, そのブロックの上に乗っかっている…

問題 Roll-A-Big-Ball | Aizu Online Judge 解法 大玉の通る線分 p1-p2 と障害物 minX-minY-maxX-maxY との間の最小距離は, p1-p2 と (minX,minY)-(minX,maxY) の距離 p1-p2 と (minX,minY)-(maxX,minY) の距離 p1-p2 と (maxX,minY)-(maxX,maxY) の距離 p1-…

問題 偏りのあるサイコロ | Aizu Online Judge 解法 実装するだけ。と言っても結構めんどくさいので実装方針を軽く書きます。サイコロのクラスを作って, init(t, f) … top と front を決めたらサイコロの状態を決定する rotate(dir)…回転させるというメソッ…

問題 Dinner | Aizu Online Judge 解法 食堂全振りをベースに考えます。ここから部分問題として, 「j 日目を自炊にしたらどうなるか」を考えてみます。 こうすると, 当然のことながら C[j] の幸福度はなくなります。また, j 日目までに自炊パワーは j 減って…

問題 FizzBuzz | Aizu Online Judge 解法 二分探索します。calc(x) = ([1, x] まで fizzbuzz を書いた時の文字数), とすると, これは [1, 10), [10, 100), ..., [10^(n-1), 10^n) , [10^n, x] の文字数をそれぞれ調べれば求めることが出来ます。これで calc(…

問題 Dashboard - Qualification Round 2016 - Google Code Jam'G', 'L' のみで構成された長さ K の文字列 original を C 回操作する。 文字列 s を操作するときは, 'G' -> K 個の 'G' が連なったものに変換 'L' -> original に変換 と操作する(なので C 回…

問題 Dashboard - Qualification Round 2016 - Google Code Jam長さ N(N >= 2) の文字列 s が以下の条件を満たしていると嬉しい。 s[0] = s[N-1] = '1' s の各文字列は '0' または '1' 文字列 s を基数 b (2 文字列の長さ N が与えられるので, 以上の条件を…

解法わかっても結構エグイ問題。 問題 TopCoder Statistics - Problem Statement0, 1, ..., N-1 番目の看板に順番に色を塗っていく。塗る色は RGB 値で構成されている。i 番目と i+1 番目の看板の間で塗る色には d1, d2 で表される制約があって, i 番目の看…

問題 TopCoder Statistics - Problem Statementn 個の要素からなる数列 B と, n 個のオペレータ(+ か -)の列 ops が与えられる。 数列 A は正整数から構成され, A[i] `ops[i]` A[i+1] = B[i] を満たすように構成しなければならない。この条件を満たす数列 A …

問題 TopCoder Statistics - Problem Statement頂点のペア (i, j) に対して, 「頂点 i と頂点 j に対する最小カットは x[i*n+j]」という条件を表す n*n 要素の配列 x が与えられる。 この条件を満たす重みつき無向グラフがあるならそれを出力し, 存在しない…

これめっちゃ難しいと思うんですけど… 問題 Prowler | Aizu Online Judge 解法 自分の周りの 8 マスの状況を全部考えてみると, 次に移動できるマスが一意に決まりそうなことに気づきます。よって, 素直に最短経路を求めてその時に通ったマスの数を求めれば良…

問題 以下のような漸化式で数列が与えられる。a[1] = 2 a[2] = 3 a[n] = a[n-1] + a[n-2] - 1また, 2 以上 10^18 以下の整数 x が与えられる。各値が互いに異なる数列 b1, b2, ... を用いて x = a[b1] + a[b2] + ... + a[bn] としたい。このような {bi} が存…

問題 And Then. How Many Are There? | Aizu Online Judge 解法 残っている円盤を状態としてメモ化再帰すればいけそうなんですが, AOJ のメモリ制限的に dp[1よく考えると, 毎回の遷移で円盤は 2 つ消えるので, 状態としては bit が偶数個/奇数個 立ったもの…

問題 TopCoder Statistics - Problem Statement 解法 選ぶグループを決めればその箱のグループで得られる石の最小値, 最大値がわかります。得られる石の数は明らかに連続に取れるので, mp という配列を用意して, mp[最小値] = (最大値) となるようにしておき…

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

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

問題 arc050.contest.atcoder.jp 解法 これを参考に RollingHash でも解いてみました。 topcoder.g.hatena.ne.jp考え方(ソートの仕方)はさっきと同じです。問題なのは, RollingHash を使ってどうやってソートをするか, ということなんですが, s.substr(lhs),…

問題 arc050.contest.atcoder.jp 解法 問題設定が以前解いた問題に似ています。 mayokoex.hatenablog.comこれから, 文字列のソートの仕方は, p suffix array の lcp を使うと上手く行きそうな気がするのでそれを考えましょう。 suffix array 求める -> lcp[i…

問題 arc050.contest.atcoder.jp 解法 「1 を A 個並べた数」を one(A) と書くことにします。この問題では one(A) と one(B) の最小公倍数を求めたいですが, そのためにとりあえず最大公約数を求めることを考えます(A one(B) を one(A) で割った余りを考える…

問題 arc050.contest.atcoder.jp 解法 二分探索で解けます。ok(med) = (med 個の花束を用意することが出来るか？) というのを判定したいです。満たさなければならない制約条件は, (それぞれの花束を作る数を a, b として)x*a + 1*b 1*a + y*b です。med = a+…

問題 codeforces.com 解法 戦略としては, JUMP するときは a[i]+1 から a[i+1]-1 のようにめっちゃ走ってから, a[i+1]+1 のように障害物の直後の場所に着地する, というようにするのが良さそうです。dp[i] = (a[i]+1 から走って JUMP することで a[par]+1 ->…