問題 No.399 動的な領主 - yukicoder 解法 各頂点を通った回数が数えられれば, その頂点で合計かかった金額は, (cnt+1)*cnt/2 と求められます。よって, 各頂点の通った回数を求めることを目標にします。これは tree 上で imos 法をすると解けます。この発想…

問題 No.398 ハーフパイプ(2) - yukicoder 解法 dp します。dp[i][mini][maxi][sum] = (i 番目までで最小値が mini, 最大値が maxi, 合計が sum になっているような場合の数)とします。この dp は状態が O(6*W*W*6*W) で, 遷移に O(W) かかり, 結構計算量が…

問題 My friends are small | Aizu Online Judge 解法 ある集合が有効かどうかを調べるときは, 「まだ選ばれていないやつの中で一番重さの小さい友達をリュックの中に入れることができないか」というのが判定基準になります。そこで, 配列 w をソートしたの…

alien「ありえんよさみが深いw」— マヨ子@大天使クサハエル (@mayoko_) 2016年7月7日 問題 Alien's Counting | Aizu Online Judge宇宙人に N 本の指があり, この間に M 個の拘束条件が成り立っている。各拘束条件は, 「i 番目の指を曲げたら j 番目の指も自…

問題 No.393 2本の竹 - yukicoder 解法 想定解とはちょっと違う解法になりました。考察で, 「長さの短い竹をなるべく受け付ける方が良い」というのは変わりません。なので, 配列 A をソートしておけば, 選ばれる竹は, [0, upper) というような区間を選ぶこと…

問題 TopCoder Statistics - Problem Statement頂点の接続関係が与えられる。 以下の性質を持つような木の場合の数を求めよ。 葉を除くすべての頂点は, 子を 1 つか 2 つ持つ 木の根からの距離を rank とすると, rank = k の場所には 2^k 個(ただし rank が…

問題 TopCoder Statistics - Problem Statementチェスのナイトのようなものを考える。チェスのナイトは今いる位置から (+1, +2), (+1, -2), (-1, +2), (-1, -2), (+2, +1), (+2, -1), (-2, +1), (-2, -1) と動くことができるが, 今回のナイトは (+a, +2), (+…

珍しく秒で解ける問題でした(ここまで簡単じゃなくていいけどこういうの 1 つある方が参加する方も楽しくて良いです)。 問題 TopCoder Statistics - Problem Statementn 人の人がいる。それぞれの人には強さ s[i] が定義されている。n 人を 3 グループに分け…

問題 TopCoder Statistics - Problem Statement一列に並んだ N マスを指定された色に塗りつぶしたい(色の指定のない箇所もあるが, 何らかの色を塗る必要はある)。そのために, 以下の 2 つの操作をする。 まず, 長さ L のスタンプを作る。これには L * stampC…

こっちのほうが B っぽくない？(C++ でどうやるのか知らないけど) 問題 arc057.contest.atcoder.jp 解法 L とすると, L^2 となります。これが最小かどうかは分からないので, (L/10)^2 というように続いていきます。上の表記は実数で考えていますが, これを整…

全然解けなくて悲しい… 問題 arc057.contest.atcoder.jp 解法 sum = a1 + a2 + ... + an とします。K L x 日目以前では機嫌の良い日の日数は変わらない x+1 日目以降は全勝しているので, 勝率は常に上昇しており, 機嫌が良かったのに悪くなることはない。ま…

何か楽しそうなキャンペーンをやっていたので応募しました。プレゼントがほしかったのでみんなには内緒でこっそりやってました(といっても知ってる人多そう)。 問題 recruit.elysium.co.jp(もしかしたら このページが消えるかもしれないので問題文も書いてお…

この問題とは関係ないですが Typing War は楽しいです。 trap.tokyotech.org 問題 No.391 CODING WAR - yukicoder 解法 包除原理で解きます。N 人が M 問のいずれかに担当する場合の数は M^N 通りです。ですが, これだと N 人が M-1 種類以下の問題にしか割…

問題 No.389 ロジックパズルの組み合わせ - yukicoder 解法 sum = H1+H2+...+HK とします。すると, 塗られてないセルの数は M-sum になります。K 個の要素を分割するので, K 個の要素の間に塗られていないセルがいくつか必要です。これで合計 K-1 個の塗られ…

全探索お姉さんとアルゴリズムお姉さんはどっちが先だったんだろう？ 問題 A Holiday of Miss Brute Force | Aizu Online Judge 解法 時間に関しては 6 で割ったあまりのみを考えれば良いです。そう考えると, d[t][x][y] = (時間 t に x, y にたどり着けるよ…

問題 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 が与えられ, 以下の条件を満…