とてもややこしくてハマってしまった......。とても教育的な Greedy 問題。 問題へのリンク 問題概要 個の商品がベルトコンベアで運ばれてくる。 番目の商品は、時刻 から時刻 の間 (両端含む) に点字できる。 点字マシンは 1 秒あたり 1 個の商品にしか点字…

伝説の誤差問題！！ 誤差について学べる、とても教育的な問題。 問題へのリンク 問題概要 人がコイントスをしました。各人には と番号がついています。 人目は、 回表が出て、 回裏が出ました。 人目のコイントスの成功率は と定義されます。 人 の番号を、…

めっちゃいい Greedy 問題だった！！ 問題へのリンク 問題概要 個の商品があり、 番目の商品は、一般客は 円で購入でき、MMA 部員は 円で購入できる。なお、MMA 部員が一般客と比べて得できる商品もあれ得て、損する商品もあり得る。 人がいて、 人目は「一…

めっちゃ面白い問題だった！ Suffix Array の練習問題。 問題へのリンク 問題概要 英小文字からなる長さ の文字列 が与えられる。 の suffix は空文字列を除いて 個ある。これらの suffix を適切な順序で連結させて 1 つの文字列を作るとき、それが辞書順最…

すごくシンプルな面白い問題。 問題へのリンク 問題概要 個の文字列 が与えられる。 これらを並び替えて連結して 1 つの文字列を作る。作れる文字列のうち、辞書順最小のものを求めよ。 制約 解法 単純に を辞書順にソートして、小さい順に連結するのでは反…

ペア の大きい順にソートする嘘貪欲にハマってしまった方が多そうだった 問題へのリンク 問題概要 青木君と高橋君が選挙を行う。 個の町があり、 番目の町では 青木派が 人いる 高橋派が 人いる ということがわかっている。高橋君はいくつかの町で選挙活動を…

めちゃくちゃ面白かった 問題へのリンク 問題概要 この問題では、"(", ")", "[", "]" からなる文字列を考える。 文字列 は，以下のいずれかの条件を満たすとき、良い括弧列と呼ぶ。 は空文字列である ある良い括弧列 が存在し、"(", , ")" をこの順に連結す…

探索順序を上手に決めると、普通の DP になる系！！！ EDPC の Zubton なんかもそうやね！ 問題へのリンク 問題概要 個の正の整数 が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。 各 に対して、 の index が に移動するとき…

いわゆる、「必要条件を列挙したら十分条件になっている」というタイプの教育的な Greedy 問題ですね。 問題へのリンク 問題概要 個の仕事があって、仕事 は、 の時間を要し、時刻 までに終わらなければならない。 時刻 0 に仕事を開始する。 個の仕事をすべ…

学び多き問題。 僕にとっては後半のデータ構造パートが苦戦を強いられ、本当に勉強になった！ 問題へのリンク 問題概要 個の寿司があって、それぞれネタ と美味しさ をもっている。この中から 個の寿司を選びたい。選んだ寿司集合のスコアは 選んだ寿司の美…

結構好き！ソートすることが本質の問題としていい感じな気がする。 問題へのリンク 問題概要 下図のような「中央の通路とそこから横に伸びた乗り物に乗客がどこにいるかを表した地図」が与えられる。乗客は 人いる。各乗客は 1 秒かけて 1 マス移動できる。…