スポンサーサイト

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

KUPC 2011

8/6 13:00~18:00
京都大学プログラミングコンテスト (KUPC) にオンサイトで参加しました。

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

結果

A. AC (00:02)
B. AC (00:07)
C. 2WA, AC (00:24)
D. 3WA
E. 2WA
F. -
G. -
H. -
I. 3WA
J. -

Standing : 57/136


コンテスト中

A. KUPC を数えなさい

ゆっくり問題文を読む。
まぁ、さすがに A は易しい。
書いた。
submit.
あ、手元でコンパイルするの忘れた。
でも通ったからいいや。

First Acceptance かも!? とか思ったけど全然そんなことなかった。

次。

B. 蝉

後戻りしない最短コストの道をみつけなさい。
みつけた。
ふつうの DP。
submit.

次。

C. AI としりとり

interactive な問題きた!
AI は 2 文字以下の文字列しか答えない。
質問回数を最小化したいので、末尾が同じ文字になるように答えればいいよね。
submit.
WA.
なんでだ。問題文を読み直す。
AI が 1 文字を返す場合を忘れていた。
submit.
WA.
さらに直す。
submit.
AC.

やった。次。

D. 条件に合うような 0, 1 の数列をみつける

全然わからない。
急に難易度あがりすぎじゃないか?

Greedy でできるような気がするけど、具体的にどうやればいいのかさっぱり。
数字が重複してるところから優先的に選ぶのはなかなか good だけど、それだけだと反例があるしなぁ。 ( 嘘

一向に進展しないので、Greedy のような謎コードを投げてみるも WA.
以降進展せず。

コンテスト終了後、想定解を聞いて驚愕。
たしかに、解がいっぱいあるだろうことは想像できるけど...

E. しえる

しえるさんきた。
作為的な constraints から察するに、区間ふるい的なことをやるのかな。
でも、区間ふるいだと素数判定ができるだけだし、そもそも区間ふるい書いたことないし。
わからん。

もしかして、B ≦ 5×105 という制約はひっかけで、
(1 から A+B までの Fox Number) - (1 から A-B-1 までの Fox Number)
でやるんじゃないかとか考え始める。
わからん。
まぁ、そんなわけないか。

やることがないので、とりあえず DFS で全探索するコードを書いてみる。
サンプルは通るけど、もちろん大きいケースでは返ってこない。
わからん。

ここらで、残りの問題を全部読んでみた。

F. ボ~ル

なんかできそう。
とりあえず、原点を通る円の接線を考えて、区間の問題に帰着できることはすぐにわかる。

また、別の区間に完全に含まれるような区間は考えなくていい。

これら n 個の区間から k 個を選んで覆う長さを最大化したい。

DP 臭がする。
区間を右端でソートして、左から DP テーブルを埋めていく。
あ、でも 3 つ以上の区間が互いに重なるということはありえるのか。
AAAAA
 BBBBB
  CCCCC

みたいなケース。
このようなケースをうまく処理できない。
O(k n) ではできない。 (と思う)

惜しいところまで行ってる気がするけどダメだ。

G. XOR

10000 個も候補があるのに 200 回しか質問できないとか無理ゲー、とか思った。

H. うなぎを焼く

難しそうなので考えてない。

I. 京都の山々

これはまだとっかかりがつかめそう。

まず、行と列は完全に分離して考えられることがわかる。
なので、行について山を作って、そのあと列について山を作るという方針でいい。

行について山を作れるかどうかはどうすればわかるか?
行を大きい順にソートして、大きいものから順に処理していく。
一番大きいのを真ん中において、左右にどんどんくっつけていく。
左右どちらにもくっつけられるときは、前回くっつけた側と同じ側にくっつけるようにした。(そうするほうが得だと思ったから)

この方針でサンプルはすべて合ったので、submit.
AC!!

ここで、「 I はあとからリジャッジします」 というメッセージを発見。
不吉な予感がする。

rejudged.
案の定というかなんというか、落ちた。
59 番目のテストケース 1 つだけで WA が出ていたので、なにかコーナーケースがあるのかと思って探していたけど、何も思いつかなかった。

どうやら、「左右どちらにもくっつけられるときは前回と同じ側にくっつける」 という greedy 戦略がそもそも悪かったらしい。
反例はまだ自力で見つけられてないけど。

想定解は DAG の最小パス被覆。
聞いた瞬間に納得。
DAG の最小パス被覆は POJ で何問も類題を解いていたのに、コンテスト中はまったく気付かなかった。
(自分の発想力が) 残念すぎる...

J. チェスのナイトで mod がどうとか

どうせ一番難しい問題だと思ったので考えてない。

コンテスト以外

すごい人たちや twitter で親しくしてくれている人たちに会えた。
何人かに対しては積極的に話しに行ってみたり。
本当は、斜め後ろの席にいたすごい方とも話したかったけど、きっかけがつかめなくて断念。

リアルでは競技プログラミングの話をする機会がほとんどないので、すごく新鮮で楽しかった。

あと、ICPC アジア予選に対するモチベーションがすごく上がった。

運営の方々、楽しいコンテストをありがとうございました。
来年もまた開催されることを期待しています。

ソースコード

解けた問題だけ。
A.
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
char s[301]; gets(s);
int hist[128]={};
for(int i=0;s[i];i++) hist[s[i]]++;
printf("%d\n",min(min(hist['K'],hist['U']),min(hist['P'],hist['C'])));
return 0;
}


B.
#include<cstdio>
#include<algorithm>

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

using namespace std;

const int INF=1<<29;

int main(){
int h,w; scanf("%d%d ",&h,&w);
char grid[50][51];
rep(i,h) gets(grid[i]);

int dp[50][50];
dp[0][0]=0;
rep(i,h) rep(j,w) if(i>0 || j>0) {
dp[i][j]=INF;
if(i>0) dp[i][j]=min(dp[i][j],dp[i-1][j]+grid[i][j]-'0');
if(j>0) dp[i][j]=min(dp[i][j],dp[i][j-1]+grid[i][j]-'0');
}
printf("%d\n",dp[h-1][w-1]);

return 0;
}


C.
#include<cstdio>

using namespace std;

int main(){
puts("?a"); fflush(stdout);

bool used[128]={};
while(1){
char s[3]; scanf("%s",s);
if(s[1]=='\0' || s[0]!='a' || used[s[1]]){ puts("!OUT"); break; }
used[s[1]]=true;

if(s[1]=='a') puts("?aaa");
else printf("?%ca\n",s[1]);
fflush(stdout);
}

return 0;
}


D. (あとで解いた)
#include<cstdio>
#include<algorithm>

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

using namespace std;

int main(){
int n,k; scanf("%d%d",&n,&k);
static int card[500][500];
rep(i,k) rep(j,n/2) scanf("%d",card[i]+j), card[i][j]--;

int seq[1000];
rep(i,n) seq[i]=(i<n/2?0:1);
while(1){
bool ok=true;
rep(i,k){
int cnt=0;
rep(j,n/2) if(seq[card[i][j]]==1) cnt++;
if(cnt<n/8 || 3*n/8<cnt){ ok=false; break; }
}
if(ok) break;

random_shuffle(seq,seq+n);
}

rep(i,n) printf("%d",seq[i]); putchar('\n');

return 0;
}


E. (2011/08/12 追記)
#include<cstdio>
#include<vector>
#include<algorithm>

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

using namespace std;

typedef long long ll;

const int INF=1<<29;

int main(){
// Eratosthenes Sieve
const int Ne=1000000;
static bool er[Ne+1]; er[0]=er[1]=true;
for(int i=2;i*i<=Ne;i++) if(!er[i]) for(int j=i*i;j<=Ne;j+=i) er[j]=true;
vector<int> p; rep(i,Ne+1) if(!er[i]) p.push_back(i);

ll a,b; scanf("%lld%lld",&a,&b);

// (a, b) <- (max(a-b,2), a+b)
b+=a;
a=max(2*a-b,2LL);

// Prime Factorization
static int e[1000001];
fill(e,e+b-a+1,INF);
rep(i,p.size()){
int pr=p[i];
for(ll j=(a+pr-1)/pr*pr;j<=b;j+=pr){
if(e[j-a]==-1) continue;

ll jj=j;
int cnt=0;
do{
jj/=pr;
cnt++;
}while(jj%pr==0);

e[j-a]=(e[j-a]<cnt?-1:cnt);
}
}

printf("%lld\n",(b-a+1)-count(e,e+b-a+1,-1));

return 0;
}


F. (2012/01/17 追記)
const double EPS=1e-9;
const double INF=1e77;
const double PI=acos(-1);

template<class T> struct interval{
T a,b;
bool operator<(const interval &I)const{ return a<I.a; }
};

int main(){
int n,k; scanf("%d%d",&n,&k);
interval<double> I[1500];
rep(i,n){
double x,y,r; scanf("%lf%lf%lf",&x,&y,&r);
double theta=asin(r/sqrt(x*x+y*y));
double phi=atan2(y,x);
I[i].a=phi-theta;
I[i].b=phi+theta;
if(I[i].a<-PI-EPS){ // 例外ケース (区間が x 軸の負の方向をまたぐ)
I[i].a+=2*PI;
I[i].b+=2*PI;
}
I[i].a=max(I[i].a,0.);
I[i].b=min(I[i].b,PI);
if(I[i].a+EPS>I[i].b) i--, n--; // 上半平面と共通部分を持たない区間は除外
}

// 完全に覆われている区間を除去
rep(i,n){
bool cov=false; // I[i] がある I[j] に覆われているかどうか
rep(j,n) if(i!=j && I[j].a<I[i].a+EPS && I[i].b<I[j].b+EPS) cov=true;
if(cov){
swap(I[i],I[n-1]);
i--;
n--;
}
}
sort(I,I+n);

// pre[i] := 区間 i より左にあり、区間 i と共通部分を持つ区間のうち一番左にあるものの番号 (存在しなければ -1)
int pre[1500];
rep(i,n){
pre[i]=-1;
rep(j,i) if(I[i].a+EPS<I[j].b) { pre[i]=j; break; }
}

// dp1[i+1][j] := i 個目まで見て、そのうち j 個を選んだときの解 (選んだ区間の和集合の長さ)
// dp2[i+1][j] := i 個目まで見て、そのうち j 個を選んだ、最後に i を選んだときの解
static double dp1[1501][1501];
static double dp2[1501][1501];
rep(i,n+1) rep(j,k+1) {
dp1[i][j]=-INF;
dp2[i][j]=-INF;
}
dp1[0][0]=dp2[0][0]=0;
rep(i,n){
rep(j,k+1){
// i 個目の区間を選ばない
dp1[i+1][j]=max(dp1[i+1][j],dp1[i][j]);

// i 個目の区間を選ぶ
if(j>0){
int l;
double w;
// 最後に使った区間が区間 i とかぶる場合、一番左の区間だけを見ればいい
if(~pre[i]){
l=pre[i];
w=I[i].b-I[l].b;
dp1[i+1][j]=max(dp1[i+1][j],dp2[l+1][j-1]+w);
dp2[i+1][j]=max(dp2[i+1][j],dp2[l+1][j-1]+w);
}

// 最後に使った区間が区間 i とかぶらない場合
l=(~pre[i]?pre[i]-1:i-1);
w=I[i].b-I[i].a;
dp1[i+1][j]=max(dp1[i+1][j],dp1[l+1][j-1]+w);
dp2[i+1][j]=max(dp2[i+1][j],dp1[l+1][j-1]+w);
}
}
}
printf("%.15f\n",*max_element(dp1[n],dp1[n]+k+1)/PI);

return 0;
}

解説スライドを見ながら解いた。
方針もまったく同じ。
言われてみればああそうかという感じだけど、なかなか自分では思いつかないなぁ。

G. (2012/01/17 追記)
int dfs(int l,int r,int n,const int *bit){
if(l==r-1) return l;

putchar('?');
rep(i,n){
if (l<=i && i<(l+r)/2) putchar('0'+bit[i]);
else if(i<=(l+r)/2 && i<r) putchar('0');
else putchar('0');
}
putchar('\n'); fflush(stdout);

int v; scanf("%d",&v);
return v?dfs(l,(l+r)/2,n,bit):dfs((l+r)/2,r,n,bit);
}

int main(){
srand(777);
int n,k; scanf("%d%d",&n,&k);
int ans[10];
rep(t,k){
int bit[10000];
while(1){
putchar('?');
rep(i,n){
if(count(ans,ans+t,i)) bit[i]=0;
else bit[i]=rand()&1;
putchar('0'+bit[i]);
}
putchar('\n'); fflush(stdout);

int v; scanf("%d",&v);
if(v) break;
}

ans[t]=dfs(0,n,n,bit);
}

printf("!");
rep(t,k) printf("%d%c",ans[t]+1,t<k-1?' ':'\n');

return 0;
}

解いた。
解説スライドの解法 1 そのまま。
おもしろい。

I. (2012/05/03 追記)
const int V_MAX=1000;

bool augment(int u,bool *vis,int match[2][V_MAX],const vector<int> *G){
if(u==-1) return true;

rep(i,G[u].size()){
int v=G[u][i];
if(!vis[v]){
vis[v]=true;
if(augment(match[1][v],vis,match,G)){
match[0][u]=v;
match[1][v]=u;
return true;
}
}
}
return false;
}

int bipartite_matching(int L,int R,const vector<int> *G){
static int match[2][V_MAX];
rep(u,L) match[0][u]=-1;
rep(v,R) match[1][v]=-1;

int res=0;
static bool vis[V_MAX];
rep(u,L){
rep(v,R) vis[v]=false;
if(augment(u,vis,match,G)) res++;
}
return res;
}

bool solve(int h,int w,const int a[1000][1000]){
vector<int> G[1000];
rep(i1,h) rep(i2,h) {
bool ok=true;
rep(j,w) if(a[i1][j]<=a[i2][j]) { ok=false; break; }
if(ok) G[i1].push_back(i2);
}

bool top=false; // 山頂が存在するかどうか
rep(i,h) if(G[i].size()==h-1) top=true;

return top && h-bipartite_matching(h,h,G)<=2;
}

int main(){
int h,w; scanf("%d%d",&h,&w);
static int a1[1000][1000],a2[1000][1000];
rep(i,h) rep(j,w) scanf("%d",a1[i]+j), a2[j][i]=a1[i][j];

puts(solve(h,w,a1)&&solve(w,h,a2)?"YES":"NO");

return 0;
}

コンテスト当日に解説を聞いていたので、思い出しながら解いてみた。
二部グラフの構築に O(n^3) かかっているけど、AOJ が爆速なので通ってしまった。
旧 AtCoder だと TLE していたと思う。
スポンサーサイト

コメントの投稿

非公開コメント

やはり4問以降が壁…。

私はオンサイトにはいけませんでしたが、ネットで参加していました。

やはり4問以降が壁なのでしょうか。とけていらっしゃるのかな?と思っていたのですが、3問の正解ということで驚きました。

乱択に度肝を抜かれましたが、面白いコンテストでしたよね。難易度が急上昇しますけど。

Re: やはり4問以降が壁…。

4 問目も解きたかったのですが、力及ばず。
D. の乱択解法が思いつけるくらいの柔軟さがほしいです。

tatsuyan さんとも機会があれば一度お会いしてみたいです。
プロフィール

fura2

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

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

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