読者です 読者をやめる 読者になる 読者になる

n-knuu's logs

憧れ駆動。だいたい競プロ

AtCoder Beginner Contest #038 (Nim-langの練習帳)

segment tree 最長部分増加列 尺取法 AtCoder

いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library

abc038.contest.atcoder.jp

  • A - お茶

末尾がTに等しいかを見るだけ
pythonだとhoge[-1]と書くところをNimではhoge[^1]と書く

  • B - ディスプレイ

全部検査すればOK

  • C - 単調増加

尺取法
単調増加な部分を求めて、その長さをLとすると、答えにL*(L-1)//2を加えていく

  • D - プレゼント

x_i < x_(i+1) かつ y_i < y_(i+1)となる最も長い点列の長さを答える問題。本番では解けなかった。
これは、dp[y_i] := (iまで使ったときの最長の点列) として、dp[y_i] = max{dp[y_j] | x_i < x_j かつ y_i < y_j} + 1 で更新するDPで解けるが、愚直にやるとO(長さ^2)かかるのでダメで、segment treeを使ったDPが必要。詳しい説明は割愛するけども、yの大きい方から調べていくことで、それよりも小さいyのsegment treeの値が0になっていることがポイント。
あと、今回は真に大きいものしか選択できないので、segment treeの更新は高さが同じものを一気に行わないといけない。

もっと楽な方法として、x座標でソートしておくと、y座標の列の最大増加部分列問題に帰着できる。こちらの方がずっと短いし楽。

DみたいなDPは以前codeforcesでも見ていたのに解けなかった
Dの3次元パターンがICPCで出たことがあり(Longest Chain | Aizu Online Judge)、名前のついてない典型テク(skyaozoraの日記 - TopCoder部)らしい。