スポンサーサイト

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

CodeFest'11 Manthan

2011/03/14 1:30~4:30 (JST)
CodeFest'11 Manthan の参加記録

FAQ から適当に引用

Q. CodeFest って何?
A. CodeFest is the annual technical festival of Computer Engineering Society, IT-BHU, started in 2010. All the events are completely online.
( CodeFest は 2010 年から始まった、年 1 回のコンピュータのお祭です。すべてのイベントはオンラインで開催されます。)

Q. 誰が参加できるの?
A. All the events except Ratespiel are open to students and professionals. Ratespiel is open to students only.
( Ratespiel は学生のみが参加できます。それ以外は誰でも参加できます。)

Q. 何かくれるの?
A. Yeah, there are lots of prizes to be won :).
( 良い成績を残した人には賞金が出るよ。)

Tags : プログラミング Codeforces

CodeFest の詳細をもう少しメモ。

イベントは 5 種類。
ratespiel, virtual combat, mathmania, perplexed!, manthan.

今年、私が参加したのは manthan だけ。他のイベントの詳細は読んでないから知らない。
来年はもっと出てみよう。

manthan はアルゴリズムを重視したプログラミングコンテスト。
競技は Codeforces のシステムを使って行われた。
ルールは Codeforces のいつものルールとほとんど同じ。
ランダムに部屋に振り分けられて、制限時間内に問題を解きつつ Hack もできる。
5 問。3 時間。

結果

A. Hacked,AC(346)
B. -
C. Hacked
D. AC(1304)
E. -
Hacks : +-0 (0 hacked / 0 missed)
Standing : 164/1405
Rating : 17151781


あとで全部解いた感想:
問題の難易度の分散が小さかった気がする。
5 分で解けるような簡単な問題もなければ、まったく手をつけられないような難しい問題もなかった。

問題

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

A. Partial Teacher
n (≦1000) 人にお菓子をあげる。
あげるお菓子の数は次の規則をみたさないといけない。
長さ n-1 の L, R, = からなる文字列があり、i 文字目が
・ L のとき、i 人目のお菓子の数 > i+1 人目のお菓子の数
・ R のとき、i 人目のお菓子の数 < i+1 人目のお菓子の数
・ = のとき、i 人目のお菓子の数 = i+1 人目のお菓子の数
がすべての i で成立。

あげるお菓子の総数を最小化するとき、各人にあげるお菓子の数を答えよ。
各人にあげるお菓子の数は 1 以上でないといけない。

B. Restoration of the Permutation
A = {a1, a2, .., an} を 1, 2, .., n の任意の置換とする。
B = {b1, b2, .., bn} を次で定める。
at = i となる番号を t とするとき、
bi = ( a1, a2, .., at-1 の中で、値が i+k 以上となる項の個数 )

n (≦1000), k (≦1000), B が与えられたとき、A としてありうるものの中で辞書式最小のものを答えよ。
解が存在することは保証されている。

C. Sequence of Balls
文字列 A から文字列 B へ返還するための最小コストを求めよ。
許される操作は次の 4 種類。
・ 任意の 1 文字を任意の箇所へ挿入する
・ 任意の 1 文字を削除する
・ 任意の 1 文字を任意の 1 文字に置換する
・ 任意の 1 文字をその隣の文字と入れ替える

それぞれの操作を 1 回行うためのコストが与えられる。
2・スワップコスト ≧ 挿入コスト + 削除コスト を仮定してよい。

A, B : 長さ 4000 以下で小文字アルファベットのみからなる。

D. Optical Experiment
図を見るのが一番わかりやすい。
画像を転載していいか分からないので URL だけ書く。ここ

このような光線の穴の対応が与えられたとき、
「光線の集合で、どの 2 つの光線も交差しているようなもの」の中で要素数が最大のもの(の要素数)を求めよ。

一列にある穴の数 ≦ 106

E. Save the City!
単純多角形が与えられる。
入力で与えられる順で、最初の点を A, 2 つめの点を B とする。
辺 AB 上の格子点のうち、その点から多角形全体が見えるものの個数を求めよ。
辺 AB は x 軸に平行であると仮定してよい。

頂点数 ≦ 1000

解答

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

A.
bool chk(int x,int y,char c){
if(c=='L') return x>y;
if(c=='R') return x<y;
return x==y;
}

int main(){
int n;
char s[1010]; scanf("%d%s",&n,s);

int t[1010]; t[0]=1;
rep(i,n-1){
if(s[i]=='L'){
t[i+1]=1;
int j=i;
while(!chk(t[j],t[j+1],s[j]) && j>=0){
t[j]++;
j--;
}
}
else if(s[i]=='R') t[i+1]=t[i]+1;
else t[i+1]=t[i];
}

rep(i,n) printf("%s%d",i?" ":"",t[i]);
putchar('\n');

return 0;
}

A 問題なのに簡単じゃない。
たとえば、
RLLL というケースでは 1 3 2 1 が答え。
RRRRLL というケースでは 1 2 3 4 2 1 が答え。

左から順番に、その時点で考えられる一番良い値を埋めていく。
矛盾が出たら、矛盾が出なくなるまで戻りながら値を補正する。
これで通ったけど、アルゴリズムの正当性は証明できてないからスッキリしない。
誰か納得いく説明してくれないかな。

B. (時間外)
int main(){
int n,k; scanf("%d%d",&n,&k);
int b[1000];
rep(i,n) scanf("%d",b+i);

vi a;
for(int i=n-1;i>=0;i--){
bool ok=false;
for(int j=0,cnt=0;j<a.size();j++){
if(cnt==b[i]){ a.insert(a.begin()+j,i+1); ok=true; break; }
if(a[j]>=i+k+1) cnt++;
}
if(!ok) a.insert(a.end(),i+1);
}

rep(i,n) printf("%d%c",a[i],i<n-1?' ':'\n');

return 0;
}

わからん。なんでこんなに解けてる人が多いんだろう。
問題文の読解からして難しい。
この問題文じゃ説明不足だと思ったから「at って何ですか?」って聞いてみたら、No comments と返された。
あとで解説見ながら解く。

[ 2011/03/16 追記 ]

公式の解説を見ながら解いた。
大きい値から順番に、Greedy に追加していけばいいらしい。
STL の vector を使うと書きやすい。

C. (時間外)
int DamerauLevenshteinDistance(const string &s,const string &t,int INS=1,int DEL=1,int RPL=1,int SWP=1){
const int LMAX=4000;
static int dp[LMAX+1][LMAX+1];
int slen=s.length(),tlen=t.length();

rep(i,slen+1) dp[i][0]=i*DEL;
rep(j,tlen+1) dp[0][j]=j*INS;

int slast[128]={};
for(int i=1;i<=slen;i++){
int tlast=0;
// int tlast[128]={};
for(int j=1;j<=tlen;j++){
int i1=slast[t[j-1]],j1=tlast;
// int i1=slast[t[j-1]],j1=tlast[s[i-1]];

dp[i][j]=INF;
dp[i][j]=min(dp[i][j],dp[i][j-1]+INS);
dp[i][j]=min(dp[i][j],dp[i-1][j]+DEL);
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(s[i-1]==t[j-1]?0:RPL));
if(i1>0 && j1>0){
dp[i][j]=min(dp[i][j],dp[i1-1][j1-1]+(i-i1-1)*DEL+SWP+(j-j1-1)*INS);
}

if(s[i-1]==t[j-1]) tlast=j;
// tlast[t[j-1]]=j;
}
slast[s[i-1]]=i;
}

return dp[slen][tlen];
}

int main(){
int ti,td,tr,te;
string s,t; cin>>ti>>td>>tr>>te>>s>>t;
cout<<DamerauLevenshteinDistance(s,t,ti,td,tr,te)<<endl;
return 0;
}

スワップ操作がなければ、編集距離 (Levenshtein距離) を求める典型的な DP.
スワップをどう実現するかが問題。
それっぽいのを書いてみたが、submit した瞬間に Hack された。

[ 2011/03/17 追記 ]

解いた。
でも完璧には理解できていないので、以下の文章は間違っているかもしれない。
主に参考にしたものは以下。
公式の解説
Wikipedia - Damerau-Levenshtein distance
薊野日記 2006/11/10 の記事
・ eng.heshamali さんの解答
・ simp1eton さんの解答

Levenshtein距離の拡張で、Damerau-Levenshtein距離というものがあるらしい。
これは、挿入, 削除, 置換に加え、隣接要素のスワップを許すというもの。
今回の問題は Damerau-Levenshtein距離の一般化 (操作コストが任意) といえる。

方針は、Levenshtein距離の DP にスワップ操作による遷移を追加する感じ。
その際に、問題の条件 ( 2・スワップコスト ≧ 挿入コスト + 削除コスト ) が利いてくる。
この条件から、最適解では同じ要素は高々 1 回しかスワップしないということが出てくる。

以下、変換前の文字列を S, 変換後の文字列を T と書く。
S[0] から S[i] までの部分文字列を S(i) と書く。T(i) も同様。
dp[i][j] := S(i) を T(j) に変換するための最小コスト
で、スワップ操作による遷移は、
dp[i][j]
= min( S(i1-1) を T(j1-1) に変換するための最小コスト + (i-i1-1) 回削除 + 1 回スワップ + (j-j1-1) 回挿入 )
= min( dp[i1-1][j1-1] + (i-i1-1) 回削除 + 1 回スワップ + (j-j1-1) 回挿入 )
for all 1 ≦ i1 ≦ i-1, 1 ≦ j1 ≦ j-1

という形しかない。
( 上記の条件がなければ、同じ要素を複数回スワップするということがありうるので、変な状態も作れてしまう。そうなるとこの方法では解けない。)

このままだと DP の 1 ステップごとに O(S.length・T.length) 時間がいるけど、実は、スワップできる場所のうち一番右のものだけを覚えておけば十分。
ソースコード中の slast, tlast がそれに相当。
tlast は配列にしたほうが対称性があって考えやすいけど、配列にしなくても書ける。
配列にした version もコメントアウトして残しておいた。

余談:
Damerau-Levenshtein距離は数学的には距離じゃない。( 三角不等式が成り立たない。)

D.
int n,p[1000010];

int LIS(){
static int lis[1000010];
rep(i,n) lis[i]=INF;
rep(i,n) *lower_bound(lis,lis+n,p[i])=p[i];
return find(lis,lis+n,INF)-lis;
}

int main(){
scanf("%d",&n);
map<int,int> f;
rep(i,n){
int x; scanf("%d",&x);
f[x]=i;
}
rep(i,n){
int y; scanf("%d",&y);
p[i]=-f[y];
}

printf("%d\n",LIS());

return 0;
}

あることに気付ければ、あとは知識問題。

箱の上の列の穴を左から順に 1, 2, .., n と番号付けする。
箱の下の列の穴の並びは、1, 2, .., n の置換に対応している。
これを、s(1), s(2), .., s(n) と書くことにする。

{1, 2, .., n} の部分集合 {a1, a2, .., ak} が、問題の条件 (どの 2 つも交差する) をみたすのは、
s(a1) > s(a2) > .. > s(ak)
と同値。

なぜなら、ある i, j で s(i) < s(j) なら、i, j に対応する光線対は交差しないから。
( 置換を考えているから等号のケースはそもそもない。)

なので、問題は s(1), s(2), .., s(n) の最長減少部分列、すなわち
-s(1), -s(2), .., -s(n) の最長増加部分列 (LIS) を求めることと同じ。

LIS はアルゴリズムを工夫すれば O(nlogn) 時間で求めることができる。
といっても O(nlogn) 解法を自分で書いたことはなくて、すぐに書ける自身もなかったので、ネット上の資料をありがたく使わせてもらった。

[ 2011/03/18 追記 ]

Wikipedia - Permutation graph に答えがそのまま書いてあった。
the largest clique in a permutation graph corresponds to the longest decreasing subsequence in the permutation defining the graph.
( 置換グラフにおける最大クリークは、グラフを定義する置換の最長減少部分列に対応します。)


E. (時間外)
int main(){
int n; scanf("%d",&n);
Polygon g(n);
rep(i,n){
int x,y; scanf("%d%d",&x,&y);
g[n-i-1]=Point(x,y);
}
Point A=g[n-1],B=g[n-2];
if(A.real()>B.real()) swap(A,B);
Segment s(A,B);
double left=min(A.real(),B.real()),right=max(A.real(),B.real());

rep(i,n-1){
Point v=g[i],prevv=g[(i-1+n)%n],p;
Line l(prevv,v);
if(intersect(l,s,&p)){
if(ccw(prevv,v,A)!=CCW) left =max(left ,p.real());
if(ccw(prevv,v,B)!=CCW) right=min(right,p.real());
}
else{
if(ccw(prevv,v,A)!=CCW || ccw(prevv,v,B)!=CCW){ left=1e30; break; }
}
}

printf("%d\n",(int)max(floor(right+EPS)-ceil(left-EPS)+1,0.0));

return 0;
}

[ 2011/03/18 追記 ]

自前の幾何ライブラリは、今はまだ公開したくないので省略。

多角形の (辺 AB 以外の) すべての辺について、その辺の (反時計回りになぞる方向で) 左側が見えるような辺 AB 上の範囲を考える。この範囲は区間になる。
これらの区間の積集合が答えだから、答えも区間。
区間であれば、左端を右端だけに注目すればいいから、実装も難しくない。

O(n) で解いてしまったけど、入力サイズから考えて O(n2) でも間に合うはず。
O(n2) のもっとシンプルな解法があるのかもしれない。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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