あめんばーどのバーチャル日記

バーチャルな世界で過ごして競プロしてる人の雑談

【AtCoder】F - Two Exams / AtCoder Beginner Contest 238

いやぁ、久しぶりですね。続かないもんだ。VRChatと競プロはちゃんと続けてます。なんならレートちょっと伸び始めててるんるんです。VRが少しおざなり。
いろいろ書きたいって言ってたのになかなかやりたいものが多かったりメンタルブレッブレだったりでわちゃわちゃしております。 特に年末年始はプロジェクトがそのまんま変わったりする時期でもあったんでわっちゃわっちゃしておりましたね…。 どっかの人事さん拾ってくれませんか

前回の記事にも書いていたように書きたい内容はたくさんあったのですが……まぁ思うように自分のやりたいことできませんね。あめんばー2号とあめんばー3号とあめんばー4号欲しい。2号はボルテがんばって3号は競プロ頑張って4号は運動頑張って1号の俺はゲームする。

いつかの黄入記事でも書いた通り「どのようにその考えに至ったのか」を述べるのが苦手であり、できるようになりたいってのがあります。そしてABC238-Fがなんとなく語りやすそうな気がしたのが今回の問題でした。

というわけでざっくりこんな問題。

N個の整数組(P1,Q1),...,(PN,QN)があります。ここからK組を選ぶNCK通りのうち、次の制約を満たすものは何通りあるか998244353で割った余りを答えよ

  • iを選んでいて、Pi>Pj, Qi>Qjを満たすjが存在する場合jは必ず選ぶ
  • 1≦K≦N≦300

解説の通りこの問題はDPです。 ではどうDPに至ったか。というわけで最近私がよくやる考えの癖。

  1. 実装難やTLEを気にしない愚直な解法ならどうなるか考える
    ※それでも難しいなら「問題自体の条件を緩和する」など、とにかく一部のしがらみを無視する
  2. 上記を考えた上でそれが実装できないネックがどこなのかを考える
  3. ではどうすればそれが削れるか、どんな削ぐことのできる性質があるか、どのような解法にそれを消す強みがあるか
  4. 無理そうならもう一周

水色の頃は2番目……制約から考えようとすることが多かったのですが、こちらが後のほうがずっと考えが良くなった気がします。

では最初の段階に入りましょう。実装難やTLE、問題制約が緩和されるならどんなパターンがあるかです。例えばこんな感じでしょうか。

  • NCK通り全部見る
    一番シンプルかつ簡単にTLEとわかるパターンだと思います。
    個人的には高難易度になるほどTLEする考えが最もシンプルに整理しやすいので、見えるものがだいぶ変わる印象です。
  • 有向グラフとしてなんかがんばる
    問題条件から有向グラフができます。そこでなんかいろいろしたらできないのかなぁ。ただABCらしからぬ実装難を感じる。 この段階ではまだ細かいことを考えません。ただ有効グラフの関係性や木DPに似た形を感じたりもします。

この段階じゃさっぱりですね。では次にそこのボトルネック。シンプルですが。

  • 計算量がO(2N)近く
  • 実装が非常に複雑で不明瞭

全然ダメでした。ただここでどうすればそれぞれが削れるかと言う次の段階です。

  • 複数のパスが重なっている有向グラフが完成しているのでなんかそこで頑張って計算量を削る
  • 図で書いてみると絶対に右上から左下への有向パスなのでDAGである

今回は1番目はまぁまぁ論外なのですが、二番目は極めてDPが強いです。DAGというと少し抵抗が出るかもしれませんが、端から順番に決めていっても差支えのないデータ構造かもしれないという点でDPと相性がいいです。

さてDAGの存在と共に二周目に入りましょう。

  • ここまで取得したもの全部ではなく、一番右上（自分より真に大きい組がない）になり得るものだけを保持してDPとか貪欲かなんかする

第二段階。

  • 右上の場所が悪いと結局2N個になり得るし、実装難

悪化していますが、今度は第三段階に対する対抗手段があります

  • 条件が緩和されたらどうなるか考える
    第一段階にも入れていいかも。一変数だったらとても考えるのは楽ですよね。
    ※ 【AtCoder】F - Cleaning Robot / AtCoder Beginner Contest 219 - あめんばーどのバーチャル日記
    「問題の条件を緩和する」という考え方に関してはこの記事とかでも言ってます。

  • 困ったらとりあえずソートするなど、貪欲な順序を導く
    E - Pancakes
    黄入の決め手になったこの問題の以降、もはや信念レベルで順不同ならとりあえずソートして損はないという考えがあります。ソートをしてみると、片方の数字を気にしなくてよくなる取り方ができるという嬉しさを見つけることができたりします。
    ※ D - 25個の整数
    この考え方はこの問題にも通ずるものがありますね。4問時代ABCの赤パフォっていうすごい問題だけど。

  • DPにするなら計算量と添字から考える
    これは経験則の話になりますね。上記計算量解決も踏まえたものになります。
    我流なのですが私は二次元以上のDPを考える時に添え字を使った文章を必ず考えます。今回は三次元までできそうなのでどうするかで考えると。
    「ソートしたi番目までの数字を見て、j個選んでいて、これまで選んだ中の最高数字がk」と日本語で言うと実装もかなり整理できます。
    と言うかもう少し言うと最初は「j個選んでいて」をk個で打ち切ろうとして実装を迷っていたのですが、別の言い方を考えて解決した感じです。間に合うし。
    ※ F - |LIS| = 3
    最近とかだとこれも4次元DPで重いけど、言葉や理論で言えばさくっとできるものでしたからね。デバッグがしづらいしづらい。

int main() {
  ll n, k;
  cin >> n >> k;
  VP pq(n);
  REP(i, n) 
    cin >> pq[i].first;
  REP(i, n) 
    cin >> pq[i].second;
  SORT(pq);
  reverse(all(pq));
 
  vector dp(n + 1, vector(n + 1, vector<mint2>(n + 1, 0)));  // i人目まで決めていて、j人採用していて、qランク最高値がk
  dp[0][0][0] = 1;
  REP(i, n) {
    REP(j, n) {
      REP(k, n + 1) {
        // 採用
        dp[i + 1][j + 1][max(k, pq[i].second)] += dp[i][j][k];
        // 採用しない
        if (k < pq[i].second) 
          dp[i + 1][j][k] += dp[i][j][k];
      }
    }
  }
  mint2 ans = 0;
  REP(i, n + 1) 
    ans += dp[n][k][i];
  cout << ans.val();
  return 0;
}

ここまで書いて過去の「問題を解くための決め手となった考察」が結構出てきたなというのもあり、精進が大事と解釈すると軽く聞こえるかもしれませんが、一問一問に対して何を考えたからこそ解けたのか、何さえ考えたら解けたのかの振り返りが大事かなと。 どんな問題も400点あたりから「学んだアルゴリズムをやるだけ」ではないはずなので、どこがポイントなのかを抑えるのが着々と押さえていきたいですね。

最後にDAG状態でDPって思ったのかというお話と、それに関する過去に私が学んだ大事な考え方を述べておこうかなと。

平たく言ってしまえば、例えば重さを添え字に使ったdpの図ってこんな感じである。図の場合3つの荷物があり、一つ目の重さが2、二つ目の重さが1、三つ目の重さが3。 f:id:amentorimaru:20220217213429p:plain

様々な状態から、入りも出も複数のパスを所持している。見た目がそのままDAGですね。DPがなぜ強いのかと言うと、O(2N)になってしまうような何通りもありえるこのパスの通り方を「一つの状態」にひとまとめにすることができることで、計算量をO(N)に落とし込むことができる。
……という説明を受けた際に、私の解釈として「たくさんのパスが存在するDAGの形だとそんな強いことになるのか」が加わったものになる。ひとまとめにできるのは、循環することのないパスの出し口と受け口とそれをひとまとめにできる「状態」が存在するからである。あと私にDPの説明をしてくれた人がとてもうまかったのである。

そういったただ解き方をだけでなく「なぜその方法で短縮ができるのか」を掴んだら結構考えに繋げるようにできてるんじゃないかなぁと。

この一つ一つの「状態」をまとめるという概念も結構応用性があります。「数値の遷移をステートチャート図として表す」という概念である。これもまた説明が超うまい人がいたおかげです。

※F - Sugoroku2
真っ先に思い浮かんだのがこれの解法1。DAGではありません。
期待値や確率なんかを求める問題でも、「このマスにいる状態」と「パス」の遷移を整理していって、その間にどんな方程式が成り立つのか、というのを考えることになります。 逆に言うとDAGでなくとも「状態とパスの関係」という形で問題を整理すれば連立方程式として問題が整理しやすくなる、といった考え方なのかもしれません。

というわけで今回は解説ではなく「書きなぐり」でした。本番はこのブログじゃなくて「誰かにちゃんと説明をするその時」にちゃんとお話ができますように。終わり。