second best を管理する
AtCoder
ABC-C
灰色diff
バケット
for文
ソート
second best を管理する
AtCoder250点
ソート:比較関数を設計する
ソート:ソート後のindexを求める
【問題集】ソート
バケットを使ってもいいし、set や map を使ってもいいかもしれない 問題へのリンク 問題概要 が 3 回ずつ表れる長さ の数列 が与えられる。 を「数列 において 2 回目にその値が登場する index」が小さい順にソートせよ。 制約 考察:まず問題を掴む 最初の…
JOI
JOIG
JOI難易度6
順列の最適化問題
条件の言い換え
絶対値やminを扱う問題
式変形
コーナーケース
二値パラメータ問題
Greedy
最適化テク:最適解の形を考える
ある量を固定して考える
最小コスト
数列
変数変換して扱いやすい同型な問題を見出す
探索順序を工夫して解く
前処理
second best を管理する
後ろから解く
まずソートして考える
ソート:前処理
最適化問題
面白かった! ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
AtCoder
AtCoder900点
構築
探索順序を工夫して解く
最大値や最小値に着目する
木
Union-Find
必要条件を列挙したら十分条件になる
Greedy:端から順に決まっていく
Greedy
二部グラフ
パリティ
黄色diff
ARC-like
second best を管理する
実装に精彩を欠いてしまった...コンテスト中に WA を取りきれず... WA の原因は「すでに色を決めたはずの頂点について再度色を上書きしていることがある (現在見ている D 値について、それより小さい値の頂点とはつながっておらず、等しい D 値同士で結ばれ…
AtCoder
AtCoder300点
ABC-C
バケット
最頻値に関する問題
数列
最適化テク:最適解の形を考える
コーナーケース
緑色diff
ARC-C
second best を管理する
for文
最小回数・最小個数を求める
操作
操作:1文字を変更する
集計処理
最適化問題
意外と罠にはまりやすい問題かもしれない!!! この手の問題は「最適解の形を考える」という意識で解くと良さそう。 そして、コーナーケースがサンプルにあるのが親切。 問題へのリンク 問題概要 長さ ( は偶数) の数列 が /\/\/\/ であるとは 任意の に対…