問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0353 解法 とりあえず観察しないとよくわからない。 僕は観察してもよくわからなかったので、確実に言えることを探すことにした。 まず、一番小さい数は、左端に到達したら以降はもう動か…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0323 解法 二分探索するとよい。 海岸からの距離を y とすると、半円 i との交点の x 座標は、x[i] ± sqrt(r[i] * r[i] - y * y) となる。 これを区間と見て、すべての半円に対応する区間…

問題文 http://codeforces.com/contest/570/problem/E 解法 前と後ろの状態を同時に持たないことにはどうしようもなさそうだが、愚直に持つとオーダーが悪い。 よく考えると、現状態から i ステップ後の位置は、列か行の位置のどちらか一方を持てばもう一方…

問題文 http://codeforces.com/contest/570/problem/D 解法 部分木の特定の高さのノードだけ取り出すのもオイラーツアーでできる。 この場合は高さごとにノードを管理すればよい。 各ノードが持つ区間は普通のオイラーツアーと同じで、各高さごとに持つデー…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1383 解法 始点および終点からの最短路を求めておく。それぞれ from_s, from_t とする。次に s-t 最短路グラフを作る。このとき、グラフには s から t へ行くのに必要になるかもしれない辺…

問題文 http://codeforces.com/contest/555/problem/E 解法 二重辺連結成分分解をしてくださいと書いてあるので、先にやっておく。 ただし、与えられるグラフは単純グラフとは限らないので、多重辺にも対応しておく。 するとグラフは森になるので、結局木の…

問題文 http://codeforces.com/contest/553/problem/D 解法 二分探索して BFS で解ける。 最大化したい値を例えば仮に x とおく。 最初、使える集合 S には k 頂点以外のすべての頂点を入れておく。 queue には使えなくなった頂点（初期は k 頂点）を入れる…

はじめに JAG夏合宿2018の参加記です。今年が初参加だったのですが、結構濃密な3日間だったので参加してよかったです。3日間とも、ICPCのときのチーム Zerokan_Sunshine (@nakano, @kazuma, @suibaka) で出ました。 Day1 当日会場まで 原宿からオリセンまで…