ちぇ〜ふちぇふちぇふ。21位で入紫！星が4つになりました。普段はかなりスロースターターなんですが、今回は珍しく序盤からかなり冴えており非常にいい調子で5完することができました。嬉しい！ # Find Outside Array $A_i > 0$かつ$\max(A) = A_i$であるような物を2つ足したもの、あるいは$A_i < 0$かつ$\min(A) = A_i$を二つ足したものは元の配列に含まれません(これは簡単に証明できます)。唯一、配列のすべての要素が0である場合は足しても0にしかならないので構成不可能です。よって、これを適当に実装してあげることでこの問題を解くことができます。 ```cpp void solve() { int n; cin >> n; set st; vll a(n); rep(i,n)cin >>a[i], st.insert(a[i]); rep(i,n){ if(st.find(a[i]*2)==st.end()) { cout << a[i] << ' ' << a[i] << '\ '; return; } } cout << "-1\ "; } ``` # **Flip Prefix** Flipが可能なのはprefixに含まれる0, 1の個数が同じ時のみです。ということは、Flipの前後で個数は変わらないので、Flipしても以降のものに影響しません。よって、構成可能な文字列の数は、Flip可能な場所が$k$個であるとすると$2^k$となります。 ```cpp void solve() { int n; cin >> n; string s; cin >> s; int cnt[2] = {0, 0}; ll ans = 1; rep(i,n) { cnt[s[i]-'0']++; if(cnt[0]==cnt[1]) { ans*=2; } } cout << ans << '\ '; } ``` # The Best Matrix これかなり好きです。$A_{1, 1}=0$として実験してみると、右に+1するか-1するか、下に+1するか-1するかでそれぞれ2通り、合計4通りしかあり得ません。よって、それら前計算しておき、「マス$A_{i,j}$を残すとした時に変えなければならない要素の個数」を求める全探索が可能で、全体で$O((NM)^2)$時間でこの問題を解くことができました。 ```cpp void solve() { int n, m;cin>>n>>m; vvll a(n, vll(m)); rep(i,n)rep(j,m) cin >> a[i][j]; vector target(4, vvll(n, vll(m))); ll idx = 0; for(int di: {-1, 1}) { for(int dj: {-1, 1}) { target[idx][0][0] = 0; rep(i, n) rep(j, m) { if(i==0&&j==0) { continue; } if(j == 0) { // 上から target[idx][i][j] = target[idx][i-1][j] + di; } else { target[idx][i][j] = target[idx][i][j-1] + dj; } } idx++; } } ll ans = inf; rep(i,n){ rep(j,m) { rep(k, 4) { ll cnt = 0; rep(ni, n) { rep(nj, m) { if(a[i][j] - a[ni][nj] == target[k][i][j] - target[k][ni][nj]) { } else { cnt++; } } } chmin(ans, cnt); } } } cout << ans << '\ '; } ``` # Tree Colouring(easy) これもかなり好きです。というか、Tree Colouringの本質部分が詰まっていて、これが置いてあったおかげでHardがめちゃくちゃ簡単になったので本当にありがとう。Writerさんありがとう。ちゅっちゅはい。まずは簡単に実験してあげると、同じ色が3つ以上ある場合はgoodではないことがわかります。また、ある辺が最短経路として用いられる回数が**ちょうど**一回となることを満たすためには、同じ色の頂点の親は同じ頂点でなければいけません。頂点0は頂点0を親とする頂点とペアにしなければならないことに注意しつつ、上記のことを実装してあげることでこの問題を解くことができます。 ```cpp void solve() { int n;cin>>n; vll a(n-1); rep(i,n-1)cin>>a[i], a[i]--; vvll cnt(n); rep(i,n-1) { cnt[a[i]].push_back(i+1); } // 0は奇数それ以外は偶数 rep(i,n){ // cerr << i << " " << cnt[i].size() << '\ '; if(!((i==0&&cnt[i].size()%2==1) || (i>0&&cnt[i].size()%2==0))) { cout << "-1\ "; return; } } vll ans(n, 0); ll cur = 1; rep(i,n) { if(i==0) { ans[0] = cur; ans[cnt[0][0]] = cur; cur++; for(int j=1; j>n; vll a(n-1); rep(i,n-1) cin >> a[i], a[i]--; vvll g(n); g[0].push_back(0); ll cnt = 1; // 1つ以上の要素が残ってる頂点の数 string s = ""; vll col(n); ll cur = 1; rep(i,n-1) { g[a[i]].push_back(i+1); if(g[a[i]].size()%2==0) { cnt--; col[g[a[i]][0]] = cur; col[g[a[i]][1]] = cur; while(!g[a[i]].empty()) g[a[i]].pop_back(); cur ++; } else { cnt++; } s += (cnt==0) ? '1' : '0'; } cout << s << '\ '; if(cnt==0) { rep(i,n) cout << col[i] << ((i+1==n)?"\ ": " "); } } ```

Codechef Starters181 Div.2