スポンサーサイト

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

Codeforces Beta Round #45

JST 12/12 17:00~20:00 に行われた、Codeforces Beta Round #45 (ACM-ICPC Rules) の参加記録です。
以前よりは力がついてきたように感じるけど、まだまだダメなところが多い。
上位に食い込むためには、もう 1 問解く力が必要。

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

結果

A. 00:06(WA,AC)
B. 00:32(3WA,AC)
C. 02:12(3WA,AC)
D. 00:47(AC)
E. -
F. -
G. -
H. -
Standing : 154/650
Rating : 16721671


問題

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

A. Rock-paper-scissors
3人でじゃんけんをするとき、誰かが1人勝ちしたかそうでないかを答えよ。

B. Land Lot
大きさ n × m の庭に果物の木が何本か植えられている。
今、庭に 大きさ a × b の小屋を建てたいのだが、小屋を建てる位置にある木は切り落とさなければならない。
切り落とす木の最小本数を求めよ。

C. The Race
Vanya は愛車 Huff-puffer に乗ってまっすぐな道を走っている。
道には 100km おきにガソリンスタンドがあり、車は 100km あたり 10 リットルのガソリンを消費する。
車には最初、α (≧10) リットルのガソリンが入っている。
Vanya はガソリンスタンドに着くたびにガソリンの残量をチェックし、 10 リットル未満であれば α リットルを給油することにしている。
走り始めてから Vanya が立ち寄った n コのガソリンスタンドのリストが与えられるとき、Vanya が立ち寄ることになる n+1 コめのガソリンスタンドを求めよ。
そのようなガソリンスタンドが複数考えられる場合はそのことを指摘せよ。
※ α は一般に実数であり、その値は入力で与えられない。

D. Permutations
105 以下の整数が n (≦105) コ与えられる。
それらの整数をいくつかのグループに分けて、各グループが置換になっているようにできるかどうかを判定せよ。
ここで、グループが置換になっているとは、グループの要素数を N とするとき、グループ中に 1, 2, ..., N がちょうど1回ずつ現れることを言う。

E. Ivan the Fool VS Gorynych the Dragon
F. Snow sellers
G. Galaxy Union
H. Black and White

解答

言語は C++。include文とusing文は省略。

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

int main(){
map<string,int> f;
f["rock"]=0;
f["paper"]=1;
f["scissors"]=2;

int hand[3];
rep(i,3){
string s; cin>>s;
hand[i]=f[s];
}

if((hand[0]==0 && hand[1]==2 && hand[2]==2)
|| (hand[0]==1 && hand[1]==0 && hand[2]==0)
|| (hand[0]==2 && hand[1]==1 && hand[2]==1)) cout<<'F'<<endl;
else if(
(hand[1]==0 && hand[2]==2 && hand[0]==2)
|| (hand[1]==1 && hand[2]==0 && hand[0]==0)
|| (hand[1]==2 && hand[2]==1 && hand[0]==1)) cout<<'M'<<endl;
else if(
(hand[2]==0 && hand[0]==2 && hand[1]==2)
|| (hand[2]==1 && hand[0]==0 && hand[1]==0)
|| (hand[2]==2 && hand[0]==1 && hand[1]==1)) cout<<'S'<<endl;
else cout<<'?'<<endl;

return 0;
}

出力する文字を間違えて 1WA.
mod を使えばきれいに書けるだろうけど、パターンを全部列挙しても大した量じゃない。
あと、今まで避けていた rep マクロを今回から使ってみることにした。

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

int main(){
int m,n; cin>>m>>n;
int field[50][50];
rep(i,m)rep(j,n) cin>>field[i][j];

int a,b,cmin=1<<30; cin>>a>>b;
rep(t,2){
rep(i,m-a+1)rep(j,n-b+1){
int cnt=0;
rep(y,a)rep(x,b){ if(field[i+y][j+x]==1) cnt++; }
cmin=min(cmin,cnt);
}
swap(a,b);
}

cout<<cmin<<endl;

return 0;
}

m, n が 50 以下と非常に小さいので、4 重ループの全探索で間に合う。
ありえないタイポのせいで 3WA. あせりすぎ。

前に Codeforces で似た問題を見た気がする、と思ったら これ (B問題) だった。
ちなみに、ICPC の予選にも同じ問題が出ている。(こっちは長方形が覆う木の個数を最大化する)

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

const double EPS=1e-9;

int main(){
int n,plast; cin>>n;
static bool stop[1000001];
rep(i,n){
int p; cin>>p;
if(i==n-1) plast=p;
stop[p]=true;
}

double amin=10,amax=1e20;
int cnt=0;
rep(i,plast+1){
if(stop[i]){
amin=max(amin,(10.*i)/(cnt+1));
amax=min(amax,(10.*(i+1))/(cnt+1));
cnt++;
}
else{
amin=max(amin,(10.*(i+1))/(cnt+1));
}
}

double a1=(n+1)*amin-10*plast;
double a2=(n+1)*amax-10*plast;
int s1=(int)floor(a1/10);
int s2=(int)floor((a2-EPS)/10);
if(s1==s2) printf("unique\n%d\n",plast+s1);
else puts("not unique");

return 0;
}

最初、数論の問題かと思ったけど違った。
進んだ距離 - ガソリン残量 でグラフを書いてみると方針が見えてくる。

各ガソリンスタンドで給油したかどうかという情報があるので、それを使って、ありうる α の範囲を絞り込むことができる。
i 番目のガソリンスタンドに着いた時点でのガソリン残量 gi は、それ以前に給油した回数を c とすると、
   gi = (c+1) α - 10 i リットル
になる。
i 番目のガソリンスタンドで
・ 給油した場合は 0 ≦ gi < 10
・ 給油しなかった場合は 10 ≦ gi
が成り立つので、それぞれ α について解くと α のみたす不等式が得られる。

こうして分かった α の範囲 を αmin ≦ α < αmax とする。
n+1 番目に立ち寄るガソリンスタンドが、n 番目に立ち寄ったガソリンスタンドに
・ 一番近くなるのは α = αmin のとき
・ 一番遠くなるのは α = αmax のとき
なので、それぞれについて n+1 番目のガソリンスタンドを求めて、それらが一致しているかどうかを見ればいい。

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

typedef vector<int> vi;

int main(){
int n; scanf("%d",&n);
vi a(n);
static int buc[100001];
rep(i,n){
scanf("%d",&a[i]);
buc[a[i]]++;
}

bool ok=true;
int mx=*max_element(a.begin(),a.end()),m=0;
for(int i=mx;i>=1;i--){
buc[i]-=m;
if(buc[i]<0){ ok=false; break; }
m+=buc[i];
}
if(!ok){ puts("-1"); return 0; }

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

static int cnt[100001];
rep(i,n){
if(i>0) putchar(' ');
printf("%d",++cnt[a[i]]);
}

return 0;
}

1 番目の Sample Output が謎の番号付けになってるけど、気にしてはいけない。
  1. 与えられる数の中で値が最大のもの( X とする)に注目すると、X が入るグループには 1 から X-1 までの数が 1 回ずつ使われる。

  2. まだ使ってない数の中で最大のもの( Y とする)に注目すると、Y が入るグループには 1 から Y-1 までの数が 1 回ずつ使われる。

  3. 以下同様

  4. 全部の数を使い切るまでこれを繰り返すことで、与えられた数の列をいくつかの順列に分けることができる。
    分けている途中で必要な数が足りなくなったら、順列に分けられなかったということなので -1 を出力する。
    具体的な実装方法は、文章で説明するのが大変なので、気になる人はがんばってソースコードを読んでください。

    E.


    問題文を読むのに疲れたので、Yahoo! 翻訳に頼った。
    「ばかな勇者」と「頭と尻尾がたくさんあるドラゴン」が戦う。
    勇者はドラゴンの頭を切りまくる。ドラゴンの頭は再生しまくる。
    さて、どっちが勝つでしょうか? という問題。
    解いてる人少なかったし、C. で気力を使い果たしたので全然考えてない。今度また考えよう。
    スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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