問題 King Slime | Aizu Online JudgeH*W のグリッド上に N 個の頂点がある。各頂点は, 上下左右いずれかの方向に移動でき, 移動する際は壁にぶつかるか別の頂点にぶつかるまで動き続ける。別の頂点にぶつかった場合, ぶつかった頂点同士は合体する。この移…

問題 Marked Ancestor | Aizu Online Judgeルートが頂点 0 の木が与えられる。頂点 0 の点は最初から黒く, それ以外の点は白い。これについて, 以下の二種類のクエリが投げられるので, 対応する。 頂点 v を選び, その点を黒く塗る。 頂点 v, もしくはその先…

問題 TopCoder Statistics - Match OverviewDAG が与えられる。次の条件を満たす頂点集合 S の最大の大きさを求めよ。 条件: 任意の異なる 2 つの頂点 i, j S について, i から j へのパスも j から i へのパスもない。 解法 この問題に関して, dilworth の…

問題 Eleven Lover | Aizu Online Judge数字のみからなる文字列 s が与えられる。この中に, 連続した文字列でその表す数が 11 の倍数であるようなものは何通りあるか。ただし, 先頭が 0 であるような数は数とみなさないことにする。 解法 区間 [i, j] が 11 …

問題 Class Representative Witch | Aizu Online Judge 解法 (S[i], T[i]) のペアごとに考えます。S[i] と T[i] の間にいくつの P[j] があるかが分かれば(これは lower_bound を使えば高速にわかる), 2 つおきの累積和を使って目的の値が求められそうです。 …

問題 City Merger | Aizu Online Judgen 個の文字列が与えられる(それぞれの文字は 20 字以下)。これら n 個を連続部分文字列として含む文字列を作りたい。この文字列の最小の長さはいくらか。 解法 bitDP します。dp[now][state] = (state にある文字列は作…

問題 arc056.contest.atcoder.jp 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jpdp[t] = (「t の時間に飲む」と決めたとき, t の時間までに得られる美味しさの総和の最大値)とします。部分点解法では, t の前に飲む時間 t1 を全探索します。t1 …

問題 No.387 ハンコ - yukicoder 解法 bitset を使うアレです。各色ごとに考えます。 色 i が現れる位置 pos を覚えておき, memo |= b*2^pos とすれば, memo という配列に「色 i が塗られる場所」が記録されます。これをすべての色について行えば良いです。 …

問題 No.386 貪欲な領主 - yukicoder 解法 よくある問題は, 「木に辺コストが与えられる。頂点 (u, v) が何個も与えられるので, u, v 間の距離を答えろ」みたいのがあります。これは LCA を使うと簡単に求めることができるので, 今回の問題もこれに帰着させ…

問題 No.385 カップ麺生活 - yukicoder 解法 お金が素数になるところは絶対に通る方が得です。そこで, dp[m] = (お金が m になるまでに買えるカップ麺) というのを覚えておくと, m が素数のところでは ans += dp[m] とする dp[m] が最大のところで ans += dp…

問題名がめっちゃヒント。 問題 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 マスのいずれかを塗る必要があります。このいずれかで, 白色になるべきところを黒く塗ってしまうようなのがあったらダメですが, そういうのがなけれ…