AGC004 B-Colorful Slimes

【問題】
agc004.contest.atcoder.jp

【考察】
最初、魔法で色を変えられるスライムは 1 匹だけと勘違いしてて、各色のスライムごとに元になるスライムをどの色にすればコストが最小になるかを計算するコードを書いたんですが、サンプルの 2 で落ちて誤読に気づきました。そこでちょっと考えてみると、魔法の唱える回数を k と固定すると、全てのスライムは、適当な瞬間に召喚することにより、自分の色から k 遡るまでの任意の色のスライムから遷移できることが分かります。あとはその中で最小のコストを見つけて、その色のスライムから遷移すると決めればいいです。
最小値を計算するのにセグツリを使ったら結構実行時間が危なくなった。

【コード】

// RMQ のコードは省略
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll n,x;
	cin>>n>>x;
	RMQ rmq(n);
	REP(i,n) {
		ll a;
		cin>>a;
		rmq.update(i,a);
	}
	ll ret=INF*INF;
	REP(i,n+1) {
		ll cost=x*i;
		REP(j,n) {
			ll c=INF*INF;
			c=min(c,rmq.query(max(0ll,j-i),j+1));
			if(j-i<0) c=min(c,rmq.query(n-(i-j),n));
			cost+=c;
		}
		ret=min(ret,cost);
	}
	cout<<ret<<endl;
}

【使ったアイデア】
思いつくまで頑張る。

【得た知見】
何か重要な値を固定したり、要素を独立に考えたりすると見通しがよくなることがある（結構ある？）。

ARC058 D-いろはちゃんとマス目

【問題】
arc058.contest.atcoder.jp

【考察】
典型数え上げ問題の変形タイプ。この問題では少し特殊な制約がついていて、二項係数ライブラリで一発 AC というわけにはいきません。まず数え上げ問題の常套手段として、いくつかの排反な事象への場合分けをします。この場合分けのやり方は色々あると思うんですが、自分の場合は、

「このピンクで囲まれたマス (まとめて P とします) のうち、初めて到達するマスがどれであるか」で場合分けをしました。この場合分けは明らかに排反なものになっていますし、ゴールまでの経路は必ず P のうち少なくとも 1 つの点を通るため、この場合分けで全ての経路を数え上げることができます。P のうち上から i マス目 (点 p とする) を初めて訪れる経路の数を考えてみます。ここで、p までのある移動経路について最後の移動が下方向だった場合、その経路は P のうちの初めて訪れるマスが p ではありません。つまり、ある経路が P のうち初めて通るマスが p であるためには、p までの移動経路の最後の 1 回の移動は右方向である必要があります (逆に最後の 1 回の移動が右方向であれば、そのような経路は P のうち初めて通るマスが p となります)。あとは典型問題で、各 p ごとに p までの (P のうち初めて通るマスが p になるような) 経路数 * p からゴールまでの経路数を足していけばよいです。

【コード】

// 二項係数ライブラリは省略。mod_comb(n, k) が nCk に相当。
int main() {
	int h,w,a,b;
	cin>>h>>w>>a>>b;
	ll res=0;
	REP(i,h-a) {
		res+=mod_comb(b-1+i,b-1)*mod_comb(w-b-1+(h-1-i),w-b-1);
		res%=MOD;
	}
	cout<<res<<endl;
}

【使ったアイデア】
数え上げ問題における、排反事象への場合分け。二項係数の高速な計算。

【得た知見】
数え上げ問題は、何を基準に場合分けするかが肝心。

ARC024 C-だれじゃ

【問題】
arc024.contest.atcoder.jp

【考察】
そこまで難しくないんですが、結構一般的な知見を得た問題。
以下簡単のため、互いに共通部分をもっていてもアナグラムダジャレになれる、と考えます。まず、2 つの部分文字列がアナグラムの関係にあるとき、その部分列の各アルファベットの出現回数は等しくなります。そこで、ある英小文字列に含まれる 'a' ~ 'z' の数を記録しておく配列を便宜的にその文字列の「頻度表」と呼ぶことにすれば、S の長さ K の部分文字列を調べ上げ、同じ「頻度表」をもつものが見つかったなら S は長さ K のアナグラムダジャレを含むことが分かります。二分探索木を使って見たことのある部分文字列の頻度表を入れていけば、これを判定することができます。
当たり前ですが、全ての部分文字列の頻度表を愚直に作り上げていこうとすると、O(N^2) となり TLE してしまいます。ではどうすればいいかというと、ある部分文字列の頻度表は、すぐ隣の部分文字列の頻度表から O(1) で構成できる事実を用います。というのも、区間から消えるアルファベットを頻度表から減じ、新しく区間に入るアルファベットを頻度表に増やせばいいからです。この性質を利用することで、全ての頻度表を O(N) で列挙することができます。
以上をまとめます。区間の固定長 K の部分区間を調べ上げるような問題を考えます。これは愚直にやろうとすると、区間の大きさの二乗に比例する計算量がかかってしまいます。しかし、ある部分区間の情報が、その隣の部分区間の情報から O(1) で構成できるような性質をもっているときは、左から順に走査していくことで区間の大きさに比例する計算量で調べ上げることができます。
自明と言えば自明なことですが、意識しておけば若干閃きやすくなるような気がする。あと実装が地味にややこしいので、慣れておくとよい気がする。
あとこの問題、アナグラムダジャレがあるかないかだけじゃなくて、アナグラムダジャレの関係になるような組の数も、同じ計算量で求められます。

【コード】

int main() {
	ios::sync_with_stdio(false);
	int n,k;
	cin>>n>>k;
	string s;
	cin>>s;
	map<vector<int>, int> ma;
	vector<int> c(26,0);
	REP(i,k-1) {
		c[s[i]-'a']++;
	}
	bool f=false;
	FOR(i,k-1,n) {
		c[s[i]-'a']++;
		if(ma.count(c)!=0&&ma[c]<=i-(2*k-1)) f=true;
		if(ma.count(c)==0) ma[c]=(int)(i-(k-1));
		c[s[i-(k-1)]-'a']--;
	}
	if(f) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

【使ったアイデア】
固定長の部分区間を調べ上げるテクニック。

【得た知見】
以上の一般化。

【類題】
arc017.contest.atcoder.jp

ARC014 C-魂の還る場所

【問題】
arc014.contest.atcoder.jp

【考察】
N がそれなりに小さいのですが、ギリギリ半分全列挙はできないくらいの大きさ (そもそも効率的にマージする方法もなさそうですが)。そこで O(N^4) くらいの DP かなと思ってあれこれ考えてみるものの、箱に入ってる全てのボールの情報をもたないことには、どうやっても DP は不可能そう。ここでサンプルをよく見てみると、どちらのケースも解が小さいことに気づく。さらに軽く考察してみて、色ごとのボールの数を数えて奇数個あるものの種類数を出力するようにしたら AC。
軽く証明を考えてみます。奇数個ある色のボールは、どうやっても全て消すことができないので、少なくともこの解よりも小さい解を構成することはできません。次に、実際にこの解が構成できることを示します。まず、最初に入れる 2 つのボールが異なる色であるとしても一般性を失いません (初めのいくつかのボールが同じ色なら、それらは全て自動的に消えていくため)。仮にその 2 つのボールが赤色と青色であるとします。すると、次に赤か青のボールを入れるまでの間、円筒に入るボールは全て緑色です。この緑色のボールが偶数個の場合は、適当に片側に寄せてボールを入れていくことで、その全てを消すことができます。奇数個の場合は、仮に次に入れる緑以外のボールが赤色の場合、最後の 1 つを青色のほうに寄せて入れます。こうするとその赤色のボールを 2 つ並べて消したあとには、青色と緑色のボールが 1 つずつ残ることになります。このような操作を繰り返していけば、最終的に奇数個ある色のボールが 1 つずつ残るので、目的の解が構成できることが分かります (ちょっと議論を省略した)。
ちなみに枝刈り全探索してもギリギリ通るらしい。

【コード】

int main() {
	ios::sync_with_stdio(false);
	int N; string S; cin>>N>>S;
	int res=0;
	int rc=0,bc=0,gc=0;
	REP(i,N) {
		if(S[i]=='R') rc++;
		if(S[i]=='G') bc++;
		if(S[i]=='B') gc++;
	}
	res+=(rc%2!=0)+(bc%2!=0)+(gc%2!=0);
	cout<<res<<endl;
}

【使ったアイデア】
サンプルでエスパーする (解の予想をつける)。緩い制約に惑わされない。

【得た知見】
サンプルでエスパーしたほうが早い問題が存在する。

ARC038 C-茶碗と豆 (100点)

【問題】
arc038.contest.atcoder.jp

【考察】
Grundy 数を使いそうなのはすぐに分かるのですが、普通に山ごとに Grundy 数を設定しようとすると、ある山の遷移が他の山に影響を与える設定のせいでうまくいきません。そこで視点を変えて、茶碗に入っている豆ごとに Grundy 数を定めることにします。つまり山から豆が減る (あるいは増える) ことを遷移と捉えるのではなく、ある豆が、入っている茶碗の C の値によって定められる範囲内でより左の茶碗に移動することを遷移と見るわけです。これなら互いの豆は干渉し合わないため、入っている茶碗を基準としてうまく Grundy 数を決めていくことができます。ただ解説にも述べられているんですが、存在する全ての豆について、Grundy 数の XOR をとっていこうとすると TLE して 80 点しか取れません。幸いなことに、同じ値を偶数回 XOR すると 0 になる (XOR の関わる問題の重要な性質だと思う) ことから、ある茶碗に入った豆全体の XOR は、その豆の数が偶数なら 0 で、奇数なら豆が 1 つのときの Grundy 数に一致することがわかります。これを使うことで O(N) で XOR を取っていくことが可能です。
満点 (104点) 解法は、セグツリを使うことまでは分かったけど、うまく実装できなかった。かなしい。

【コード】

vector<int> memo;
vector<P> z;
int grundy(int x) {
	if(x==0) return 0;
	if(memo[x]!=-1) return memo[x];
	set<int> q;
	REP(i,z[x-1].first) q.insert(grundy(x-(int)(i+1)));
	int g=0;
	while(q.count(g)!=0) ++g;
	return memo[x]=g;
}
int main() {
	ios::sync_with_stdio(false);
	int n;
	cin>>n;
	memo.resize(n);
	REP(i,n) memo[i]=-1;
	z.resize(n);
	REP(i,n-1) cin>>z[i].first>>z[i].second;
	int ret=0;
	REP(i,n-1) {
		if(z[i].second%2==1) ret=ret^grundy((int)i+1);
	}
	if(ret!=0) cout<<"First"<<endl;
	else cout<<"Second"<<endl;
}

【使ったアイデア】
Grundy 数は、状態が他の要素に依存しないような対象に対して設定する。同じ数で XOR を偶数回とると 0 になる。

【得た知見】
この問題を解くために蟻本のゲームの章を読んだ。