スポンサーサイト

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

hos' Xmas Contest 2010

hos さん主催 Xmas Contest 2010 の参加記録です。
私が参加した夜の部は、2010-12-25 (土) 22:00 ~ 26:00 に行われました。
途中、バグがとれなくて苦しいときもありましたが、4 時間がっつりと問題に取り組めて楽しかったです。

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

結果

A. WA (60/100)
B. AC (100/100)
C. WA (40/100)
D. -
E. -
F. -
G. -
H. AC (100/100)
Standing : 44/99

考えたこと

A.
A 問題だから簡単なはず。
ゆっくり考えて 15 分くらいで書き上げる。
Submit.
.
.
.
No - 60% Accepted.

だいたいあってる。
多分、コーナーケースを忘れてるんだろうなぁとは思ったけど、分からなかったので B へ行く。

B.
構文解析かと思いきや、
実は,答えることが要求されているのは,計算結果が偶数か奇数かだけである.
と、問題文中にあるように、そんなことはしなくていい。

数式に現れる演算子は +, - の 2 種類だけであることに注目する。
偶数 ± 偶数 = 偶数
偶数 ± 奇数 = 奇数
奇数 ± 奇数 = 偶数
だから、結局、入力中に現れる奇数の個数の偶奇を調べればいい。
Submit.
.
.
.
Yes - Accepted.

C.
問題をざっと読んで、
「絶対に選ばなければいけないアクセサリが 10 個以下」だと勘違い。
これは、最近本で読んだばかりの、最小 Steiner 木問題だ!!

といっても解法は知らなかったので、とりあえず Spaghetti Source を見てみると、ノード数が 11 以下程度なら間に合う指数時間の DP が載ってる。
これだ!!
Ctrl+C, Ctrl+V.
前原氏のコードで使われている行列マクロとかを適当に修正。
サンプルが通る。
Submit.
.
.
.
No - Wrong Answer.

あれ?
そもそも DP の中身を理解していないので、何が違うのかさっぱり分からない。

採点用データのうち配点の 40% 分については,N <= 10 を満たす.
と問題文にあるので、とりあえず部分点がとれそうな戦略
「答えとしてありうる最小全域木を全部調べる」
に切り替える。

実際これが正解だったみたいだけど、問題を読み間違えているので変なところで Runtime Error が出る。
RE の原因なんて大抵は配列の範囲外アクセスなので、丹念にチェックしてみるもおかしいところがまるで分からない。

いたるところに while(1){} を突っ込んで超デバッグ。
この方法だと、結果が RE か TLE のどちらになったかで原因を絞れる。(負荷かけてごめんなさい
18WA くらいしたところで、問題の読み間違えに部分的に気付いた。
しかしまだ微妙に勘違いしている。

プログラムを修正して Submit.
.
.
.
No - 40% Accepted.

部分点が取れたので、この問題はもう諦めて、解いている人が多い H へ。

H.
変な問題。

入力として与えられるのは A~G のどれかの入力データであり、どれにも当てはまらないものは来ない。
なので、とりあえず最後の行を調べてやれば、A, D, G 以外は特定できる。
D は、2行目にある数が 3 つかどうかで判定できる。
G は、データセットの数と値の範囲で判定できる。
A は、「G ならば A」なので、「A または G」だと分かった瞬間に A であると分かる。

Submit.
.
.
.
Yes - Accepted.

ここでコンテスト終了。
競技時間の半分以上は C 問題でつぶれました。



コンテストが終わってから 他の参加者のブログを見て、

A.
c==d がコーナーケースだと知った。これは気付かなかった。

C.
問題をようやく正しく理解した。
教訓 : 問題をちゃんと読みましょう。


解答


A.
#include<cstdio>
#include<cstdlib>
#include<algorithm>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){
for(int a,b,c,d;scanf("%d%d%d%d",&a,&b,&c,&d),a;){
if(a>b) swap(a,b);

int l,ans;
l=(c==d)?(c+d):abs(c-d);
ans=l/(a+b)*2;
l%=a+b;
if(b<=l) ans++;
printf("%d ",ans);

l=c+d;
ans=l/(a+b)*2+1;
l%=a+b;
if(a<=l) ans++;
printf("%d\n",ans);
}

return 0;
}


B.
#include<string>
#include<iostream>

#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

int main(){
for(string expr;cin>>expr,expr!="#";){
bool ans=0;
int len=expr.size();
rep(i,len){
if(isdigit(expr[i])){
if(i==len-1 || !isdigit(expr[i+1])){
int num=expr[i]-'0';
if(expr[i]%2==1) ans=!ans;
}
}
}
cout<<(ans?"ODD":"EVEN")<<endl;
}

return 0;
}


C.
#include<queue>
#include<cstdio>
#include<vector>

#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

const int INF=1<<29;

int main(){
for(int n,m;scanf("%d%d",&n,&m),n;){
vi cand,nece;
rep(i,n){
int s; scanf("%d",&s);
if(s) cand.pb(i);
else nece.pb(i);
}
vector<pii> adj[100];
rep(i,m){
int a,b,c; scanf("%d%d%d",&a,&b,&c);
a--,b--;
adj[a].pb(mp(b,c));
adj[b].pb(mp(a,c));
}

int ans=INF;
rep(stat,1<<cand.size()){
bool use[100]={};
int nodenum=nece.size();
rep(i,nece.size()) use[nece[i]]=true;
rep(i,cand.size()) if(stat&(1<<i)) use[cand[i]]=true,nodenum++;
int s=nece[0];

int totalcost=0,usedcnt=0;
bool visited[100]={};
priority_queue< pii,deque<pii> > pq; pq.push(mp(0,s));
while(!pq.empty()){
pii a=pq.top(); pq.pop();
int cost=-a.first,u=a.second;
if(visited[u]) continue;
visited[u]=true;
totalcost+=cost;
usedcnt++;

rep(i,adj[u].size()){
int v=adj[u][i].first,nextcost=adj[u][i].second;
if(use[v] && !visited[v]) pq.push(mp(-nextcost,v));
}
}
if(nodenum==usedcnt) ans=min(ans,totalcost);
}

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

return 0;
}

最小全域木を求めるのには Prim 法を使用。
隣接リストを使ったり、priority_queue の実装に deque を使ったりと色々マイナーチューンをしてみたものの、このコードでは 90% の部分点しかもらえない。(テストケース 8 で TLE)
Kruskal 法で書いたら間に合ったんだろうか?

H.
#include<string>
#include<vector>
#include<sstream>
#include<iostream>

#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;

typedef vector<int> vi;

bool isA(vector<string> in){
int h=in.size();
if(in[h-1]!="0 0 0 0") return false;
int cnt=0;
rep(i,in[1].length()) if(in[1][i]==' ') cnt++;
if(cnt==2) return false;

if(h>101) return false;
return true;
}

bool isB(vector<string> in){
int h=in.size();
return in[h-1]=="#";
}

bool isC(vector<string> in){
int h=in.size();
return in[h-1]=="0 0";
}

bool isD(vector<string> in){
int h=in.size();
if(in[h-1]!="0 0 0 0") return false;
int cnt=0;
rep(i,in[1].length()) if(in[1][i]==' ') cnt++;
return cnt==2;
}

bool isE(vector<string> in){
int h=in.size();
return in[h-1]=="0";
}

bool isF(vector<string> in){
int h=in.size();
return in[h-1]=="0 0 0";
}

bool isG(vector<string> in){
int h=in.size();
if(in[h-1]!="0 0 0 0") return false;
int cnt=0;
rep(i,in[1].length()) if(in[1][i]==' ') cnt++;
if(cnt==2) return false;

if(h>21) return false;
bool ok=true;
rep(i,h-1){
stringstream ss(in[i]);
int n,m,a,b; ss>>n>>m>>a>>b;
if(!(1<=n&&n<=100000 && 1<=m&&m<=100000 && 1<=a&&a<=n && 1<=b&&b<=n)){ ok=false; break; }
}
return ok;
}

int main(){
while(1){
vector<string> in;
for(string s;getline(cin,s);){
if(s=="@@@@@@@@@@@@@@@@@@@@") return 0;
if(s=="@@@@@@@@@@") break;
in.pb(s);
}

vector<char> ans;
if(isA(in)) ans.pb('A');
if(isB(in)) ans.pb('B');
if(isC(in)) ans.pb('C');
if(isD(in)) ans.pb('D');
if(isE(in)) ans.pb('E');
if(isF(in)) ans.pb('F');
if(isG(in)) ans.pb('G');
if(ans.size()>=2) cout<<'?'<<endl;
else cout<<ans[0]<<endl;
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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