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

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

個数のみわかれば遷移が作れるDP

AOJ ???? Watering (AUPC 2020 day3-G)

この問題に似てた drken1215.hatenablog.com 問題へのリンク editorial 問題概要 の順列 を最適化したい。以下の手順にしたがって、各要素 のスコアが定まる。この 個のスコアの最大値の最小値を求めよ。 値が のいずれかであるような数列 ( 項) が与えられ…

AtCoder ABC 163 E - Active Infants (500 点)

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

Codeforces CodeCraft-20 (Div. 2) E. Team Building (R2300)

これは楽しい!!! 順番をうまく決めれば、全部の情報を持たなくても、個数のみの情報に落とせる系。 問題へのリンク 問題概要 要素の数列 と、 の二次元数列 が与えられる。 個の の中から 個を選び、 残りの 個の index の中から 個分、 の行ベクトルを選…

第6回 ドワンゴからの挑戦状 2020 予選 E - Span Covering (1100 点)

すごく面白かった!!!!!!! 問題へのリンク 問題概要 長さ のマス目があって、長さがそれぞれ の 個の区間を配置していきたい。 個の区間がすべてのマスを被覆するような配置方法は何通りあるか、1000000007 で割ったあまりを求めよ。 制約 考えたこと …

AOJ 2630 Dictionary (JAG 夏合宿 2014 day2-B)

最初は「え!? i 行目の文字列情報がないと i+1 行目以降のことを考えられなくない?」となってしまって、途方に暮れてしまった 問題へのリンク 問題概要 個の文字列 があって、それぞれいくつかの文字は '?' で隠されている (したのは の例) '?' 全体をア…

第6回 ドワンゴからの挑戦状 予選 C - Cookie Distribution (800 点)

これ 81 人も通してるのか... 問題へのリンク 問題概要 人の子供がいる。 日間にわたって、 人の中から 人を一様ランダムに選んでクッキーを与える。 日分のあらゆるクッキーの配り方を考えたときの「各子供の最終的にもらったクッキーの個数の積」の総和を…

AOJ 2439 箱根駅伝 (JAG 夏合宿 2012 day3aF)

sky さんの提唱した、代々伝わる名問題!!! 問題へのリンク 問題概要 人の選手が箱根駅伝を走っている。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示される。 ある中継所を 番目に通過したそれぞれの選手について、前…

AtCoder AGC 002 F - Leftmost Ball (1600 点)

すごく楽しかった。 問題へのリンク 問題概要 色 のボールがそれぞれ 個ずつあります。 個のボールを好きな順序で並べ、各色について最も左側にあるボールを色 へと塗り替えました。 最終的な色の並びとして考えられる個数を 1000000007 で割ったあまりを求…

JOI 2019 予選 F - 座席 (AOJ 0657)

挿入 DP。。。TDPC O - 文字列を複雑にした問題。アイディアはシンプルだけど詳細詰めが重たい。。。 問題へのリンク 問題概要 個の正の整数 が与えられる。 が 個 が 個 ... が 個 を合わせた 個の数を並べる方法のうち、どの隣り合う箇所も数値の差が 以上…