スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

IOPC 2012

2012/01/14 16:00 ~ 01/15 16:00 (JST)
CodeChef がホストで開催された IOPC 2012 の参加記録。

komiya さんに声をかけてもらったので、hasi さんとの 3 人チームで参加。

Tags : プログラミング CodeChef 未解決

結果

17 問中 13 問解いて 6 位。
僕が 1 つの問題で悩んでいる間に komiya さんが何問もぽんぽん解いていってすごかった。
hasi さんが難しい問題をさくっと通してるのもすごかった。

僕はといえば、ライブラリが遅くて TLE したり、ライブラリがバグっていたり、色々ひどかった。
まぁでも、久しぶりのチーム戦は楽しかった。

自分がある程度係わっていて、解法を把握している問題については、解説を書きます。

問題

問題セットの原文はここを参照。

01 : Rubiks cube

3×3のルービックキューブで回転操作の列が与えられる。
その操作列を何セット繰り返せば最初の状態に戻るか?

操作列の長さ ≦ 1000

02 : Quadrilaterals

頂点が格子点の正方形 A が与えられる。
Σ_{ B は頂点が格子点の凸四角形で、各辺の中点がAの頂点 } area(B) を mod 10^9+7 で求めよ。

テストケース数 ≦ 25000
-10^9 ≦ 座標値 ≦ 10-9

03 : Crazy texting

携帯電話の入力方式で文字列を入力する。
連続する数字の区切りを任意に決めていいとして、何通りの文字列が出力されうるか?

テストケース数 ≦ 10
文字列長 ≦ 10^5

10 : An unfortunate incident

N 人の生徒それぞれが、好きな生徒のリストを持っている。
「 生徒の任意の部分集合 S に対して、( S にいる生徒が1人以上書かれたリストの数 ) ≧ |S| 」 であるかどうかを判定せよ。

テストケース数 ≦ 10
N ≦ 500
各リストの長さ ≦ 50

解答

言語は C++。テンプレはここを参照。

01.
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }
ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }

int n_op,op[3000];
int f[6][6][9],g[6][6][9]; // [U,L,F,R,B,D][face][id] -> f:どの面にいくか, g:どの番号にいくか

int loop[6][9]={}; // ループするまでの操作回数
int rec(int face,int id,int j,int face0,int id0){
if(~loop[face][id]) return loop[face][id];

if(j>0 && face==face0 && id==id0) return loop[face][id]=j;

int face2=face,id2=id;
rep(i,n_op){
int tmpf=face2,tmpi=id2;
face2=f[op[i]][tmpf][tmpi];
id2 =g[op[i]][tmpf][tmpi];
}
return loop[face][id]=rec(face2,id2,j+1,face0,id0);
}

int main(){
// set f, g
rep(o,6) rep(k,6) rep(i,9) {
f[o][k][i]=k;
g[o][k][i]=i;
}
// Up
f[0][1][0]=4; f[0][1][1]=4; f[0][1][2]=4;
f[0][2][0]=1; f[0][2][1]=1; f[0][2][2]=1;
f[0][3][0]=2; f[0][3][1]=2; f[0][3][2]=2;
f[0][4][0]=3; f[0][4][1]=3; f[0][4][2]=3;
g[0][0][0]=2; g[0][0][1]=5; g[0][0][2]=8;
g[0][0][3]=1; g[0][0][4]=4; g[0][0][5]=7;
g[0][0][6]=0; g[0][0][7]=3; g[0][0][8]=6;
// Left
f[1][0][0]=2; f[1][0][3]=2; f[1][0][6]=2;
f[1][2][0]=5; f[1][2][3]=5; f[1][2][6]=5;
f[1][4][2]=0; f[1][4][5]=0; f[1][4][8]=0;
f[1][5][0]=4; f[1][5][3]=4; f[1][5][6]=4;
g[1][0][0]=0; g[1][0][3]=3; g[1][0][6]=6;
g[1][2][0]=0; g[1][2][3]=3; g[1][2][6]=6;
g[1][4][2]=6; g[1][4][5]=3; g[1][4][8]=0;
g[1][5][0]=8; g[1][5][3]=5; g[1][5][6]=2;
g[1][1][0]=2; g[1][1][1]=5; g[1][1][2]=8;
g[1][1][3]=1; g[1][1][4]=4; g[1][1][5]=7;
g[1][1][6]=0; g[1][1][7]=3; g[1][1][8]=6;
// Front
f[2][0][6]=3; f[2][0][7]=3; f[2][0][8]=3;
f[2][1][2]=0; f[2][1][5]=0; f[2][1][8]=0;
f[2][3][0]=5; f[2][3][3]=5; f[2][3][6]=5;
f[2][5][0]=1; f[2][5][1]=1; f[2][5][2]=1;
g[2][0][6]=0; g[2][0][7]=3; g[2][0][8]=6;
g[2][1][2]=8; g[2][1][5]=7; g[2][1][8]=6;
g[2][3][0]=2; g[2][3][3]=1; g[2][3][6]=0;
g[2][5][0]=2; g[2][5][1]=5; g[2][5][2]=8;
g[2][2][0]=2; g[2][2][1]=5; g[2][2][2]=8;
g[2][2][3]=1; g[2][2][4]=4; g[2][2][5]=7;
g[2][2][6]=0; g[2][2][7]=3; g[2][2][8]=6;
// Right
f[3][0][2]=4; f[3][0][5]=4; f[3][0][8]=4;
f[3][2][2]=0; f[3][2][5]=0; f[3][2][8]=0;
f[3][4][0]=5; f[3][4][3]=5; f[3][4][6]=5;
f[3][5][2]=2; f[3][5][5]=2; f[3][5][8]=2;
g[3][0][2]=6; g[3][0][5]=3; g[3][0][8]=0;
g[3][2][2]=2; g[3][2][5]=5; g[3][2][8]=8;
g[3][4][0]=8; g[3][4][3]=5; g[3][4][6]=2;
g[3][5][2]=2; g[3][5][5]=5; g[3][5][8]=8;
g[3][3][0]=2; g[3][3][1]=5; g[3][3][2]=8;
g[3][3][3]=1; g[3][3][4]=4; g[3][3][5]=7;
g[3][3][6]=0; g[3][3][7]=3; g[3][3][8]=6;
// Back
f[4][0][0]=1; f[4][0][1]=1; f[4][0][2]=1;
f[4][1][0]=5; f[4][1][3]=5; f[4][1][6]=5;
f[4][3][2]=0; f[4][3][5]=0; f[4][3][8]=0;
f[4][5][6]=3; f[4][5][7]=3; f[4][5][8]=3;
g[4][0][0]=6; g[4][0][1]=3; g[4][0][2]=0;
g[4][1][0]=6; g[4][1][3]=7; g[4][1][6]=8;
g[4][3][2]=0; g[4][3][5]=1; g[4][3][8]=2;
g[4][5][6]=8; g[4][5][7]=5; g[4][5][8]=2;
g[4][4][0]=2; g[4][4][1]=5; g[4][4][2]=8;
g[4][4][3]=1; g[4][4][4]=4; g[4][4][5]=7;
g[4][4][6]=0; g[4][4][7]=3; g[4][4][8]=6;
// Down
f[5][1][6]=2; f[5][1][7]=2; f[5][1][8]=2;
f[5][2][6]=3; f[5][2][7]=3; f[5][2][8]=3;
f[5][3][6]=4; f[5][3][7]=4; f[5][3][8]=4;
f[5][4][6]=1; f[5][4][7]=1; f[5][4][8]=1;
g[5][5][0]=2; g[5][5][1]=5; g[5][5][2]=8;
g[5][5][3]=1; g[5][5][4]=4; g[5][5][5]=7;
g[5][5][6]=0; g[5][5][7]=3; g[5][5][8]=6;

int atoop[128];
atoop['U']=0; atoop['L']=1; atoop['F']=2;
atoop['R']=3; atoop['B']=4; atoop['D']=5;

int T; scanf("%d",&T);
while(T--){
char s[1001]; scanf("%s",s);

n_op=0;
for(int j=0;s[j];j++){
int o,cnt;
if (isalpha(s[j])) o=atoop[s[ j ]], cnt=1;
else if(s[j]=='2') o=atoop[s[j-1]], cnt=1;
else o=atoop[s[j-1]], cnt=2;
while(cnt--) op[n_op++]=o;
}

ll ans=1;
memset(loop,-1,sizeof loop);
rep(k,6) rep(i,9) ans=lcm(ans,rec(k,i,0,k,i));

printf("%lld\n",ans);
}

return 0;
}

回転パターンを全部埋め込んで、各マスが何回でループするかを求めて、最小公倍数をとる。
TLE したのでメモ化して 6*9 倍速くらいにした。
答えの上界が見積もれないので多倍長がいる気にもなるけど、long long で accepted をもらえた。
方針とデバッグは hasi さん。
大変だった。ライブラリ化しておこう。

02.
const ll M=100000007;

struct point{ int x,y; };

point operator-(const point &a,const point &b){ return (point){a.x-b.x,a.y-b.y}; }
ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }

inline ll cross(const point &a,const point &b){
return (ll)a.x*b.y-(ll)a.y*b.x;
}

ll area2(const point &a,const point &b,const point &c){
return llabs(cross(b-a,c-a));
}

ll solve(point p[4]){
ll nb=4; // 境界にある格子点の個数
rep(i,4) nb+=gcd(abs(p[(i+1)%4].x-p[i].x),abs(p[(i+1)%4].y-p[i].y))-1;
ll A=(area2(p[0],p[1],p[2])+area2(p[0],p[2],p[3]))/2; // 面積
ll ni=A-nb/2+1; // 内部にある格子点の個数 (Pick の定理)
return 2*(A%M)*(ni%M)%M;
}

int main(){
int T; scanf("%d",&T);
while(T--){
point p[4];
rep(i,4) scanf("%d%d",&p[i].x,&p[i].y);

// 頂点を CW or CCW に並べ替え
int u=0,b=0; // 上の頂点, 下の頂点
rep(i,4){
if(p[i].y<p[u].y || p[i].y==p[u].y && p[i].x<p[u].x) u=i;
if(p[i].y>p[b].y || p[i].y==p[b].y && p[i].x>p[u].x) b=i;
}
int j1=0; while(j1==u || j1==b) j1++;
int j2=0; while(j2==u || j2==b || j2==j1) j2++;

point q[4]={p[u],p[j1],p[b],p[j2]};

printf("%lld\n",solve(q));
}

return 0;
}

1 つの頂点を決めれば、あとの 3 つは中点の制約から自動的に決まる。
こうしてできる四角形 B が凸になるのは、一点を図の緑の位置に取ったときに限る。これは紙に描いて実験していれば見えてくる。
( 境界は含まない。境界では縮退して三角形になる。 )

また、( B の面積 = A の面積の 2 倍 ) であることは図をみれば明らか。
整数座標の四角形にのみ興味があるので、B としていくつの四角形がありうるかというのは、A の内部にある格子点を数えればいいことになる。

これは、Pick の定理を使えば簡単に計算できる。( komiya さんに教えてもらった )

余談:
実は、似た格好をした問題 ( 本当は全然違う ) を POJ で解いたことがあった。
POJ 1940 : Polygon Programming with Ease
この問題は何も考えずに連立一次方程式に直して解いたので、今回もそれができると思っていた。
でも、行列をよく観察してみると、次数が偶数のときにはランク落ちして、解が一意に定まらないことがわかる。
x, y 方向にそれぞれ自由度 1 がある。
( POJ 1940 を読み直してみると、n は奇数という制約がしっかり付いていた。)
結局、悩んだ末、上の解法に至った。

03.
const ll M=100000007;

int main(){
int f[128]; // キーの種類
f['a']=f['b']=f['c']=2;
f['d']=f['e']=f['f']=3;
f['g']=f['h']=f['i']=4;
f['j']=f['k']=f['l']=5;
f['m']=f['n']=f['o']=6;
f['p']=f['q']=f['r']=f['s']=7;
f['t']=f['u']=f['v']=8;
f['w']=f['x']=f['y']=f['z']=9;
int g[128]; // 押下回数
g['a']=g['d']=g['g']=g['j']=g['m']=g['p']=g['t']=g['w']=1;
g['b']=g['e']=g['h']=g['k']=g['n']=g['q']=g['u']=g['x']=2;
g['c']=g['f']=g['i']=g['l']=g['o']=g['r']=g['v']=g['y']=3;
g['s']=g['z']=4;
int h[10]={-1,-1,3,3,3,3,3,4,3,4}; // 周期

// dp3[i] := 長さ i, 周期 3 の解
static ll dp3[400001],dp4[400001];
// 周期的でない場合
dp3[0]=dp4[0]=1;
rep(i,400001){
if(i>=1) dp3[i]+=dp3[i-1], dp4[i]+=dp4[i-1];
if(i>=2) dp3[i]+=dp3[i-2], dp4[i]+=dp4[i-2];
if(i>=3) dp3[i]+=dp3[i-3], dp4[i]+=dp4[i-3];
if(i>=4) dp4[i]+=dp4[i-4];
dp3[i]%=M;
dp4[i]%=M;
}
// 周期的な場合も考慮
rep(i,400001){
if(i>3) dp3[i]+=dp3[i-3];
if(i>4) dp4[i]+=dp4[i-4];
dp3[i]%=M;
dp4[i]%=M;
}

int T; cin>>T;
while(T--){
string s; cin>>s;
int n=s.length();

ll ans=1;
for(int i=1,len=g[s[0]];i<=n;i++){
if(i==n || f[s[i]]!=f[s[i-1]]){
if(h[f[s[i-1]]]==3) ans=(ans*dp3[len])%M;
else ans=(ans*dp4[len])%M;
len=0;
}
len+=g[s[i]];
}
printf("%lld\n",ans);
}

return 0;
}

UAPC の I 問題 : 11224111122411 とまったく同じ。
あのときは OEIS というチート技を使って解いたけど、今回はちゃんと DP で解いた。
前のコードを参照もしなかったので、しっかり身についている感があってよい。

10.
( コードは自分で書いていないので略 )

生徒を頂点、生徒 u が生徒 v を好きなときに辺 u -> v があるような有向グラフを考える。
問題は、

このグラフの頂点の部分集合 S について、
| S のある頂点への有向辺をもつ頂点全体 | ≧ |S| …… (*)

であるかどうかを判定する、と言い換えられる。

有向グラフの頂点をコピーして、
生徒 u が生徒 v を好きなときに、左の頂点 u から右の頂点 v への辺がある
ような二部グラフを考える。
(*) は、この二部グラフが完全マッチングを持つことと同値。

実際、完全マッチングを持てば、各生徒 v に対して、v のことが好きな別々の生徒が割り当てられることになるので、(*) はみたされる。
逆も正しいけど、これは自明ではない。コンテスト中は証明なしに使った。

上記の解法はけっこう時間をかけて考えたんだけど、これは Hall の結婚定理というらしくて、知っていれば瞬殺だったとか。

反省

00 が解けないなど、自分は探索が苦手だということがはっきりわかった。
そういえば年末の hos さんのコンテストでも A の数論っぽい探索が解けなかった。

あと、グラフ理論の知識がまったく足りてない。
LCA, Hall の結婚定理, 最短経路木
などなど。

今後の練習ではそこを重点的に強化したい。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。