最小コスト
for 文のループカウンタ が偶数か奇数かに応じて処理を変える問題！ 問題へのリンク 問題概要 長さが奇数 の文字列 が与えられる。 この文字列に対して、次の操作をすることで、"IOIOIO...OI" というように "I" と "O" を繰り返す文字列にしたい。操作回数の…
整数の切り上げの問題。意外と正確に解くのは大変かもしれない。 問題へのリンク 問題概要 ベースとなるアイスクリームの金額は 250 円で、高さは cm である。追加のアイスクリームは 1 個につき 100 円で、1 個追加するごとにアイスクリームタワーの高さが …
面白い問題！ 問題へのリンク 問題概要 箱 とボール がある。ボール は箱 に入っていて、その重さは である。 これから、ボールの入っている箱を移すことで、どの箱にもちょうど 1 個ずつボールが入っている状態にしたい。ボールを移すコストは、そのボール…
めっちゃ面白い問題！！ 実はよく似た類題として次の問題がある！ atcoder.jp 問題へのリンク 問題概要 長さが の数列 が与えられる。この数列から 個の要素を削除する。 残った数からなる数列中の、最大値と最小値の差の最小値を求めよ。 制約 考えたこと …
平面走査の典型問題だけど、とにかく重くて辛かったのと、コーナーケースになかなか気づけなかった。 問題へのリンク 問題概要 数直線上に 個の区間がある。区間 は である ()。 = 区間 が、与えられた 個の区間のうち何個と交差するか としたときに、 の範…
ちょっと頭を使う系の問題。この時期の ABC-A にはこういうものが多かったね。 問題へのリンク 問題概要 りんごをちょうど 個買いたい 円払って 個買う 円払って 個買う のいずれかによって、ちょうど 個買うための最小コストを求めよ。 解法 以下のいずれか…
現実世界っぽい題材を扱ったちょっと楽しい問題。 問題へのリンク 問題概要 チーム A とチーム B が野球対戦をし、9 回表まで終了していて、 (チーム A の得点) ≧ (チーム B の得点) となっている。チーム B が 9 回裏で勝利するのに必要な最小追加点を求め…
久しぶりの易しい問題！ 問題へのリンク 問題概要 電車を使うと 1 人あたり 円かかります。 タクシーを使うと 人で 円かかります。 人で移動する最小料金はいくらか。 解法 A * N B のうちの小さい方を答えれば OK。関数 min() が使える。 #include <bits/stdc++.h> using n</bits/stdc++.h>…
セグメント木を用いた DP 高速化！ 問題へのリンク editorials 問題概要 'R' と 'G' と 'B' のみからなる長さ の文字列 が与えられる。以下の操作を繰り返し行うことで、"RGB" を繰り返す文字列となるようにしたい。 (操作) 連続する 個以下の文字を消す 目…
この問題は意味を理解するのが大変だと思う！ 問題へのリンク 問題概要 3 つの整数 が与えられる。これらを適切に並び替えたときの 1 番目と 2 番目の差 2 番目と 3 番目の差 の和として、考えられる最小値を求めよ。 解法 実際に幾つかのケースで手を動かし…
2 変数劣モジュラ関数の和の最小化を最小カットにするやつ！ 問題へのリンク 問題概要 種類のスキルがある。それぞれ初期状態のスキルレベルは 1 であるが、最大で 5 まで上げられる。スキル のスキルレベルを 1 上げるのに必要なコストは 円である。 種類の…
実は DP の添字の取りうる範囲が log オーダーであることを見抜く問題。より高度な問題でもしばしば見られる考え方。 問題へのリンク 問題概要 二次元平面上に点 がある。点 の座標は である。 今、点 1 にいて、原則として点 を順に通過して最終的に点 に到…
個の区間を、プチ区間たちを用いて、最小コストですべて被覆しようという問題。DP 状態の持ち方を工夫することで計算量を小さくしたい。 問題へのリンク 問題概要 個の区間があって、長さが である。これらすべてを 2 種類の区間で被覆したい。 長さが であ…
少し頂点を増やす感じの Dijkstra 法。とても教育的な典型問題！ 問題へのリンク 問題概要 頂点数 の完全グラフが与えられる。頂点 1 から頂点 へと到達したい。途中までは社用車を使い、途中からは電車を使うことができる。電車から社用車に乗り換えること…
セグ木上で DP する問題として、人生で最初に解くべき問題と言えるかもしれない！ 問題へのリンク 問題概要 個の区間がある。各区間 は、 で重みは である。 これらの区間からいくつか選ぶ方法のうち、 全体を被覆するものについて、最小重みを求めよ。 制約…
「平均値の最小化」に基づく二分探索 + 最小全域問題 問題へのリンク 問題概要 (意訳) 頂点数 、辺数 の重み付き単純無向グラフが与えられる。各辺 は、重みが であり、長さが である。 グラフの辺集合のうち、すべての頂点を連結にするものを考える。そのよ…
chokudai さんの思想が詰まった問題 問題へのリンク 問題概要 個の開発案がある。これらの開発案によって上昇し得るパラメータが 種類ある。 開発案 () を採用すると、パラメータ () の値が だけ上昇する。その分、 のコストがかかる。 すべてのパラメータを…
少し重たかった。でもいい問題。JOI にありそう。 問題へのリンク 問題概要 数直線上に 箇所の燃料補給所がある。 番目の補給所は次のようになっている。 座標 にある 補給すると、現在の HP が であるとき、HP が になる (コストとして を支払う) 今、高橋…
二重辺連結成分分解とか low-link とか色々考えたけど、結果的に最後は「ただ DFS 木を作るだけ」になるという、すごく印象的な問題！ 問題へのリンク 問題概要 以上 以下の整数からなるサイズ の 2 つの数列 、 が与えられる。 今、0 と 1 のみからなるサイ…
区間分割をしていく DP として、一番最初に解くべき問題を意図して作った！！ けんちょん本の 3 例題 (ナップサック問題、編集距離、これ) の 1 つでもある。 問題へのリンク 問題概要 個の要素が一列に並んでいる。これら 個の要素に対して、区間 のコスト…
本当に三分探索で通るのね！ これらの問題を思い出した drken1215.hatenablog.com drken1215.hatenablog.com 問題へのリンク 問題概要 二次元平面上に 本の線分がある。この平面上の円盤 (円周と内部を含む) のうち、 本の線分すべてと共有点をもつようなも…
最近話題の Functional Graph の問題！ 問題へのリンク 問題概要 人 がいる。各人 には 1 人ずつ嫌いな人 がいる。 今、彼らに順番にキャンディーを配る。ただし、各 について、もし人 よりも先に にキャンディーを配ると、不満度が だけ加算される。 キャン…
opt さん、とよさんと一緒に解いた。楽しかった！ 問題へのリンク 問題概要 数列 に対して、最大 回の操作を繰り返すことで順列 を作りたい。 回目の操作では、値 ( 以上 以下) を選ぶと、コスト がかかる 値 を選んだとき、数列の末尾 を取り出して、順番を…
問題の入力変数が多いので、読み解くのが大変かもしれないですね。 問題へのリンク 問題概要 AtCoder ドリンクは定価である 円を払えば飲むことができます。 また、割引券を持っており、それを使うと AtCoder ドリンクを定価より安い価格である 円で飲むこと…
ランレングス圧縮をする問題に一瞬見えるかもしれない。でもそんなことしないで、最初から最後まで綺麗に DP で殴れる！ 問題へのリンク 問題概要 文字 'a' と 'A' のみからなる長さ の文字列 が与えられる。 以下のキーボード操作を繰り返すことで、この文…
木上で bit DP する感じ 問題へのリンク 問題概要 頂点数 の根付き木が与えられる。各頂点 には重み が付されている。 この根付き木はタスクの依存関係を表している。各頂点に対して、対応するタスクの「実行」と「削除」ができる。 頂点 のタスクを実行する…
慣れれば解ける問題だけど、最初は「固定する」という考え方が難しいかもしれない。 問題へのリンク 問題概要 長さ の文字列 が与えられる。この文字列に対して、次の操作を繰り返すことで回文にしたい。 先頭の文字を末尾に移動する (コスト ) 文字を 1 つ…
面白かった！ ジャッジページ 問題文 問題概要 人の走者がいる。 人の中から 人を選んで、100m 走る × 3 の 300m リレーを行う。 人目の 100m 走のタイムは 秒、バトンパスタイムは 秒で与えられる。リレーの走者として、 の 人を選んでこの順に走るときの総…
落ち着いて整理して考えましょう。問題自体は「累積和」が使える良い問題ですね！ 問題へのリンク editorial 問題概要 個の電球を一列に並べていて、オンオフ状態が であるような状態を作りたいとします。ただし は 番目の電球をオンにしたいことを表し、 は…
大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。 問題へのリンク 問題概要 個の風船がそれぞれ初期状態では高度 の位置にあり、1 秒ごとに ずつ上昇する。これらすべての風船を射撃によって割りたい。 競技開始時に 1 個風船…
