AtCoder Beginner Contest #038 (Nim-langの練習帳)
いつも通り、Nim-langでABCに出た
Nim-lang: index - Nim Programming Language
Nim-lang Tutorial: Nim Tutorial (Part I)
Nim Standard Library: Nim Standard Library
- 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部)らしい。
