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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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