読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AtCoder Regular Contest 058 D - いろはちゃんとマス目 / Iroha and a Grid

問題 arc058.contest.atcoder.jp 解法 左上の座標を (1, 1), 右下の座標を (H, W) とします(座標は (y, x) )。y 座標が H-A+1 に初めて到達したときの x 座標の値で場合分けします。y 座標が H-A+1 に初めて到達したときの x 座標が i ( > B) であるとすると…

SRM 695 div1 hard BearEmptyCoin

問題 TopCoder Statistics - Problem Statementあなたは K 回コインを投げるゲームをする。コインは表裏がそれぞれ 1/2 の確率で出る。ルールは以下のとおりである。 コインを投げてまだ何も書いてない面が出たら, その面に好きな数字を書く。 出た面に書か…

SRM 695 div1 med BearKRoads

問題 TopCoder Statistics - Problem Statementグラフが与えられる。各頂点にはスコアがある。 このグラフから K 本の辺を選び, 以下のようにスコアを計算する。頂点から少なくとも 1 本の選ばれた辺が伸びている場合, その頂点のスコアを得られ, その和がス…

SRM 695 BearPasswordLexic

問題の勘違いはな。 問題 TopCoder Statistics - Problem Statement 以下の条件を満たす文字列を求めよ。ただし, 解が複数ある場合は辞書順最小のものを求めよ。 文字列の長さは N 文字列は 'a', 'b' のみで構成される 配列 x が与えられる。長さ i+1 の部分…

yukicoder No.399 動的な領主(その2)

初 HL 分解です。 問題 No.399 動的な領主 - yukicoder 解法 HL 分解を使います。下の記事が HL 分解については詳しいです。 math314.hateblo.jpまた, 以下で書かれていることは pekempey さんの記事でもまとめられています。 pekempey.hatenablog.com下のコ…

AtCoder Grand Contest 001 C - Shorten Diameter(その2)

問題 agc001.contest.atcoder.jp 解法 想定解のほうで解きます。木の直径周りではいろんな定理が成り立っていて, この辺りは知っておいた方が良いかもしれません。定義 頂点 v からの距離が最大の点との距離が最小であるような頂点を木の中心という。 木の中…

AtCoder Grand Contest 001 C - Shorten Diameter

問題 agc001.contest.atcoder.jp 解法 よくわからない理論で通ってしまったので後で想定解も書きます。ここでは本番に自分が書いた解法を書きます。頂点 v が, 木の直径をなす一つの頂点であるとします。このとき, v は葉になっていないといけないので, v か…

AtCoder Grand Contest 001 B - Mysterious Light

問題 agc001.contest.atcoder.jp 解法 こういうの, 直感的に gcd もしくはその考え方を使うような気がします。と考えて適当にやると解けそうです(本番そんな感じで適当に書いたら AC してびっくりしました)真面目な話をすると, 2 回光が反射したのちは, 必ず…

AtCoder Grand Contest 001 E - BBQ Hard

天才か… 問題 agc001.contest.atcoder.jp 解法 普通に計算しようとすると, (Ai + Aj + Bi + Bj)! / (Ai+Aj)! / (Bi+Bj)!を各 i, j について求めてその和を計算することになります。が, これだと間に合いません。そこで, 上の式をよく見ると, これは (0, 0) …

AOJ 1302 Twenty Questions

AOJ

問題 Twenty Questions | Aizu Online JudgeN 個の物体で構成された世界がある。これらすべては, M 種類の Yes/No で答えられる特徴で区別することができる。 あなたは, 今目の前にあるものがなんの物体であるかを調べたいのだが, 最悪の場合でもなるべく少…

yukicoder No.399 動的な領主

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

yukicoder No.398 ハーフパイプ(2)

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

AOJ 2333 My friends are small

AOJ

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

AOJ 2222 Alien's Counting

AOJ

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

yukicoder No.393 2本の竹

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

SRM 559 div1 med HatRack

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

SRM 559 div1 easy HyperKnight

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

SRM 694 div1 easy: TrySail

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

SRM 558 div1 easy Stamp

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

AtCoder Regular Contest 057 C - 2乗根

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

AtCoder Regular Contest 057 B - 高橋君ゲーム

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

何かを解きました

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

yukicoder No.391 CODING WAR

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

yukicoder No.389 ロジックパズルの組み合わせ

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

AOJ 2425 A Holiday of Miss Brute Force

AOJ

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

AOJ 2382 King Slime

AOJ

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

AOJ 2170 Marked Ancestor

AOJ

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

SRM 557 div1 med Incubator

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

AOJ 2182 Eleven Lover

AOJ

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

AOJ 2317 Class Representative Witch

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

AOJ 1320 City Merger

AOJ

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

AtCoder Regular Contest 056 D - サケノミ

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

yukicoder No.387 ハンコ

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

yukicoder No.386 貪欲な領主

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

yukicoder No.385 カップ麺生活

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

SRM 555 div1 med XorBoard

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

AOJ 2442 ConvexCut

AOJ

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

AOJ 2157 Dial Lock

AOJ

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

AOJ 2176 For The Peace

AOJ

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

SRM 693 div1 easy: BiconnectedDiv1

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

AtCoder Regular Contest 056 C - 部門分け

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

AtCoder Regular Contest 056 B - 駐車場

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

AOJ 2383 Rabbit Game Playing

AOJ

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

ICPC 2016 国内予選に参加しました

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

yukicoder No.377 背景パターン

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

SRM 692 div1 easy HardProof

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

AtCoder Beginner Contest 040 D - 道路の老朽化対策について

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

SRM 553 div1 med TwoConvexShapes

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

yukicoder No.381 名声値を稼ごう Extra

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

SRM 553 div1 easy Suminator

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