ABC134-D Preparing Boxes

いやこれはどうやって解くの。何したら良いのかわっかんねーぞと思ったので頭の整理がてら書きます。

問題を見て考えたこと

とりあえず競プロの流儀に則って問題文を読みかえてみる。

・1以上N以下の任意の整数iについて、iの倍数が書かれた箱に入っているボールの個数の和を2で割った余りをa[i]に出来るような構成例を示せ。ただし一つの箱にボールは一つしか入らない。

うーん、言い換え方もわからん！w
iの箱ではなくiの倍数が書かれた箱、そして入るボールは一つだけというのがこの問題の難しいポイントですね。とりあえず全探索を考えると2^10^5で、数え上げお姉さんになってしまいます。
これはつらいのでDPを考えます。

dp[i][j] := i番目までみた時にjを入れることで構築可能かどうか(j == 0 or 1)

として、復元してやればワンチャンありそうです。想定解ではないでしょうが。
しかし初期状態を考えようとしてふと思いました。これ前から見ても決まらなくないか。
例えば1の倍数はN個存在するわけですが、1を見ている段階では0と1それぞれの時に構築が可能かどうか判断が出来ません。何故ならその後の数によって0にするのが最適になるかもしれないし、1にするのが最適かもしれないし、どちらにしても構築は不可能かもしれません。
逆に最後から見れば、その倍数が書かれた箱に現在入っている数を実際に確かめながら見ていくことでこれを効率的に達成できます。

つまりこの問題の苦しいところは、もしも前から見てしまうと、2という箱を見ている時に4や6の箱にボールが入っているかどうかの情報が無いため、適切な判断が下せないということです。

というわけで実装します。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

int main(int argc, char const *argv[]) {
	int n; cin>>n;
	vector<int> a(n+1), b(n+1), ans;
	rep(i,n) cin>>a[i+1];
	for (int i = n; i >= 1; --i) {
		int sum = 0;
		for (int j = i+i; j <= n; j+=i) {
			sum+=b[j];
		}
		if (sum%2==1) {
			if (a[i]==1) b[i]=0;
			else b[i]=1, ans.push_back(i);
		}
		else {
			if (a[i]==1) b[i]=1, ans.push_back(i);
			else b[i]=0;
		}
	}
	sort(ans.begin(), ans.end());
	cout<<ans.size()<<endl;
	rep(i,ans.size()) cout<<ans[i]<<endl;
	return 0;
}

するとACしました。いや結局この問題の本質を理解できていなかったので、ダメ