問題名がめっちゃヒント。 問題 TopCoder Statistics - Problem StatementH 行 W 列のグリッドが与えられる。最初グリッド上のセルはすべて 0 であるが, rowCount 回どこかの行を選んでそこのすべての 0 を 1 に変え, 1 を 0 に変える, という作業をしたのち…

問題 ConvexCut | Aizu Online Judge 解法 答えがあるとしたら, それは重心以外ありえません。重心が答えになるとき, 図形は重心に関して点対称になっているはずです。素直にそれを実装しましょう。 typedef long double Real; Real eps = 1e-12; Real add(R…

問題 Dial Lock | Aizu Online Judgek 桁の数字が与えられる。もとの数 now から target という数を作りたいが, そのために以下の動作が許される。 動作: 区間 [s, t] および数 d を選び, その区間の数について, nxt = (prev+d)%10 とする。動作回数の最小の…

for the peace という問題でキレてるの, 悲しみがある— マヨ子@大天使クサハエル (@mayoko_) 2016年6月27日 問題 For the Peace | Aizu Online Judgen 個の国がある。各国はいくつかのミサイルを持っているが, これを以下の条件を満たすようにすべて捨てたい…

問題 TopCoder Statistics - Problem Statement無向グラフが 2-edge-connected とは, 任意の頂点の組(u, v) について, グラフ上のどの辺 e を削除しても, いまだ u から v へのパスが存在することを言う。 n 頂点の無向グラフ G が与えられ, 以下の条件を満…

うーん, 80 点はほしかったかも。 問題 arc056.contest.atcoder.jp 解法 bitDP します。dp[state] = (state にあるものをうまく使ったときの最大スコア) とします。このとき, dp の更新は, state から適当な集団(state2 とする)を取り出して, 集合を state2 …

問題 arc056.contest.atcoder.jp 解法 答えに x が含まれるかどうかは, 以下のようにして判定できます。 x 以上の頂点のみを用いて, S から x に到達できる。 これはなぜかというと, もし x 未満の頂点 y が行き止まりになっておらず, その頂点を使って x に…

問題 Rabbit Game Playing | Aizu Online Judge数列 D が与えられる。これに関して, 以下の条件を満たす並べ方は何通りあるか求めよ。 条件: 任意の i について, D[i] 解法 挿入DP というやつ？dp[i] = (i 番目までの並べ方の場合の数) というのが分かってい…

ICPC 国内予選に参加しました。15 位なので去年よりすこしもらえる賞品が多いです。アジア予選は行けそうにないですね。 開始前 会場に行く前にｹﾝｷｭｰ室でごにょごにょやる。一つ小発見があったけどそのあとはそわそわして全然落ち着かない。 会場に向かう。…

問題 No.377 背景パターン - yukicoder 解法 まず蟻本の p269 に書いてある問題を解いてみましょう。これを解いてみれば, 後は似たような話です。蟻本の問題では塗り方は一次元的ですが, 今回の問題では二次元的です。そこで, 「横に w, 縦に h だけずれる場…

問題 TopCoder Statistics - Problem StatementN 頂点の有向グラフが与えられる(各頂点 i からは i 以外のすべての頂点にむかってあるコストの辺が張ってある)。 ここから適切な辺を選び, N 頂点をすべて強連結にしたい。この条件を満たすもとで, (選ばれる…

4 問目まで某実況者みたいな適当なタイトルからのこの問題名はなんか面白いですね(作問者別？)。 問題 abc040.contest.atcoder.jp 解法 クエリを先読みして, 年度が大きいものしか通れないものを優先して考えていきます。このように考えると, 一度通れるよう…

問題 TopCoder Statistics - Problem StatementN*M のグリッドを考える。セルのいくつかはすでに黒色か白色に塗られている。残りの箇所を, 以下の性質を満たすように塗りたい。 各色のセルは連結である。 各色のセルは凸である。ここで, 凸とは, 各行, 各列…

問題 No.381 名声値を稼ごう Extra - yukicoder 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jp適当に i = 1, 2, ..., 100 で実験すると, 答えが __builtin_popcount(N) となりそうなことに気付きます。実際, (極端に) N = 2^k とすると, 単純…

問題 TopCoder Statistics - Problem Statement最初に十分たくさん 0 が詰まっているスタックがある。これに次のような操作をする。 スタックに数 p を入れる スタックから 2 つの数 p, q を取り出し, p+q を入れる このような操作を順番にするプログラムが…

問題 Contest Page | CodeChef数列 F が与えられる。以下のクエリを処理せよ。 F[p] = f とする R が与えられるので, F[0]*F[R]*F[2*R]*...*F[(N-1)/R*R] の値について, 10 進法における一番上の数, 10^9+7 で割ったあまり を求める 解法 自分の解法だと 100…

まためっちゃ久しぶりに記事書いてますね…最近心に余裕がなくて全然解いてない… 問題 Contest Page | CodeChefN*M の行列が与えられる。これに対して Q 個のクエリが投げられるのでそれぞれに答えよ。 整数 a, b が与えられるので, N*M 行列の中にある a*b …

問題 Dashboard - Round 3 2016 - Google Code Jam長さ N の文字列が与えられる。また, 「i 番目の文字は j 番目の文字が現れた後しか現れてはいけない」という条件が与えられる。このような条件を満たす文字列はたくさん考えられるが, この中で「できた文字…

せっかく Round3 にまで進むことができたので参加してみたんですが, 上位陣のレベルの高さを実感してしまい場違い感を感じました…ついていけるようになりたいですね。 問題 Dashboard - Round 3 2016 - Google Code Jam長さ 2n の C か J のみが書かれた文字…

問題 abc039.contest.atcoder.jp 解法 目標になる画像のある点(i, j)が黒色なら, その点もしくはその回り 8 マスのいずれかを塗る必要があります。このいずれかで, 白色になるべきところを黒く塗ってしまうようなのがあったらダメですが, そういうのがなけれ…

問題 Contest Page | CodeChefN 個の区間 [Si, Ei] が与えられる。以下の Q 個のクエリに答えよ。 s, e が与えられるので, 上記 N 個の区間のうち, [s, e] におさまるものの個数の最大値を求める。ただし, 区間同士は交差してはいけない。i.e. [Si, Ei] と […

問題 TopCoder Statistics - Problem StatementH*W のグリッドが与えられる。各セルには 'P' か 'L' か '.' と書かれている。このグリッドから, 2 つの長方形を交差しないように選び, 以下の条件を満たすもとで 2 つの長方形内の 'L' の数 + 'P' の数 を最大…

いろんな意味で嫌らしい問題だった… 問題 TopCoder Statistics - Problem Statementi 行目に i 個のボールを並べるようにして N 行の三角形を作る。この三角形に色を塗るが, 塗る色は R, G, B の 3 種類のみ 三角形内の任意のボールについて, 隣り合ったボー…

ものすごく久しぶりに記事を書いている気がする… 問題 No.154 市バス - yukicoder 解法 この問題では, G と R のペアが存在するかどうか 存在するとしたら, そのペアについて, 対応する W が少なくとも 1 つ存在するかどうか というのが問題です。どちらも s…

問題 Contest Page | CodeChef1, 2, ..., N の順列を使って, LIS が K 個あるようなものを作れ。ただし, 1 解法 とりあえずチェックプログラムを作っておくほうが良さそうなので, まずそっちを作りましょう(下のプログラムで check ってやつ)。LIS の個数を…

問題 Contest Page | CodeChef整数 A, B, C, D が与えられる。abs( (A+p*C) - (B+q*D) ) を最小化するように p, q(p, q >= 0) を取った場合の, abs の値を求めよ。 解法 これは超典型的で, C, D の最大公約数 g に対して, abs(A+g*p - B) (p は任意の整数) …

問題 No.376 立方体のN等分 (2) - yukicoder 解法 最大のものについては明らかに N-1 が答えです。最小のものが問題ですが, よくわからない方法で解いてしまった感があります。まず N の約数を全列挙します。これをすべて格納した配列を div として, 後は約…

人類なので解くのが難しかった… 問題 No.374 コイン - yukicoder 解法 今回のゲームは離散的じゃないので, 動的計画法的 something は使えそうにないです。問題が解けるらしいことを考えると, (どちらかが必ず勝つための)戦略があるはずです。そこでわかんね…

問題 arc055.contest.atcoder.jp 解法 ABCAC の 2 つ目の A の開始位置について全探索します。この位置を rp として, 最大で A の長さをどこまで長くできるか(lenA とする)を考えます。これはローリングハッシュを使って二分探索すればできます。また, C に…

難しすぎる… 問題 arc055.contest.atcoder.jp 解法 鹿の立場に完全に寄り添って考えます。今回は問題の性格からして動的計画法な気がします(ゲームの流れ(状態)に応じて戦略を変えるというような感じになるはずなので)。ということで dp を考えるのですが, …