スポンサーサイト

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

Codeforces Alpha Round #21

日本時間で 6/28 22:00~24:00 に行われた Codeforces Alpha Round #21 の参加記録です。

Alpha Round は今回で 2 回目の開催、私は初参加でした。
今回はいつもとは違う Codeforces format というルール。競技中に相手のソースコードを読むことができ、バグをみつけて落とす(Hackする)といった、対戦型の競技です。

TopCoder の SRM にも似ていますが、Codeforces はコーディングと相手への攻撃が同時に行われます。
時間をどう分配するかはプレイヤー次第といったところでしょうか。

問題と解答は [ 続きを読む ] から

Tags : プログラミング Codeforces

今回の問題は全 4 問です。

[ 問題 ]
今回の問題セットはこんな感じでした。

A. Jabber ID
与えられた文字列が <username>@<hostname>[/resource] というフォーマットになっているかどうかを判定する。
ここで、
<username> と resorce は、アルファベット(A-Z,a-z),数字(0-9),アンダースコア(_)からなる1~16文字の文字列。
<hostname> は、1 ~ 32 文字の文字列で、いくつかのドット(.)で区切られている。ドットで区切られた各部分列は <username> と同じ条件をみたす。

たとえば、
mike@codeforces.com は ○
john.smith@codeforces.ru/contest.icpc/12 は × (usernameにドットがある, /以降にドットと/がある)
i_am@a_pen は ○ (ドットは0個でもいい! これは問題文からは読み取りにくい!!)

B. Intersection
6つの整数 A1, A2, …, C2 が与えられたときに、
{ (x,y) | A1x+B1y+C1=0 and A2x+B2y+C2=0 }
という集合の要素数を求める。(無限個なら -1 を出力する)

C. Stripe 2
与えられた n ( ≦ 105 ) 個の整数からなる数列
a1, a2, …, an
の 2 箇所に区切りを入れて 3 個の部分 (いずれも空でない) に分割するとき、それぞれの部分に含まれる数の和が等しくなるような分割は何通りあるか?

D. Traveling Graph
頂点数 n, 辺数 m の重みつき無向グラフが与えられる。
頂点 1 から出発して、すべての辺を少なくとも 1 回通るような閉路の中で、重みの和が最小になるものを求めよ。
そのような閉路がないときは -1 と答えよ。
なお、入力されるグラフは自己ループや多重辺を含んでいてもよい。

1 ≦ n ≦ 15
0 ≦ m ≦ 2000

[ 解答 ]
言語は C++。include文とusing文は省略。
追記した分はテンプレを使っている。テンプレはここを参照。

A. (時間外)
bool validchr(char c)
{
if(!isalnum(c) && c!='_') return false;
return true;
}

bool validlen(string s,int l)
{
if(s.length()<1 || l<s.length()) return false;
return true;
}

bool validstr(string s)
{
if(!validlen(s,16)) return false;
for(int i=0;i<s.length();i++) if(!validchr(s[i])) return false;
return true;
}

void end(char *s)
{
cout<<s<<endl; exit(0);
}

int main()
{
string str; cin>>str;
int len=str.length();

int at=0;
for(int i=0;i<len;i++){
if(str[i]=='@'){ at=i; break; }
}
if(!validstr(str.substr(0,at))) end("NO");

int dot[128]={0},dnum=0,slash=len;
for(int i=at+1;i<len;i++){
if(str[i]=='.') dot[dnum++]=i;
if(str[i]=='/'){ slash=i; break; }
}
if(!validlen(str.substr(at+1,slash-at-1),32)) end("NO");

if(dnum!=0){
if(dot[0]-at-1<1 || 16<dot[0]-at-1) end("NO");
for(int i=0;i<dnum-1;i++){
if(dot[i+1]-dot[i]-1<1 || 16<dot[i+1]-dot[i]-1) end("NO");
}
if(slash-dot[dnum-1]-1<1 || 16<slash-dot[dnum-1]-1) end("NO");
}

for(int i=at+1;i<slash;i++){
if(str[i]=='.') continue;
if(!validchr(str[i])) end("NO");
}

if(slash==len) end("YES");

if(!validstr(str.substr(slash+1))) end("NO");

end("YES");

return 0;
}

書くだけの問題ですが、hostname まわりの処理を失敗して、競技中に書いたコードはhackされてしまいました
正規表現が使える言語なら、かなり短く書けるみたいですね。( Ruby で1行で済ましている人もいました)

B. (時間外)
int main()
{
int a1,a2,b1,b2,c1,c2;
cin>>a1>>b1>>c1>>a2>>b2>>c2;

// null set
if(a1==0 && b1==0 && c1!=0){ cout<<0; return 0; }
if(a2==0 && b2==0 && c2!=0){ cout<<0; return 0; }

// universal set
// if(a1==0 && b1==0 && c1==0){ cout<<-1; return 0; }
// if(a2==0 && b2==0 && c2==0){ cout<<-1; return 0; }

// line
if(a1*b2-a2*b1!=0) cout<<1; // intersect
else if(a1*c2-a2*c1==0 && b1*c2-b2*c1==0) cout<<-1; // parallel
else cout<<0;

return 0;
}

条件の式は直線だから、要素の数は 0, 1, ∞ のいずれか。
線形代数の知識から、係数行列の determinant が非零だったら2直線は交差する。そうでないとき、右辺のベクトルが係数行列の range に入っていれば方程式は無限個の解をもつ。簡単。

かと思いきや、たとえば A1=B1=0,C1≠0 のときは条件を満たす(x,y)が存在しないので空集合となり交点なし。
結局、場合分けして解くわけですが、場合わけの仕方を間違えるとバリエーションが増えすぎて大変なことに。
競技中に書いたコードはhackこそされなかったものの、どこかで漏れがあったらしく、Wrong Answer でした。
再考して書き直したのが↑のコードです。コメントアウトしている部分はあったほうが分かりやすいので残していますが、結局あとの処理に含まれているので必要ないですね。

C. (時間外)
int main(){
int n,a[100000],sum=0; scanf("%d",&n);
rep(i,n){ scanf("%d",a+i); sum+=a[i]; }

if(sum%3!=0){ puts("0"); return 0; }

sum/=3;
int rcnt[100000];
for(int i=n-1,psum=0;i>=0;i--){
psum+=a[i];
rcnt[i]+=(i<n-1?rcnt[i+1]:0)+(psum==sum);
}

ll ans=0;
for(int i=0,psum=0;i<n-2;i++){
psum+=a[i];
if(psum==sum) ans+=rcnt[i+2];
}
printf("%I64d\n",ans);

return 0;
}

書いた。
submit.
0 0 0 0 0 … 0 という最大ケースを投げられて TLE.

[ 2011/03/21 追記 ]

↑ この頃は、O(n2) 解法では TLE になることも分からなかったのか。

解いた。
また、問題文を読み間違えていたので修正。

方針は DP.
数列の右から左へ部分和をとっていって、その時点より右にいくつの区切りを入れられるかを rcnt に記録していく。
その後、数列の左から右へ部分和をとっていって、区切りを入れられるポイントが現れるたびに答えに加えていく。
全体で O(n).

D. (時間外)
template <class T> struct Edge{
int u,v;
T w;
Edge(){}
Edge(int U,int V,T W):u(U),v(V),w(W){}
bool operator<(const Edge &e)const{ return w<e.w; }
};

template <class T>
struct AdjMatrix:public vector< vector<T> >{
AdjMatrix(){}
AdjMatrix(int n,const vector<T> &v=vector<T>()):vector< vector<T> >(n,v){}
template <class U> AdjMatrix(U b,U e):vector< vector<T> >(b,e){}
};

template <class T>
struct AdjList:public vector< vector< Edge<T> > >{
AdjList(){}
AdjList(int n,const vector< Edge<T> > &v=vector< Edge<T> >()):vector< vector< Edge<T> > >(n,v){}
template <class U> AdjList(U b,U e):vector< vector< Edge<T> > >(b,e){}
};

template <class T>
T MinimumWeightPerfectMatching(const AdjMatrix<T> &adj){
int n=adj.size();
vector<T> dp(1<<n,INF); dp[0]=0;
rep(S,1<<n){
rep(u,n)if(!(S&(1<<u))){
rep(v,u)if(!(S&(1<<v))){
dp[S+(1<<u)+(1<<v)]=min(dp[S+(1<<u)+(1<<v)],dp[S]+adj[u][v]);
}
}
}
return dp[(1<<n)-1];
}

template <class T>
T ChinesePostman(const AdjList<T> &adj){
int n=adj.size();

AdjMatrix<T> wf(n,vector<T>(n,INF));
rep(u,n){
wf[u][u]=0;
rep(i,adj[u].size()){
int v=adj[u][i].v;
wf[u][v]=min(wf[u][v],adj[u][i].w);
}
}
rep(k,n)rep(i,n)rep(j,n) wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
for(int u=1;u<n;u++) if(adj[u].size()>0 && wf[0][u]==INF) return -1;

vi odd;
T total=0;
rep(u,n){
if(adj[u].size()%2==1) odd.pb(u);
rep(i,adj[u].size()) total+=adj[u][i].w;
}

int n_odd=odd.size();
AdjMatrix<T> oddadj(n_odd,vector<T>(n_odd));
rep(u,n_odd)rep(v,n_odd) oddadj[u][v]=wf[odd[u]][odd[v]];

return total/2+MinimumWeightPerfectMatching(oddadj);
}

int main(){
int n,m; scanf("%d%d",&n,&m);
AdjList<int> adj(n);
rep(i,m){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
u--,v--;
adj[u].pb(Edge<int>(u,v,w));
adj[v].pb(Edge<int>(v,u,w));
}

printf("%d\n",ChinesePostman(adj));

return 0;
}

[ 2011/03/22 追記 ]

解いた。
頂点 1 から出発すること以外は、中国人郵便配達問題そのまま。
まじめにやるなら一般グラフの最小重み最大マッチング問題を解かないといけないけど、今回はノード数が少ないので、DP やバックトラックによる指数時間の解法でも間に合う。

DP は Spaghetti Source を参考にした。
最近になってなぜかこのサイトが消えてしまったけど、Google のキャッシュを探せばまだ見られる。

今後のためにも、隣接行列クラスと隣接リストクラスを作ろうとした (vector を typedef するだけだけど) ら、C++ では typedef テンプレートが使えないということでひどい目にあった。
次善策として、vector を継承したクラスを作って、必要なコンストラクタをべた書きすることにした。
この問題についてはここが詳しい。



結局 0 完。
今回は、考えに漏れが出るような問題が多かったように思います。
競技のルール的にも、そのほうがたくさん撃墜できておもしろいのかも。
なお、Codeforces Alpha では Rating は変わらないようです。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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