スポンサーサイト

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

School Regional Team Contest, Saratov, 2011

2011/10/18 15:30~20:30 (JST)
Codeforces で行われた School Regional Team Contest, Saratov, 2011 の参加記録

参加したのに書くのを忘れていた。

Tags : プログラミング Codeforces

結果

A. AC (00:09)
B. AC (00:18)
C. AC (00:22)
D. AC (00:55)
E. 2WA, AC (02:47)
F. AC (01:40)
G. WA, AC (02:27)
H. 2WA
I. -
J. AC (03:49)
Standing : 140/1175
Rating : 19351908


問題

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

A. Elevator

前後に扉がついたエレベーターがある。
エレベーター内部の左右には手すりがついている。

ある人がどちらの扉から入ってどちらの手すりを掴んだかという情報が与えられるので、その人の利き手を答えよ。

B. Quiz League

n 個のスロットをもつルーレットがある。
各スロットは、すでに選ばれたか選ばれていないかのいずれか。

ルーレットがすでに選ばれたスロットを指したときは、その位置から時計回りにみたときにはじめて現れる、まだ選ばれていないスロットが選ばれる。

今、ルーレットが k 番目のスロットを指している。
何番目のスロットが選ばれるか?

1 ≦ k ≦ n ≦ 1000

C. Winnie-the-Pooh and honey

n 個の壺がある。
壺 i には a_i 単位の蜂蜜が入っている。
壺に入っている蜂蜜が k 未満になるまで、蜂蜜をちょうど k 単位だけ食べつづける。
蜂蜜は全部あわせてどれだけ残ったか?

1 ≦ n, k, a_i ≦ 100

D. Three Sons

n × m の土地がある。
土地の各マス (i, j) からは c_i,j トンのとうもろこしが収穫できる。

土地に 2 本の直線を引いて、土地を三分割する。
引く線は 2 本とも垂直か、2 本とも水平かのいずれかでないといけない。

土地の各部分のとうもろこしの量がそれぞれ A, B, C トンになるような分割は何通りあるか?

1 ≦ n, m ≦ 50
max(n, m) ≧ 3
0 ≦ c_i,j ≦ 100
0 ≦ A, B, C ≦ 10^6

E. Put Knight!

n × n のチェス盤に 2 人で順番にナイトを置いていく。
ナイトは、すでに置いてあるどのナイトにも取られないような位置に置かなければいけない。
両プレイヤーが最善を尽くすとき、どちらのプレイヤーが先にナイトを置けなくなるか?

1 ≦ n ≦ 10000

F. Spiders

n 個の木が与えられる。
木の 1 つの頂点と別の木の 1 つの頂点をくっつけて、大きな 1 つの木を作る。 ( 問題文中の図を参照 )
できた木の直径は最大でいくつになるか?

G. Boom

n チームで Boom と呼ばれるゲームをする。
各チームは 2 人からなる。
Boom とは、1 人がカードに書かれているジェスチャをして、もう 1 人がカードの内容を当てるゲームである。

各カードの説明の難しさ、プレイヤーが説明・解釈する能力の高さが与えられるので、ゲームをシミュレーションし、各チームが当てたカードのリストを答えよ。

1 ≦ n ≦ 100

H. Brevity is Soul of Wit

n 個の単語が与えられる。
各単語から 1 文字以上 4 文字以下の部分列を抜き出す。
抜き出した n 個の部分列がどの 2 つも等しくないようにできるか?
できる場合は、n 個の部分列の具体例を 1 つ求めよ。

1 ≦ n ≦ 200

I. Luck is in Numbers

0 以上 9 以下の自然数 A, B について、
f(A, B) := A, B をデジタル表記したときに共通している黒線の本数
とする。 ( 問題文中の図を参照 )

2n 桁の自然数 C が与えられる。

C の i 桁目を C[i] と書く。
C の幸福度 g (C) を
g (C) := Σ[i=1 to n] f (C[i], C[i+n])
と定める。

2n 桁の自然数 D で
・ C < D
・ g (C) < g (D)
となるもののうち、最小のものを求めよ。
そのような D が存在しないときは -1 と答えよ。

1 ≦ n ≦ 105

J. Minimum Sum

n 個のベクトル v_i = (x_i, y_i) が与えられる。

v_i は各座標方向に反転してもよい。
すなわち
v_i = (x_i, y_i), (x_i, -y_i), (-x_i, y_i), (-x_i, -y_i)
の中から好きなものを採用してよい。

ユークリッド距離 | v_i + v_j | の最小値を求めよ。

1 ≦ n ≦ 10^5
-10^4 ≦ x_i, y_i ≦ 10^4

解答

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

A.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

char s[8];
int a; scanf("%s%d",s,&a);

puts(s[0]=='f'^a==1?"R":"L");

return 0;
}

問題文が読めなかったけど、適当に推測して出したら通った。

B.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n,k,a[1000]; scanf("%d%d",&n,&k); k--;
rep(i,n) scanf("%d",a+i);

for(;a[k]==0;k=(k+1)%n);

printf("%d\n",k+1);

return 0;
}

問題文長い。

C.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n,k; scanf("%d%d",&n,&k);
int ans=0;
rep(i,n){
int a; scanf("%d",&a);
rep(j,3) if(a>=k) a-=k;
ans+=a;
}
printf("%d\n",ans);

return 0;
}

問題文長いのいや

D.
int w[50][50];

int sum(int t,int l,int b,int r){
int res=0;
for(int i=t;i<b;i++) for(int j=l;j<r;j++) res+=w[i][j];
return res;
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int m,n; scanf("%d%d",&m,&n);
rep(i,m) rep(j,n) scanf("%d",w[i]+j);
multiset<int> A;
rep(i,3){
int a; scanf("%d",&a);
A.insert(a);
}

int ans=0;
for(int i=1;i<m;i++) for(int k=i+1;k<m;k++) {
multiset<int> S;
S.insert(sum(0,0,i,n));
S.insert(sum(i,0,k,n));
S.insert(sum(k,0,m,n));
if(S==A) ans++;
}
for(int j=1;j<n;j++) for(int l=j+1;l<n;l++) {
multiset<int> S;
S.insert(sum(0,0,m,j));
S.insert(sum(0,j,m,l));
S.insert(sum(0,l,m,n));
if(S==A) ans++;
}

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

return 0;
}

最初、縦に切ってから横に切るのも OK だと思って、再帰でがんばって書いてしまった。
長方形の和は前処理しなくても間に合う。

E.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int T; scanf("%d",&T);
for(int n;T--;) scanf("%d",&n), printf("%d\n",1-n%2);

return 0;
}

相手の手を真似すればいい。
n が奇数のときは天元をつぶしておく。

この戦略が使えることはちょっと実験してみればわかる。
たとえば、クイーンとかならこの戦略が使えない。

F.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int ans=0;
int t; scanf("%d",&t);
while(t--){
int n,m; scanf("%d",&n); m=n-1;

int wf[100][100];
rep(u,n) rep(v,n) wf[u][v]=(u==v?0:INF);
rep(i,m){
int u,v; scanf("%d%d",&u,&v); u--; v--;
wf[u][v]=wf[v][u]=1;
}

rep(k,n) rep(i,n) rep(j,n) wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);

int tmp=0;
rep(i,n) rep(j,n) if(wf[i][j]<INF) tmp=max(tmp,wf[i][j]);
ans+=tmp;
}
printf("%d\n",ans);

return 0;
}

明らかに、それぞれの木の直径の総和が答え。
木の直径は高速に計算できるけど、このサイズなら Warshall-Floyd でいい。

G.
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n,t_ini; scanf("%d%d",&n,&t_ini);
int a[100][2],b[100][2];
rep(i,n) rep(j,2) scanf("%d%d",a[i]+j,b[i]+j);

int m; scanf("%d",&m);
char card[100][21];
int c[100];
rep(k,m) scanf("%s%d",card[k],c+k);

int d[100][100]={};
bool got[100]={};
vector<string> ans[100];
for(int i=0,j=0,k=0;;){
int t=t_ini,q=1-j;
while(t>0){
int need=max(1,c[k]-(a[i][j]+b[i][q])-d[i][k]);
if(t>=need){
got[k]=true;
ans[i].push_back(card[k]);
t-=need;
}
else{
d[i][k]+=t;
t=0;
}

if(count(got,got+m,true)==m) goto END;

do{ k=(k+1)%m; }while(got[k]!=0);
}

if(i<n-1) i++;
else i=0, j=q;
}

END:
rep(i,n){
printf("%d",ans[i].size());
rep(j,ans[i].size()) printf(" %s",ans[i][j].c_str());
putchar('\n');
}

return 0;
}

問題文どおりにシミュレーション。

H. ( あとで解いた )
bool augment(int u,vector<bool> &visited,const vector< vector<int> > &adj,vector<int> match[2]){
if(u==-1) return true;

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

int BipartiteMatching(const vector< vector<int> > &adj,int R,vector<int> match[2]){
int L=adj.size();

match[0].assign(L,-1);
match[1].assign(R,-1);

int ans=0;
vector<bool> visited(R);
rep(u,L){
rep(v,R) visited[v]=false;
if(augment(u,visited,adj,match)) ans++;
}
return ans;
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

static string dec[500000];

int n; cin>>n;
vector<int> h[200];
rep(i,n){
string t; cin>>t;
int m=t.length();
rep(S,1<<m){
string r;
int hash=0,d=1,pc=0;
rep(j,m) if(S&(1<<j)) {
r+=t[j];
hash+=(t[j]-'a'+1)*d;
d*=26;
pc++;
}
if(1<=pc && pc<=4){
dec[hash]=r;
h[i].push_back(hash);
}
}

sort(h[i].begin(),h[i].end());
h[i].erase(unique(h[i].begin(),h[i].end()),h[i].end());
}

int nf=0,finv[80000];
map<int,int> f;
rep(i,n) rep(j,h[i].size()) if(f.count(h[i][j])==0) {
f[h[i][j]]=nf;
finv[nf++]=h[i][j];
}

vector< vector<int> > adj(n);
rep(i,n) rep(j,h[i].size()) adj[i].push_back(f[h[i][j]]);

vector<int> match[2];
if(BipartiteMatching(adj,nf,match)<n) cout<<-1<<endl;
else{
rep(i,n) cout<<dec[finv[match[0][i]]]<<endl;
}

return 0;
}

ありうる部分列を全部生成して、元の文字列の集合と部分列の集合で二部マッチングする。
なぜ本番中は気づかなかったのか...

I. ( あとで解いた )
char *LED[]={
"1110111",
"0010010",
"1011101",
"1011011",
"0111010",
"1101011",
"1101111",
"1010010",
"1111111",
"1111011"
};

int n,a[200000],L[10][10];

void to_smallest(int i,int luck){
for(;i<2*n;i++){
int a2=a[(i+n)%(2*n)];

rep(b,a[i]+1){
int dif=L[a[i]][a2]-L[b][a2];
if(luck-dif>0){
luck-=dif;
a[i]=b;
break;
}
}
}
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

rep(b,10) rep(c,10) rep(i,7) if(LED[b][i]=='1' && LED[c][i]=='1') L[b][c]++;

for(int c;c=getchar(),'0'<=c&&c<='9';) a[n++]=c-'0';
n/=2;

int luck=0;
for(int i=2*n-1;i>=0;i--){
int a2=a[(i+n)%(2*n)];

int b;
for(b=a[i]+1;b<10;b++) if(luck-L[a[i]][a2]+L[b][a2]>0) break;

if(b<10){
luck=luck-L[a[i]][a2]+L[b][a2];
a[i]=b;
to_smallest(i+1,luck);
rep(i,2*n) putchar(a[i]+'0'); putchar('\n');
return 0;
}

luck=luck-L[a[i]][a2]+L[8][a2];
a[i]=8;
}

puts("-1");
return 0;
}

解けなかったので Akatsuki さんの解答を大いに参考にした。

下の桁から順にみていって、その桁の数を大きくしても luckiness の条件が満たされるような桁を探す。
そのような桁が見つかったら、今度はその桁から下の桁に向かって Greedy に小さい値を割り当てていく。

J.
struct Point{
int x,y,i,k;
bool operator<(const Point &p)const{ return x<p.x; }
};

inline double dist(const Point &p,const Point &q){
return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y));
}

struct cmp_y{
bool operator()(const Point &p,const Point &q){
return p.y!=q.y?p.y<q.y:p.x<q.x;
}
};

void ClosestPair(vector<Point> p,Point &s,Point &t){
int n=p.size();
sort(p.begin(),p.end());

s=p[0]; t=p[1];
double d=dist(s,t);

set<Point,cmp_y> S;
set<Point,cmp_y>::iterator it_l,it_r,it;
for(int i=0,j=0;i<n;i++){
it_l=S.lower_bound((Point){0,p[i].y-(int)d-1});
it_r=S.upper_bound((Point){0,p[i].y+(int)d+1});
for(it=it_l;it!=it_r;++it){
double tmp=dist(*it,p[i]);
if(tmp+EPS<d) d=tmp, s=*it, t=p[i];
}

while(p[j].x+EPS<p[i].x-d) S.erase(p[j++]);
S.insert(p[i]);
}
}

int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);

int n; scanf("%d",&n);
vector<Point> p(n);
rep(i,n){
int x,y; scanf("%d%d",&x,&y);
rep(k,4){
int xx=(k%2?-x:x),yy=(k<2?y:-y);
if(xx>=0 && yy>=0) p[i]=(Point){xx,yy,i,k};
}
}

Point s,t;
ClosestPair(p,s,t);

printf("%d %d %d %d\n",s.i+1,s.k+1,t.i+1,3-t.k+1);

return 0;
}

ベクトルを原点について反転できるので、
| v_i - _v_j |
を最小化する問題と同値。

また、ベクトルを折り返せるので、すべての点を第 1 象限に集めてしまえる。
こうなってしまえば、これは距離が一番近い 2 点を求める問題、すなわち最近点対問題である。
最近点対問題は O(n log n) で解ける。
上記コードは平面走査による実装。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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