2018-10-01から1ヶ月間の記事一覧
人力部門に出ました。 4月 問題が発表される。今年も人力臭がすごい。とりあえず暗号化については深く考える必要がないことがわかった。 すぐに市松模様作戦を思いつくが、のちに却下。 5月 学内審査と予選を適当にかわす。 6月 ビジュアライザを作る。メン…
問題 https://beta.atcoder.jp/contests/agc026/tasks/agc026_d 解法 高さが同じ列のヒストグラムを考えます。 左の列の塗り方が決まっているとき、その塗り方が赤青赤青……のように交互(以下マダラと呼びます)であれば、右の列の塗り方はそれと全く同じに…
全然わからん→解説見よ→意味不明→制約見落としてた→えーん 問題 https://beta.atcoder.jp/contests/arc103/tasks/arc103_d 解法 辺で繋がれたある頂点を考えます。辺を切ったときのそれぞれの連結成分のサイズをとすると、が成り立ちます。ここで、頂点を固…
問題 https://beta.atcoder.jp/contests/arc103/tasks/arc103_c 解法 木が構築可能であるための、次の必要条件が浮かびます。 実はこれらは十分条件でもあります。具体的には、次のようにして構成できます。 頂点間を繋ぐ。 直前に頂点間を繋いでいたとする…
これを通せたおかげで予選通過できました。嬉しい。 問題 https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d 解法 とします。DPをします。ガソリンスタンドまで来るにあたって、ガソリンスタンドで最後に補給す…
問題 https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c 解法 になったら、それ以降はで割らないものとします。そうすると、求める答えは本来の「回の操作後の数列としてありうるものの個数」に「回未満の操作後…