ちぇ〜ふちぇふちぇふ。21位で入紫！星が4つになりました。普段はかなりスロースターターなんですが、今回は珍しく序盤からかなり冴えており非常にいい調子で5完することができました。嬉しい！
\(A_i > 0\)
かつ
\(\max(A) = A_i\)
であるような物を2つ足したもの、あるいは
\(A_i < 0\)
かつ
\(\min(A) = A_i\)
を二つ足したものは元の配列に含まれません(これは簡単に証明できます)。唯一、配列のすべての要素が0である場合は足しても0にしかならないので構成不可能です。
よって、これを適当に実装してあげることでこの問題を解くことができます。
void solve() {
int n; cin >> n;
set<ll> 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] << '\\n';
return;
}
}
cout << "-1\\n";
}Flipが可能なのはprefixに含まれる0, 1の個数が同じ時のみです。ということは、Flipの前後で個数は変わらないので、Flipしても以降のものに影響しません。
よって、構成可能な文字列の数は、Flip可能な場所が
\(k\)
個であるとすると
\(2^k\)
となります。
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 << '\\n';
}これかなり好きです。
\(A_{1, 1}=0\)
として実験してみると、右に+1するか-1するか、下に+1するか-1するかでそれぞれ2通り、合計4通りしかあり得ません。
よって、それら前計算しておき、「マス
\(A_{i,j}\)
を残すとした時に変えなければならない要素の個数」を求める全探索が可能で、全体で
\(O((NM)^2)\)
時間でこの問題を解くことができました。
void solve() {
int n, m;cin>>n>>m;
vvll a(n, vll(m));
rep(i,n)rep(j,m) cin >> a[i][j];
vector<vvll> 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 << '\\n';
}
これもかなり好きです。というか、Tree Colouringの本質部分が詰まっていて、これが置いてあったおかげでHardがめちゃくちゃ簡単になったので本当にありがとう。Writerさんありがとう。ちゅっちゅ
はい。まずは簡単に実験してあげると、同じ色が3つ以上ある場合はgoodではないことがわかります。また、ある辺が最短経路として用いられる回数が
ちょうど
一回となることを満たすためには、同じ色の頂点の親は同じ頂点でなければいけません。
頂点0は頂点0を親とする頂点とペアにしなければならないことに注意しつつ、上記のことを実装してあげることでこの問題を解くことができます。
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() << '\\n';
if(!((i==0&&cnt[i].size()%2==1) || (i>0&&cnt[i].size()%2==0))) {
cout << "-1\\n";
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<cnt[i].size(); j+=2) {
ans[cnt[i][j]] = cur;
ans[cnt[i][j+1]] = cur;
cur++;
}
} else {
for(int j=0; j<cnt[i].size(); j+=2) {
ans[cnt[i][j]] = cur;
ans[cnt[i][j+1]] = cur;
cur++;
}
}
}
rep(i,n)cout << ans[i] << ((i+1==n)?"\\n":" ");
}ハードです。基本的な考察は同じで、先ほどのものを1文字ずつ考えるようにしてあげれば良いです。あるタイミングでgoodであるかどうかは、色塗り待ちの頂点の有無で判定できます。これは愚直にやると \(O(N)\) かかりますが、色塗り待ちの頂点の個数を別途カウントしておけば \(O(1)\) でできます。0の親は0として考えるとしているところに実装上の差異はあるものの、基本的にはEasyと同じように考えてあげることで、この問題を解くことができます。
void solve() {
int n;cin>>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 << '\\n';
if(cnt==0) {
rep(i,n) cout << col[i] << ((i+1==n)?"\\n": " ");
}
}