2020-04-09から1日間の記事一覧
AtCoder
AtCoder300点
AGC-A
場合分け
最適化テク:探索候補を絞る
最適化テク:解を変形していく(最適性を失わずに)
最適化テク:端点のみを考える
2回やる意味はない
茶色diff
丁寧に簡潔に 問題へのリンク 問題概要 合計で グラム買いたい。 0.25 グラフで 円のセット 0.5 グラムで 円のセット 1 グラムで 円のセット 2 グラムで 円のセット がある。これらのセットを組み合わせて グラム買うための最小金額を求めよ。 考えたこと 0.…
AtCoder
AtCoder200点
AGC-A
パリティ
「選ぶ」と「選ばない」の一対一対応
数え上げ問題
Greedy:各要素について独立に考えてよい
部分和
二項係数
式変形
コーナーケース
緑色diff
これ、知らなくても解ける制約設定だけど、結構大変やね 問題へのリンク 問題概要 個の正の整数 が与えられる。これらからいくつか選ぶ方法のうち、総和を 2 で割ったあまりが となる方法が何通りあるかを求めよ。 制約 考えたこと 一般に 総和が奇数 ⇔ 和の…
AtCoder
AGC-A
文字列
AtCoder300点
最適化テク:自明な上界が最適解
ランレングス圧縮
操作
最小回数・最小個数を求める
操作:2つのものを1つにマージ
緑色diff
最適化問題
一瞬コーナーケースがないかと怖くなる 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対し、以下の操作を好きな回数だけ行うことができる。文字列を「単一の文字からなる状態」にするのに必要な操作回数の最小値を求めよ。 文字列の各…