けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AUPC

AOJ 3048 Averaging (AUPC 2018 day2-J)

二乗の木 DP の例題として、すごくいい感じ!!! 問題へのリンク 問題概要 頂点のツリーが与えられて、各頂点 には 人がいる。いま、人を移動させて、各頂点の人数の最大値と最小値との差が 1 になるようにしたい。 1 人が辺 1 個分を移動するのに必要なコ…

AOJ 3047 Shiritori (AUPC 2018 day3 I)

これはコンテスト本番にて、すぐに解けてよかった 問題へのリンク 問題概要 個の単語 (いずれも英小文字) が与えられる。これらの単語の列が極大しりとりであると は、 しりとりである しりとりの最後尾に続けられる単語がもう残っていない ようなものを指す…

AOJ 3044 Timing (AUPC 2018 day3 F)

整数の三分探索は闇... 問題へのリンク 問題概要 頂点 辺の無向グラフが与えられる。時刻 0 に頂点 を出発し、頂点 まで移動するのに要する最小時間を求めよ。 各辺にはパラメータ が設定されていて、時刻 にその辺の片側の頂点から出発した場合、もう片側の…

AOJ 3045 Painting (ACPC 2018 day2 G)

コンテスト本番、つたじぇーが頑張って通してくれた!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。初期状態では の要素は全て 0 である。加えて、 個の整数のペア()が与えられる。各ペアに対し以下の操作を行い、最終的な数列 を出力せよ。 各 …

AOJ 2895 回文部分列 (AUPC 2018 day3 G)

すごく大好きな問題! 部分列を走査する考え方をちゃんとわかっていれば自然に解くことができる。 問題へのリンク 問題概要 文字列 が与えられる。 の部分文字列のうち回文となっているものが何通りあるか、1000000007 で割ったあまりで求めよ。 制約 は英小…

AOJ 2894 01 文字列と窓 (AUPC 2018 day3 F)

丁寧に考えれば解ける感じ 問題へのリンク 問題概要 0 と 1 のみかならなる長さ N のビット列 S, T が与えられる。S に以下の操作を好きな回数だけ行って T にするのに必要な最小回数を求めよ。 (というクエリが Q 回投げられる) S の最も右にある 1 を含む…

AOJ 2893 均衡な辺削除 (AUPC 2018 day3 E)

あの激熱展開を繰り広げた会津合宿北大セットの E 問題。 「橋以外を壊した方がいいケースもある」ということに終盤間際で気づいてからの、残り 14 秒で通せたのは感動した!!!!!!! こたつがめさん・シンヤカトーありがとーーー コンテストでは、「二…

AOJ 2892 しりとり圧縮 (AUPC 2018 day3 D)

迷走しないようにしたい問題。 問題へのリンク 問題概要 banana at tomb but tos sound does some のようなしりとりが与えられる。同じ文字で始まるところは 1 つにつぶすことができる。上の例で言えば (banana at tomb but) (tos) (sound does some) という…

AOJ 2891 な◯りカット (AUPC 2018 day3 C)

なもりなもり。サイクルが 1 個だけある連結グラフ、すなわち「木」に辺を 1 個くわえてできるグラフのことなん。 問題へのリンク 問題概要 N 頂点のなもりグラフが与えられる。以下の Q 個のクエリに答えよ。 2 頂点 a, b の間を分断するのに最小何個の辺を…

AOJ 2890 ピボット (AUPC 2018 day3 B)

ぐへへへ...ლ(´ڡ`ლ)グェッヘッヘッ 勉強になった。 問題へのリンク 問題概要 1 〜N の順列 a1, a2, ..., aN が与えられる。 この順列に対して Q 個のクエリが順に与えられる。i 番目のクエリでは次の操作をしなければならない: 値 q が与えられる。順列 {a1, a2,…,…

AOJ 1523 Cone Cut

3 次元幾何の練習 問題へのリンク 問題概要 円錐を平面によって切断するとき、分離された2つの部分の体積を求めよ。 解法 ちょっと複雑だが、2次元に射影して考える。 そのためには、3次元幾何の正射影が必要になる #include <iostream> #include <vector> #include <cmath> #include <iomanip></iomanip></cmath></vector></iostream>…