スポンサーサイト

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

Codeforces Beta Round #43

JST 12/05 17:00~20:00 に行われた、Codeforces Beta Round #43 (ACM-ICPC Rules) の参加記録です。
Codeforces の解けてない問題がだんだんたまってきてるので、機を見て一気に解きたい。

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

結果

A. 00:11(AC)
B. 00:26(AC)
C. 00:47(AC)
D. 02:09(2WA,AC)
E. -
F. -
G. -
Standing : 200/939
Rating : 16981672


問題

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

A. Ball Game
n 人の子どもが円形に並んでいる。子どもには時計回りに 1 ~ n の番号がついている。
最初、子ども 1 がボールを持っている。
以下のルールにしたがって n-1 回のボール投げを行う。各回でボールを持っている子どもの番号を出力せよ。

[ ルール ]
i 回目のボール投げで、ボールを持っている子どもは自分の位置から時計回りに数えて i+1 人目の子どもにボールを投げる。

B. T-shirts from Sponsor
サイズ S, M, L, XL, XXL のTシャツがそれぞれ、NS, ..., NXXL 枚ある。
K 人に順番にTシャツを配る作業をシミュレートせよ。
各人に合ったTシャツのサイズ(S, ..., XXL)が与えられる。必要なサイズのTシャツが足りなくなったときは、なるだけ自分に合ったもの(*)を選ぶものとする。

(*) 2種類のサイズが考えられる場合は大きいものを優先する。たとえば、サイズ L の人は L, XL, M, XXL, S の順に選ぼうとする。

C. Hamsters and Tigers
計 n 匹のハムスターと虎が円形に並んでいる。
「 2 匹を選んで場所を交換する」という操作を何回か行って、ハムスターと虎を分離(*)したい。
必要な操作の最小回数を答えよ。

(*) うまい言葉が思いつかないけど、要は
   [ ハムハムハム…ハム虎虎虎…虎 ]
  みたいな感じにするということ。なお、上の図で左端と右端はつながっている。

D. Parking Lot
長さ L (1≦105) の直線状の駐車スペースに車が駐車/発車される様子をシミュレートせよ。
n (≦100) 件の駐車/発車情報が与えられる。
車は駐車スペースの左端から入ってきて、前の車との距離が f 以上かつ後ろの車との距離が b 以上になる場所を見つけたらそこに駐車する。このとき、車の駐車した座標を出力する。
最後までそのような場所が見つからなかった場合は駐車しない。このとき、-1 を出力する。

E. Comb
n行 m列 (n, m ≦1500) のパネルがあり、パネルの各マスには絶対値 10000 以下の整数が書かれている。
各行について、左端を含むような連続するいくつかのマスを選んで、選んだマスに書かれた数の和を最大化せよ。

ただし、
第 i 行で ci コのマスを選んだとすると、各 ci
・ 1 ≦ ci ≦ m
・ c1 > c2 < c3 > ...
をみたさなければならない。

F.
G.

解答

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

A.
int main(){
int n; cin>>n;
int p=0;
for(int i=1;i<n;i++){
p=(p+i)%n;
cout<<(i==1?"":" ")<<p+1;
}
cout<<endl;

return 0;
}

やるだけ。
競技開始時には sample input が間違っていて、10分後に修正されるまで自分が誤訳したんだと思った。

B.
int main(){
char *finv[]={"S","M","L","XL","XXL"};
map<string,int> f;
for(int i=0;i<5;i++) f[finv[i]]=i;

int order[5][5]={
{0,1,2,3,4},
{1,2,0,3,4},
{2,3,1,4,0},
{3,4,2,1,0},
{4,3,2,1,0}};

int n[5];
for(int i=0;i<5;i++) cin>>n[i];

int m; cin>>m;
while(m--){
string man; cin>>man;
int sz=f[man];
for(int i=0;i<5;i++){
if(n[order[sz][i]]>0){
cout<<finv[order[sz][i]]<<endl;
n[order[sz][i]]--;
break;
}
}
}

return 0;
}

やるだけ2。特に書くことがない。

C.
int n;

int calcDistance(const string &s1,const string &s2){
int cnt=0;
for(int i=0;i<n;i++) if(s1[i]!=s2[i]) cnt++;
return cnt;
}

int main(){
string ini;
cin>>n>>ini;

int nh=0,nt=0;
for(int i=0;i<n;i++){
if(ini[i]=='H') nh++;
else nt++;
}

int dmin=1<<30;
string arranged=string(nh,'H')+string(nt,'T')+string(nh,'H')+string(nt,'T');
for(int i=0;i<n;i++){
dmin=min(dmin,calcDistance(ini,arranged.substr(i,n)));
}
cout<<dmin/2<<endl;

return 0;
}

たとえば、ハムスター 3 匹、虎 2 匹のとき、最後の状態は
・ HHHTT
・ THHHT
・ TTHHH
・ HTTHH
・ HHTTH
の 5 通りしかない。これらそれぞれの状態について、
「初期状態から辿りつくのに必要なスワップ回数」は簡単に計算できる。(初期状態と違っている動物の数/2)
各スワップ回数の中で最小のものが答え。

D.
struct Car{
int id,p,len; // p : coordinate of its back
Car(int _id,int _p,int _len):id(_id),p(_p),len(_len){}
};

int main(){
int L,b,f,n; cin>>L>>b>>f>>n;
list<Car> ls;
for(int i=1;i<=n;i++){
int type; cin>>type;
if(type==1){ // park
int len; cin>>len;

int parkpos=-1;
if(ls.size()==0){
if(len<=L){
parkpos=0;
ls.pb(Car(i,parkpos,len));
}
}
else{ // at least 1 car is parked
list<Car>::iterator it1,it2;

if(len+f<=ls.front().p){ // the leftmost space
parkpos=0;
ls.push_front(Car(i,parkpos,len));
goto PARKED;
}

for(it1=it2=ls.begin(),++it2;it2!=ls.end();it1++,it2++){
int p1=it1->p,p2=it2->p,len1=it1->len;
int need=b+len+f;
if(need<=p2-(p1+len1)){
parkpos=p1+len1+b;
ls.insert(it2,Car(i,parkpos,len));
goto PARKED;
}
}

if(b+len<=L-(ls.back().p+ls.back().len)){ // the rightmost space
parkpos=ls.back().p+ls.back().len+b;
ls.pb(Car(i,parkpos,len));
goto PARKED;
}

PARKED:;
}

cout<<parkpos<<endl;
}
else{ // departure
int id; cin>>id;

list<Car>::iterator it;
for(it=ls.begin();it!=ls.end();){
if(it->id==id) it=ls.erase(it);
else it++;
}
}
}

return 0;
}

今回、シミュレーションばっかり。
最初、データ構造を工夫して各クエリを高速に処理しないとTLEですよ的な問題かと思ったけど、nが高々 100 なのでそんなことはしなくてよかった。
リストを使って車の位置情報だけを持つ形で実装したけど、駐車スペース全体の配列を持ってシミュレートしても、L×n ≦ 107 なので間に合うかもしれない。

競技中には、リストに要素を挿入する処理と、車が駐車スペースの右端に停まるときの条件文を間違えて 2WA。

E. (時間外)
const long long INF=1LL<<60;

int main(){
int n,m; scanf("%d%d",&n,&m);
static int stone[1500][1500];
for(int i=0;i<n;i++)for(int j=0;j<m;j++) scanf("%d",stone[i]+j);

static int psum[1500][1500];
for(int i=0;i<n;i++){
psum[i][0]=stone[i][0];
for(int j=1;j<m;j++) psum[i][j]=psum[i][j-1]+stone[i][j];
}

static long long memo[1500][1500];
for(int i=0;i<n;i++)for(int j=0;j<m;j++) memo[i][j]=-INF;
for(int j=0;j<m;j++) memo[0][j]=psum[0][j];
for(int i=1;i<n;i++){
if(i%2==1){
int jmax=m-1;
for(int j=m-2;j>=0;j--){
memo[i][j]=memo[i-1][jmax]+psum[i][j];
if(memo[i-1][jmax]<memo[i-1][j]) jmax=j;
}
}
else{
int jmax=0;
for(int j=1;j<m;j++){
memo[i][j]=memo[i-1][jmax]+psum[i][j];
if(memo[i-1][jmax]<memo[i-1][j]) jmax=j;
}
}
}

printf("%I64d\n",*max_element(memo[n-1],memo[n-1]+m));

return 0;
}

n×m の表を順番に埋めていくタイプの、典型的なDP。
アルゴリズム自体は単純だけど、問題の英文が非常に難解。
マスを選ぶルールがさらっと書かれていて、かなり注意深く読まないと分からない。

あと注意すべき点としては、
・ cin を使うとTLEになるので、C言語の入力関数を使うこと
・ 答えがintに入りきらないので、64bit 整数を使わないといけないこと
Codeforces で64bit整数値を出力するときは、printf("%lld") でなく printf("%I64d") とすること (理由はしらない)

3つめの注意を忘れていて、競技中ではWA連発した挙句、結局通らなかった。

F.
G.
時間ができたらやる。


以上。
School Personal Contest #2 も兼ねていたためかどうかは分からないけど、今回は全体的に簡単な問題セットでした。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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