【本記事の想定する読者】
本問題が解けなくてつらくなっている昨日の私
【問題概要】
長さ n の数列が与えられる。以下の条件を満たすように、各要素を色１、色２のどちらかに塗ることができるか？できるなら一例を挙げよ。
・同じ色の要素の順番は入れ替えずに、色２で塗られた要素が色１で塗られた要素の右側に来るように並び替えると、数列は全体として非減少数列になる。
【制約】
テストケースの数 t について 1 ≦ t ≦ 10,000
テストケース全体を合わせて、数列の長さ n について t ≦ n ≦ 200,000
【最終的な方針】
境界 d∈[0,10)について全探索する。計算量はO(d|s|)。
【最終的な方針へ辿り着くまでの道筋と実装の注意】
やりたいことはわかるがイマイチ実装が思いつかない。できそうでできない問題っぽい...。こういう時は、条件をできるだけ定式化してみる。
与えられた数列のうち、色１で塗るものを a0,a1,...,alast とし、色２で塗るものをb0,b1,...,br としてみると、（色１の要素）（色２の要素）のように並べ替えた数列が非減少数列であるとは以下の条件を満たすことと同値である。i の普遍集合は整数とする。
・∀i ∈[0,last), ai ≦ ai+1
・∀i ∈[0,r), bi ≦ bi+1
・alast ≦ b0
数列に出てくる数がいずれも一桁であることと、三つ目の条件に注目すると、alast ≦ d ≦ b0 なる d が[0, 10)の範囲にしかないことがわかるので、あとはこの d に対して条件を満たす数列を構築できるか判定できればよいということになる。その判定方法のイメージは下の画像のように、与えられた数列を、[0, d]の範囲の数だけを含むようなaiと[d, 10)の範囲の数だけを含むようなbiに分離することである。
実装方法は提出コードを参考にしてほしいが、いろいろ罠があるので注意されたい。具体的には色２で塗る部分を小さい方から見ていき、そのあとに色１で塗る部分を小さい方から見る。その際すでに色２で塗った部分を無視しながらループを進める必要がある。
【提出コード】
#include <bits/stdc++.h> using namespace std; #define repr(i,a,b) for(int i=a;i<b;i++) #define rep(i,n) for(int i=0;i<n;i++) int main(){ cin.tie(0); ios::sync_with_stdio(false); int t; cin >> t; while(t--){ int n; cin >> n; string s; cin >> s; vector<int> color(n, -1); // left[i]: i 入っている一番左の位置（なければ-1） vector<int> left(10, -1); rep(i, n){ int t=s[i]-'0'; if(left[t]==-1) left[t]=i; } bool nothing=true; rep(d, 10){ if(left[d]==-1) continue; // colorを初期化 rep(i, n) color[i]=-1; // 色２で塗れるものから埋める int pre=d; color[left[d]]=2; repr(i, left[d], n){ int t=s[i]-'0'; if(t>=pre && t>=d){ color[i]=2; pre=t; } } // 色１で塗れるものを埋める pre=0; color[left[0]]=1; repr(i, left[0], n){ int t=s[i]-'0'; if(t>=pre && t<=d && color[i]==-1){ color[i]=1; pre=t; } } // 全て塗れていれば終わり bool ok=true; rep(i, n) if(color[i]==-1) ok=false; if(ok){ rep(i, n) cout << color[i]; cout << '\n'; nothing=false; break; } } if(nothing) cout << "-\n"; } return 0; }
