1ミスしたけど割とよい順位でした。
https://csacademy.com/contest/round-26/#task/build-the-towers
問題
0だけで埋められたN要素の数列がある。
数列中0の要素を1つ任意に選択する、という処理を任意回数行える。
要素を選択すると、0は以下の通りに変化する。
- 隣接要素に1がなければ1になる。
- 隣接要素に1があるが2がなければ2になる。その際隣接する1は0になる。
- 隣接要素に1と2あれば3になる。その際隣接要素は0になる。
N要素の数列が与えられるので、上記処理を繰り返し入力の数列を生成するための手順を答えよ。
解法
処理の内容から、1,2,3のそれぞれを構築するのに必要な条件を考える。
大きな数字を作る方が難しいので、先に大きな数字を作り、あとで小さな数字を作るとする。
まず以下は容易にわかる。
- 0以外の要素で同じ要素が連続するものを作ることはできない。
- それ以外の場合、1は任意に作成できる(両隣が0,2,3のいずれかの状態でその要素を選択すればよい)
- 2は両隣のいずれかが1以下の要素を生成すればよいなら生成可能。
まず3を作ることを考える。
3を作るには両隣に1,2を作る必要がある。
1は容易に作成できるが、2を作るには3の隣に2要素の空きが必要である。
よって、まず目的の数列を探索し、2要素以上連続で3以外の数値がある箇所があるか判定する。
それがないなら2を生成できないので条件を満たせない。
条件を満たす場合、*3**という状態を作るためには、0000→1000→1001→1020→0300とすれば他の要素を0としたまま3を生成できる。
あとは遠い順に3を生成しよう。
次に2を生成する。その際、両隣のいずれかに1以下でよい要素があれば、そこに一旦1を作って、本来の目的の2を作ることができる。
最後に1を生成して終了。
int N; int A[101010]; vector<int> res; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>A[i]; FOR(i,N-1) if(A[i]==A[i+1] && A[i]!=0) return _P("-1\n"); if(A[0]==3 || A[N-1]==3) return _P("-1\n"); if(*max_element(A,A+N)==3) { FOR(i,N-1) if(A[i]!=3 && A[i+1]!=3) { FOR(j,i) if(A[j]==3) { res.push_back(j-1); res.push_back(j+2); res.push_back(j+1); res.push_back(j); } for(j=N-1;j>i;j--) if(A[j]==3) { res.push_back(j+1); res.push_back(j-2); res.push_back(j-1); res.push_back(j); } break; } if(i==N-1) return _P("-1\n"); } FOR(i,N) if(A[i]==2) { if(i&&A[i-1]<=1) { res.push_back(i-1); res.push_back(i); } else if(i<N-1&& A[i+1]<=1){ res.push_back(i+1); res.push_back(i); } else return _P("-1\n"); } FOR(i,N) if(A[i]==1) res.push_back(i); _P("%d\n",res.size()); FOR(i,res.size()) _P("%d%c",res[i]+1,(i==res.size()-1)?'\n':' '); }
まとめ
なんか変わった問題。