問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2850 解法 01BFSで解いた。 まず、2部グラフだと永遠に終わらないことはわかる。 2部グラフじゃない場合、どこかのタイミングで隣接2頂点が同時に current に入り、そこからそれらの頂点は…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2847 解法 まず一行目を適当に埋める。次数が 2 の頂点を見つけて、そこから隣接する中で一番小さい次数の頂点をたどっていけば自然に一行埋められる。 一行目が埋まると、下の行の数は一…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2858 解法 区間篩の要領で解ける。 [1, 1e5] ぐらいまでの素数を普通に篩で検出し、素数が見つかれば [L, R] にカウントを割り振っていく。 今回の場合は、素数 p が検出できたら、[L, R] …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2593 解法 辺の長さをまず決め打つと、それぞれの円と交わる部分が区間として求まる。 得られた区間の連結な部分の総長さで、決めうった値よりも長い所があれば、そのような正方形を配置す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1620 解法 前もってすべての式を生成してしまえばOK。 真理値表は 16bit 分の情報があればよく、bitDP 的な要領で生成していけば良い。 つまり、キーが真理値表で、値がその最小長さである…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 解法 自分は数式で捉えて、ラグランジュの未定乗数法で解いた。 ラグランジュの未定乗数法については以下のサイトがわかりやすい（ただし厳密な証明はない）。 mathtrain.jp与えられ…

問題文 http://codeforces.com/contest/566/problem/A 問題概要 n 個の名前と、n 個のペンネームが与えられる。これらを1対1対応させることを考える。 名前 a とペンネーム b をペアにした時の満足度を lcp(a, b) と定義する。 lcp(a, b) の総和が最大となる…

問題文 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 当日会場まで 原宿からオリセンまで…

問題文 http://codeforces.com/contest/551/problem/E 解法 平方分割．まあそれはそうだよね． 実装方法はいろいろありそうだけど，10秒制限が意外と厳しいので，map とか set はできるだけ使わないほうが良い． 各塊は2つ目のクエリに答えるために，(val, i…

問題文 http://codeforces.com/contest/551/problem/D 解法 結論をいうと行列累乗で解ける． まず重要なポイントとして，各ビットは独立に考えて良い（全く同じ条件なので）． つまり，結局この問題は1ビットの問題に帰着される． 1ビットの n 個の整数を，…

問題文 http://codeforces.com/contest/547/problem/C 解法 与えられた値を素因数分解して出てくる素数の数は高々6個しかない． gcd を考えるときはこれだけで十分である． 今回は直接答えを求めず，gcd(a, b) != 1 となる個数を求めて最後にトータルから引…

問題文 解法1 値の大きい方から追加していって，区間やその幅をset, multiset で管理して頑張るだけ． 実装が悲しい感じになる． ソースコード1 #include <bits/stdc++.h> using namespace std; using pii = pair<int, int>; constexpr int inf = 1e9; int main() { int n; cin >> n; </int,></bits/stdc++.h>…

問題文 http://codeforces.com/contest/547/problem/A 解法 mod を取っているので，それぞれ高々 m 回でループするのはすぐわかる． とりあえずそれぞれについて目的の高さになるまで愚直にシミュレートする． この時到達できないならそもそも不可能なので -…

問題文 http://codeforces.com/contest/543/problem/C 解法 n それは，a-z の26文字より小さいので，各文字は1箇所変更するだけで easy to remember にできるということ． つまり，ある文字列 i を easy to remember にするには，以下のどちらかしかない． …

問題文 http://codeforces.com/contest/542/problem/F 解法 DPで解ける． dp[i][j] := 高さ i に存在するノードが j 個であるようなときの，価値の最大値 とする． ある高さ i のときに考えるべきタスクは，実はコストが T - i であるものだけでよい． なぜ…

はじめに 7/6 に行われた ACM-ICPC 2018 国内予選の参加記です． 忘れないうちに書こうと思います． 今年は大雨で関西勢は大変でしたね．自分の大学もリモート参加推奨，という形になってしまいかなりバタバタしていました． 結果 チーム Zerokan_Sunshine …

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2702 解法 後退解析で解く． ゲームの探索なので，最初は始点からDFSしたくなるかもしれないが，普通に状態が自分に戻ってくるような遷移があるので困る． こういうときは確定しているとこ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く． 与えられるグラフはDAGになっていて，この上で2回違う条件で最短経路を求めたい．しかし依存関係にあるので独立にはできない． こういうときは1回目と2回…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける． 左が欠けているやつを考えるときは末尾から比べたいので，各文字を反転した文字列集合も別に持っておく． 与えられた石版に ? がある場合は26文字全通り試す…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽？ union find の各集合がどのクラブに属するかを別に vector で持っておく． a と b が同じ部活に所属している場合，マージするのだが違うクラブに属し…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2693 解法 いかにもな bitDP 感がある． しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える． うまくやれば状態に順列持てたりしないかな～と制約を読むと N -…

問題文 http://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか，という問題． まず，n * m （n, m はただの自然数）のような表現は完全に不利． 例えば 99 * 99 を考えてみるとわかりやすいが，そのまま出力したほうが短い…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390 解法 感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう． そして投げたら通った（終了）…だと困るので厳密じゃないけど一応それっぽいのだけ．木なので基地…