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

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

2^kコスト

TopCoder SRM 604 D1E PowerOfThree

平衡三進法!!! 問題へのリンク 問題概要 二次元座標平面上で、(0, 0) から出発して へと移動したい。何ステップかの移動を行うことができる。 ステップ目の移動では、上下左右のいずれかの方向を一つ選んで、 だけ移動することができる (いずれかの方向に…

KUPC 2019 C - てんびんばかり

パズルだ!! 問題へのリンク 問題概要 正の整数 が与えられる。 個の正の整数 を用意して、 がそれぞれ 個ずつあるとして それらの足し引きによって までの整数がすべて作れる という条件を満たすような最小の を求めよ。 制約 考えたこと の場合は結構な有…

AtCoder ABC 141 F - Xor Sum 3 (600 点)

Xor Sum シリーズしゃん。典型てんこ盛り!!! XOR は各桁ごとに独立に考えるとよい XOR に関する問題は mod. 2 での方程式みたいになることも多い であることから上位の桁から辞書順的に優先で考えるような貪欲が決まる などなど。 問題へのリンク 問題概…

Codeforces Global Round 2 E - Pavel and Triangles (R1900)

こういう貪欲は確実に抑えて行きたい 問題へのリンク 問題概要 長さが の線分がそれぞれ 本ずつある。 これらから三角形は最大で何個作れるか? 制約 考えたこと 面白そう!!!!! な量を扱う問題リストにまた 1 問加えられる!!!!! この手の問題では…

AtCoder AGC 031 C - Differ by 1 Bit (800 点)

証明はできるし、その証明に基づいた構成を数学的に与えることまではできるけど、それを実装に落とすのがすごく大変な問題。。。 問題へのリンク 問題概要 整数 が与えられます。 の順列 であって、 次の条件をすべて満たすものが存在するかどうか判定してく…

みんなのプロコン 2018 決勝 B - 経路が色々 (800 点)

解説は三進法でやってたけど、二進法でもできた 問題へのリンク 問題概要 次をすべて満たすようなマス目を構成せよ。 マス目の各マスは白か黒で塗られている マス目の縦横の長さをそれぞれ N,M としたとき、N,M は 1 以上 100 以下である 一番左上のマスから…

AtCoder AGC 029 B - Powers of two (600 点)

「交換しても悪化しない」というのは Greedy の証明の共通構造だとは思うん。 問題へのリンク 問題概要 個の正の整数 がある。 これらの 個の整数に対応する 頂点のグラフを考えて、和が の形で表せる 2 数間に辺を引く。 このグラフの最大マッチングを求め…

AtCoder ARC 102 D - All Your Paths are Different Lengths (700 点)

好きだけど細かいところで時間とられるやつなん 問題へのリンク 問題概要 (ARC 102 D / ABC 108 D) 整数 L が与えられる。N 頂点 M 辺の重み付き有向グラフ (頂点番号は 1, 2, ..., N) であって N <= 20 M <= 60 任意の辺 (u, v) について u < v でなければ…