IOI 2012 day1

公式
JAPLJさんによる翻訳
解いてみました。

Odometer

HOJerとかは得意系だと思うけど、Task 5が手強い。

コードは省略でコードの概要だけ

1.　一個ずつ交互に取っていって、無くなったら止まる。
2.　1.の後putしながら30回くらい往復する。
3.　石を一個ずつ真ん中にずらしながら往復する。
4.　直進・端に来たら１行ずれて左右逆バージョンをする・端の行まで行ったら初期位置に帰ってput連打。
5.　4.と同様の動きで石を回収していくコードと配るコードを何個も書く？　むずい。
(追記 → 0個の場所、1個の場所・・・を探していく方が良いらしい。なんか全部のマスを辿る方法も工夫が要りそう？)

解法：15分
実装：1時間？

Rings

１発AC出来たらぱなそう。
うまい解法あるのかなあ？
僕が思いついたのは
・次数３の頂点が出てきたらそのそこから距離２までの頂点のみの小さいグラフを作って貪欲にシミュレーションする。
・次数３以上の頂点が無いのにループが２つ以上出来たらダメとか
・場合分けは慎重にやらないといけない。

解法：15分でいったん放置→＋35分で方針決まる
実装：他の問題をやった後、残った時間で頑張る

Scrivener

とても面白い。
これは満点とって欲しいなぁ。

解法は下の図とコードで察してください。

赤が「文字の追加」「アンドゥー」などの編集の経過を表す経路。
何回目の操作の後、どの頂点に移るのかを配列で持つ。
青が文字列の変遷を表す木。
GetLetterをO(log N)程度で処理しなければならないので、文字木にはダブリングを施しておく。
要するに、1つ前の文字・2^1個前の文字・2^2個前の文字・・・・を保存しておく。

#include<cstdio>
#include<algorithm>
#define rep(i,n) for(int i = 0; i < n; i++)
using namespace std;

const int MX = 1000005, x20 = 20;

int s[MX]; // edit node
int l[MX][x20]; char c[MX]; // char node
int ns, cs;

void Init(){
	ns = cs = 1;
}

void TypeLetter(char L){
	c[cs] = L;
	s[ns] = cs;
	int p = s[ns-1];
	rep(i,x20){
		l[cs][i] = p;
		p = l[p][i];
	}
	cs++; ns++;
}

void UndoCommands(int U){
	s[ns] = s[ns-U-1];
	ns++;
}

char GetLetter(int P){
	int n = 0, p = s[ns-1];
	for(int i = x20-1; i >= 0; i--){
		if(l[p][i]){
			p = l[p][i];
			n += (1<<i);
		}
	}

	n -= P; p = s[ns-1];
	int x = 1<<x20-1;
	for(int i = x20-1; i >= 0; i--){
		if(n >= x){
			p = l[p][i];
			n -= x;
		}
		x >>= 1;
	}

	return c[p];
}





int main(){
	char a;
	int x;
	Init();
	while(1){
		scanf(" %c",&a);
		switch(a){
			case 't':{
				scanf(" %c",&a);
				TypeLetter(a);
				break;
			}
			case 'u':{
				scanf("%d",&x);
				UndoCommands(x);
				break;
			}
			case 'g':{
				scanf("%d",&x);
				printf("%c\n",GetLetter(x));
				break;
			}
			case 'e':{
				return 0;
			}
		}
	}

	return 0;
}

実装も軽い
解法：15分