mayoko’s diary

プロコンとかいろいろ。

CODE FESTIVAL 2016 に参加しました

タイトル通りです。思ったことをつらつら書いていきます。 1 日目 家から追い出されたのでちょっと早めに家を出ると案の定早く着きすぎた。来ちゃった♥ pic.twitter.com/r5pIBd4dUS— マヨ子@大天使クサハエル (@mayoko_) 2016年11月26日 暇だったのでちょっ…

ハル研プロコン2016に参加しました

ハル研プロコンに参加しました。 www.hallab.co.jp個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。とりあえず自分のやったことを書いていきたいと思います。 貪欲パート 一番近くの小惑星に近づく, 最も小惑…

Codeforces Round #365 (Div. 2) C. Chris and Road

問題 codeforces.comn 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。 y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。 解法 凸多角形の左側を歩…

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

問題 codeforces.com数列 A に対して, 以下のクエリに答えよ。 区間 [l, r] に偶数個ある整数の xor を取る 解法 偶数じゃなくて奇数だったら簡単です。というのも, xor は 2 回同じ数をかけられれば自動的に 0 になるので [l, r] の区間の xor を累積和で適…

Codeforces Round #372 (Div. 1) B. Complete The Graph

いやなんか時間とってゆっくり競プロやりたいんですけど… 問題 codeforces.comコスト付きの無向グラフが与えられる。いくつかの辺のコストは好きに選べるので, s から t への最短経路の大きさを L にしたい。このようなことが可能であれば, そのうちの 1 つ…

Codeforces Round #367 (Div. 2) E. Working routine

問題 codeforces.comN*M のグリッドが与えられる。各クエリで 「(a, b), (c, d) を左上の頂点とする高さ h, 幅 w の領域を交換する」ということをする(ただし, 交換する長方形は辺やセルを共有しない)。 全てのクエリを処理した後の最終的なグリッドの状態を…

Codeforces Round #368 (Div. 2) D. Persistent Bookcase

これ普通に頭良いと思うんだけどみんな解いてるんだよなぁ… 問題 codeforces.com最初すべてのセルが塗られていないグリッドが与えられる。以下の Q 個クエリを処理し, グリッドで黒色のセルの数を出力せよ。 i 行 j 列目のセルが白なら黒くする。 i 行 j 列…

AtCoder Regular Contest 061 F - 3人でカードゲーム / Card Game for Three

問題 arc061.contest.atcoder.jp 解法 まず普通に解法を考えます。一度それぞれのカードを決めたらすでにゲームの勝敗は決まっていることを考えるとなんか dp ではないような気がします。で, 問題の性質をよく考えると A さんが勝つには A さんに N 回ターン…

AtCoder Regular Contest 061 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip

問題 arc061.contest.atcoder.jp 解法 koyumeishi さんに教えてもらいました。@mayoko_ こんな感じでわかるかなぁ…? 赤がコスト 1 、 黒がコスト 0 の辺で、最後に2で割るようにしました。 人のを見ると中継点に入る辺(出る辺)のみコスト1にする派もいるっ…

2015-2016 XVI Open Cup, Grand Prix of Bashkortostan, SKB Kontur Cup Stage 2 A. Abstract Picture

JAG 夏合宿最終日に yurahuna さんに投げたら勝手に AC してくれた問題です。 問題 codeforces.comN*N のグリッド上に色を塗りたい。 1 回の操作では行に同じ色をバーっと塗るか列に同じ色をバーッと塗るかしかない。最終的に塗りたい配色が与えられるので, …

JAG 夏合宿 Day3 G - Share the Ruins Preservation

問題 jag2016autumn.contest.atcoder.jp二次元平面上に点が N 個与えられる。ある X 座標を境に二つの頂点を分割し, それぞれで凸包を作る。この二つの凸包の面積の和を最小化せよ。 解法 蟻本に載っている凸包は, 凸包の下側と上側に分けて凸包を構成します…

JAG 夏合宿 Day3 F - Escape from the Hell

問題文は面白かったんですが実装はつらかったです。 問題 jag2016autumn.contest.atcoder.jp 解法 最後に A[i] 登るところ以外は, 明らかに D[j] = A[j] - B[j] が大きい順に使うのが最適です。この j をどこまで使うかで場合分けします。j の最大値も j あ…

SRM 566 div1 med: PenguinEmperor

問題 TopCoder Statistics - Problem Statement 解法 入力の名前が長いので, n, m とします。 見た目からして行列累乗っぽい感じがします。具体的には, まず dp[i][j] = (i 日目に場所 j にいるような場合の数) というのを i で, それを調べ終わったら m/n …

SRM 566 div1 easy: PenguinSledding

問題 TopCoder Statistics - Problem Statementn 頂点の無向グラフが与えられる。このグラフから辺をいくつか選ぶとき, 以下の条件を満たす選び方の場合の数を求めよ。条件: 選んだ辺上の頂点を 2 次元平面上でどのように配置しても(ただし 3 頂点が同一直線…

JAG 夏合宿 Day2 A - Parades

問題 jag2016summer-day2.contest.atcoder.jpN 頂点からなる木がある。各頂点の次数はたかだか 10 である。このグラフ上でいくつかのパレードを開きたい。パレードの候補は M 個あり, その各パレードは頂点 u から 頂点 v へのパスで構成される。 これらのパ…

院試(東京大学大学院情報理工工学研究科 システム情報学 2016)

院試の受験記です。なんかの参考になれば。 準備編 試験は 英語(TOEFL ITP) 数学 専門 面接 があります。日程的に英語 -> (しばらく間が空く) -> 数学 -> 専門 -> 面接 でした(数学と専門は同じ日にやってほしい感)。噂によると筆記試験(面接以外)でほぼ結果…

JAG 夏合宿に参加しました

楽しかったです。 前日 家で高速回転したり奇声を発したりしながら楽しみにしてました。 1 日目 と言ってもシャイなのでビクビクしながら会場入りしました。 自己紹介でクソなぞなぞに言及したところ結構知られてるイメージでした。うれしい。 ゆらふなさん…

AIM Tech Round 3 (Div. 1) C. Centroids

問題 codeforces.com頂点数 n の木 T 上の点 v が T の centorid であるとは, T から v を取り除いて得られる任意の連結成分が, 全て頂点数 n/2 以下であることを言う。各頂点について, その頂点が以下の操作を一回以下許したとき centroid になるかどうかを…

AIM Tech Round 3 (Div. 1) B. Recover the String

問題 codeforces.com0, 1 のみから構成される文字列で, 以下を満たすものを作れ。 00 の部分文字列が a00 個ある 01 の部分文字列が a01 個ある 10 の部分文字列が a10 個ある 11 の部分文字列が a11 個ある 連続部分文字列ではないことに注意。 解法 0 が n…

AOJ 2439 Hakone

AOJ

問題 Hakone | Aizu Online Judge 解法 まず, '-' があるところは順位が一意的に決まるので, 無視して良いです。与えられる文字列は 'U' と 'D' しか含まれないものとしましょう。そしたら dp します。問題では今の中継地点での i 位の人が, 前の中継地点で…

Codeforces Round #366 (Div. 2) C. Thor

問題 codeforces.comq 個のクエリが飛んでくる。それぞれのクエリは type, x の二つの整数から構成され, type = 1 の時, 種類 x のボールが飛んでくる type = 2 の時, 今までに飛んできた種類 x のボールをすべて捨てる type = 3 の時, 今まで飛んできたすべ…

AOJ 2397 Three-way Branch

AOJ

問題 Three-way Branch | Aizu Online JudgeW*H のグリッドが与えられる。これらのうち, N 個のセルは通れなくなっている。あるセル(x, y) からは (x-1, y+1) or (x, y+1) or (x+1, y+1) にのみ行ける場合, (0, 0) から (W-1, H-1) までの経路は何通りあるか…

Educational Codeforces Round 16 D. Two Arithmetic Progressions

問題 codeforces.comx = a1 * k + b1 = a2 * l + b2, L 解法 k, l の組を一つ求められれば, 後は x が lcm(a1, a2) の周期で解になるので簡単です(実装が楽とは言っていない)。a1 * k + b1 = a2 * l + b2 を変形すると a1 * k - a2 * l = b2 - b1 となります…

Codeforces Round #369 (Div. 2) E. ZS and The Birthday Paradox

問題 codeforces.com整数 n, k が与えられる。p = 2^n として, 1 - (p! / p^k * (p-k)!) の分母と分子を求めよ。ただし分母と分子は非常に大きな値になることがあるので, 10^6+3 で割ったあまりを求める。 (本当は p 解法 上では p! / p^k * (p-k)! と書きま…

Codeforces Round #369 (Div. 2) Directed Roads

問題 codeforces.comn 個の頂点からなるグラフが与えられる。各頂点 i から, A[i] への有向グラフが一本ずつ生えている。このグラフの辺の向きをいくつか入れ替えることにより, このグラフにサイクルができないようにしたい(つまり x0 -> x1 -> ... -> xm ->…

AtCoder Regular Contest 060 F - 最良表現 / Best Representation

問題 arc060.contest.atcoder.jp 解法 n = |w| とします。全て同じ文字で構成されている場合答えが n 1 となること, および w が良い文字列である場合答えが 1 1 になることは明らかです。その他の場合は最良表現が 2 になることが分かるようです。よって, …

AtCoder Regular Contest 060 D - 桁和 / Digit Sum

問題 arc060.contest.atcoder.jp 解法 本番はよくわからない解法で通したのですが, そちらも紹介したいと思います。ある数 n に対して b を決めると, 次のような規則性があることに気付きます。n/2+1 から n までは f(n/2+1, n) から始まって 1 ずつ f(b, n)…

AtCoder Regular Contest 060 E - 高橋君とホテル / Tak and Hotels

なんだかんだ 3 完できてうれぴー。 問題 arc060.contest.atcoder.jp 解法 クエリでは a 戦略としては, 「その日にたどり着けるところまでなるべく遠くへ行く」というのが明らかに最適です。ということで, nxt[0][i] = (頂点 i からなるべく遠くへ行こうとし…

AtCoder Grand Contest 003

問題 agc003.contest.atcoder.jp 解法 全ての数が異なるので, ソートされた後それぞれの数がどこに移動するかが決まっている, ということと, 操作 2 が「偶数番目のみ, 奇数番目のみを入れ替えることができる」ということに対応している, ということがポイン…

yukicoder No.417 チューリップバブル

O(NM^2) だと結構厳しめの制約だと思ってだいぶ悩んでいた。 問題 No.417 チューリップバブル - yukicoder 解法 O(NM^2) の木 dp をします。まず考察ですが, 最後に頂点 0 に戻ってこなければならないことから, v -> u と辺を降りた場合, 再び u -> v と戻っ…

yukicoder No.416 旅行会社

問題 No.416 旅行会社 - yukicoder 解法 クエリを逆に読んでデータ構造をマージする一般的なテクを使えば解けます。まず消される辺についてはすべて消されてる状態にします。この際 0 と連結な頂点は答えが -1 です。で, クエリの後ろの辺から辺を追加してい…

SRM 565 div1 med TheDivisionGame

med にしてはかなり簡単ですね。復帰戦だったのでちょうど良いけど。 問題 TopCoder Statistics - Problem StatementU さんと K さんがゲームをする。ゲームは S = {L, L+1, ..., R-1, R} という数の集合を使って行う。そして, 集合 S の中から何らかの数 X …

SRM 565 div1 easy MonstersValley

院試が終わりました。受かったらそれについてもなんか書きます。 問題 TopCoder Statistics - Problem Statement0 ~ N-1 番までの商品を順番に買っていく。それぞれの商品には値段と重さがあり, 値段は 1 か 2 である。 あなたは, 今までに買った商品の重さ…

AtCoder Regular Contest 059 F - バイナリハック / Unhappy Hacking

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えます。dp[n][m][now] = (すでに n 回キーを押したときに, 目標の文字列と m 番目までは一致していて, 生成されている文字は now 個であるような場合の数) という dp をします。これは各状態で 0 を…

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

問題 arc059.contest.atcoder.jp 解法 まず部分点解法を考えてみますと, dp[i][rest] = (i 番目まで考えた時点でべき乗する数が C から rest まで減っているような時の和) というのを考えると, この i 番目でべき乗する数をいくつ使うかで場合分けして A[i]^…

AOJ 2638 Hyperrectangle

AOJ

問題 Hyperrectangle | Aizu Online Judge 解法 まず, このページを見ると d 次元の立体における体積の求め方が分かります。各辺の長さが 1 の三角錐(?) の体積は 1/d! なんですね。 単体 (数学) - Wikipediaで, 後は包除原理です。例えば 各辺の長さが {2, …

AOJ 2538 Stack Maze

AOJ

問題 Stack Maze | Aizu Online JudgeH*W の迷路が与えられる。この迷路には小文字のアルファベットで表される宝石と, 大文字のアルファベットで表されるそれに対応する宝石を埋め込む穴がある(例えば 'a' とそれに対応する 'A' がある, という感じ)。あなた…

AOJ 2296 Quest of Merchant

AOJ

Merchant, かわいい(小並感) 問題 Quest of Merchant | Aizu Online Judge 解法 すごく複雑そうな問題に見えますが, 落ち着いて問題を分解すると一個一個は大したことありません。まず, 1 回の出張で訪れる町の集合がわかったら, その町の集合へ訪れる最短時…

AOJ 2168 Luigi's Tavern

AOJ

問題 Luigi's Tavern | Aizu Online JudgeH 人の勇者, W 人の戦士, C 人の僧侶, M 人の魔法使いがいる。以下の条件を満たすパーティは最大いくつ作れるか。 パーティには必ず勇者がいなければならない。 同じパーティの勇者と戦士は仲良くなければならない。…

yukicoder No.409 ダイエット

この問題実は btk さんから相談をもらっていたんですけど時間内に解けなかった…(主に蟻本を探していた) 問題 No.409 ダイエット - yukicoder 解法 dp[i] = (i 日目に最後にドーナツを食べる際の最小体重)とします。この発想の時点で結構頭良い気がします(こ…

yukicoder No.408 五輪ピック

問題 No.408 五輪ピック - yukicoder 解法 「頂点 1 からの距離が 2 の頂点 a, b が辺でつながっていたら, 1 -> c -> a -> b -> d -> 1 みたいな感じでループにならない?」っていうのが基本的な発想です。つまり, 各頂点について「1 からの距離が 2 になり…

AOJ 2305 Beautiful Currency

AOJ

問題 Beautiful Currency | Aizu Online Judge要素数 n の数列 a が beautiful であるとは, 1 以上 n-1 以下の任意の i について, a[i+1] % a[i] == 0 となることである。数列 a のいくつかの数を入れ替えて, a を beautiful にしたい。a[i] の値を b[i] に…

AOJ 2326 Number Sorting

AOJ

問題 Number Sorting | Aizu Online Judge 解法 dp[i] = (A+i 番目の数字から始まる数列の数) とします。B-A 例えば 792 という数字の次に来るものを考えると, 8**, 9** となるもの i.e. [800, 1000) 79* となるもの i.e. [793, 800) というように, 各桁を 1…

SRM 562 div1 med CheckerFreeness

問題 TopCoder Statistics - Problem Statement白い頂点と黒い頂点が与えられる。白い頂点からなる線分と黒い頂点からなる線分で, 交差するものは存在するか。 解法 実は, 線分が交差する場合, 白い頂点の線分か黒い頂点の線分のいずれかはその凸包のいずれ…

SRM 562 div1 easy PastingPaintingDivOne

問題 TopCoder Statistics - Problem Statementクリップボードが与えられる。これは H*W 個のセルがあり, それぞれのセルは透明か RGB いずれかの色をしている。このクリップボードを, 左上が(0, 0), (1, 1), ..., (T-1, T-1) になるように (0, 0) が一番下…

AtCoder Grand Contest 002 D - Stamp Rally

問題 agc002.contest.atcoder.jp 解法 クエリが 1 個の場合を考えると, UnionFind を使うことで O((N+M)logM) ぐらいで答えを求めることができます(単体だけを考えたら O(N+M) でできそうだけどそれは今はいいです)。というのは, ok(m) = (辺の id が m の部…

SRM 561 CirclesGame

問題 TopCoder Statistics - Problem StatementAlice と Bob がゲームをする。ゲームは交差しないいくつかの円が書かれた平面上で行う。 まだ円内に赤点がない円を選ぶ。 その円内に赤点をいれる。 赤点を入れることができないほうが負け。 両者が最適に動い…

SRM 561 div1 easy ICPCBalloons

問題文長すぎな。 問題 TopCoder Statistics - Problem StatementN 種類のボールがある。これらは以下のような特徴がある。 大きさが決まっている(medium と large の 2 種類がある) 種類ごとにいくつあるか決まっている 種類ごとに色が異なることは保証され…

yukicoder No.404 部分門松列

問題 No.404 部分門松列 - yukicoder 解法 とりあえず配列 A は座圧しておきます。そうすると, 各 A[i] を真ん中とする門松列の数は, 基本的には (i より左側にある A[i] より小さい値の数) * (i より右側にある A[i] より小さい値の数) (i より左側にある A…

AtCoder Regular Contest 058 E - 和風いろはちゃん / Iroha and Haiku

問題 arc058.contest.atcoder.jp 解法 余事象を考えます。つまり, 「XYZ が含まれない数列の数」を求めることを目的にします。これを dp で解くことを考えましょう。状態として, 直前の X+Y+Z 個の数字を持っておけば良いのはわかりますが, これだと 10^(X+Y…