スポンサーサイト

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

Codeforces Beta Round #64

2011/03/27 1:00~3:00 (JST)
Codeforces Beta Round #64 の参加記録

個人ブログだし、今回から感想も書くことにした。

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

結果

A. Hacked, AC (398)
B. WA, AC (850)
C. -
D. -
E. -
Hacks : +-0 (0 hacked / 0 missed)
Standing : 236/1226
Rating : 16601710


紫の真ん中でくすぶりすぎ。

感想

感想は記事の一番最後に移すべきかもしれない。検討中。

A.
問題文を流し読みして開始 5 分で出したら、n = 0 のケースで Hack された。
最近、A は submit → hacked → resubmit のパターンばかりな気がする。
ただ、これで失敗しても点数は 100 点程度しか下がらないのであまり気にしていない。

B.
自分にしては、中々早く書き上げることができた。
出力文字列の typo で 1 回 WA をもらったけど、大した問題じゃない。

C.
90 分くらい考えて解けなかったのは残念。Rating が伸びないのは、明らかに C を解けないのが原因。
何とか時間内に C を解く力をつけたい。
なんだかんだで今回も 100 人程度は通しているし。

D. E.
そんなのはなかった。

問題

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

A. Cookies
を見るのが一番分かりやすい。
与えられた n ( 0 ≦ n ≦ 1000 ) に対して、2n × 2n の正方形を図のような三角形でできるだけ埋めたとき、空きマスはいくつあるか?
mod 1000003 で答えよ。

B. Text Messaging
入力される文字列 TEXT は次の BNF をみたす。

TEXT ::= SENTENCE | SENTENCE SPACE TEXT
SENTENCE ::= WORD SPACE SENTENCE | WORD END
END ::= {'.', '?', '!'}
WORD ::= LETTER | LETTER WORD
LETTER ::= {'a'..'z', 'A'..'Z'}
SPACE ::= ' '

文字列は SENTENCE と SENTENCE の間でだけ改行することができる。
改行の際、SENTENCE の間にある SPACE は削除される。

1 行の文字列長を n 文字以内に収めるように改行するとき、必要な行数の最小値を求めよ。
所望の改行方法が存在しないときは -1 と答えよ。

C. Lucky Tickets
正整数 a について、rev(a) を「 a を 10 進数で書いたものを右から読んだ数」と定義する。
正整数の組 (a, b) が Lucky であるとは、a・b = rev(a)・rev(b) であることをいう。

与えられる xmax, ymax, w に対して、次の 3 条件をみたす (x, y) を 1 つ求めよ。
条件に合うものが複数ある場合はどれを答えてもいい。
条件に合うものがない場合は -1 と答えよ。

1. 1 ≦ x ≦ xmax, 1 ≦ y ≦ ymax
2. 1 ≦ a ≦ x, 1 ≦ b ≦ y なる Lucky な (a, b) が w 個以上ある
3. 2. の条件をみたす (x, y) の中で x・y が最小である

1 ≦ xmax, ymax ≦ 105
1 ≦ w ≦ 107

D.
E.
いつか。

解答

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

A.
int M=1000003;

int main(){
int n; scanf("%d",&n);
int ans=1;
rep(i,n-1) ans=(ans*3)%M;
printf("%d\n",ans);

return 0;
}

図からみて明らかなように、
n = 0 のとき 1,
n > 0 のとき 3n-1
が答え。

問題の図形はフラクタル (の構成を有限ステップで止めたもの)。
n が 1 つ増えると、左上と右下に同じものがコピーされるので、
f(n) = f(n-1) + 2 f(n-1) = 3 f(n-1).

B.
bool isend(char c){ return c=='.' || c=='?' || c=='!'; }

int main(){
int n; cin>>n;
cin.ignore();
string s; getline(cin,s);

vector<string> ss;
for(int i=0,bef=0;i<s.length();i++){
if(isend(s[i])) ss.pb(s.substr(bef,i-bef+1)),bef=i+2;
}

int pos=0,line=1;
rep(i,ss.size()){
s=ss[i];
int len=s.length();
int space=(pos==0?0:1);
if(len>n){ line=-1; break; }
if(pos+space+len<=n) pos+=space+len;
else{ pos=len; line++; }
}

if(line==-1) cout<<"Impossible"<<endl;
else cout<<line<<endl;

return 0;
}

「改行しないといけなくなるまで改行しない」という Greedy アルゴリズムでいい。
というのも、早めに改行しておくことで、後で改行数が少なくなるようなことは起こらないから。

C++ は文字列を split するのが面倒。
space を delimiter にしたくないときは stringstream も使いにくい。

C. (時間外)
ull gcd(ull a,ull b){ return b?gcd(b,a%b):a; }

int main(){
static int rev[100001];
rep(i,100001){
int a=i,r=0;
while(a>0) r=r*10+a%10,a/=10;
rev[i]=r;
}

int xmax,ymax,w; scanf("%d%d%d",&xmax,&ymax,&w);

map<pii,int> rowhist,colhist;
for(int y=1;y<=ymax;y++){
int g=gcd(y,rev[y]);
++colhist[mp(rev[y]/g,y/g)];
}

int xans=INF,yans=INF;
int cnt=0;
for(int x=1,y=ymax;x<=xmax;x++){
int g=gcd(x,rev[x]);
pii xkey(x/g,rev[x]/g),xkeyinv(xkey.second,xkey.first);
cnt+=colhist[xkey];
++rowhist[xkeyinv];

if(cnt<w) continue;
while(1){
g=gcd(y,rev[y]);
pii ykey(y/g,rev[y]/g),ykeyinv(ykey.second,ykey.first);
int dif=rowhist[ykey];
if(cnt-dif>=w){
cnt-=dif;
y--;
--colhist[ykeyinv];
}
else break;
}

if((ll)x*y<(ll)xans*yans) xans=x,yans=y;
}

if(xans<INF) printf("%d %d\n",xans,yans);
else puts("-1");

return 0;
}

[ 2011/03/29 追記 ]

正解者何人かのコードを参考にしながら解いた。
まったく手がつけられないほど難しくはないが、初見では思いつかない解法だった。

最初にある程度の考察が必要で、それができれば、二分探索木 (map) でごにょごにょやってオーダーを落とすタイプの問題。adhoc.

x・y = rev(x)・rev(y) ⇔ x / rev(x) = rev(y) / y に注目する。
前計算として、map などを使って 1 ≦ y ≦ ymax に対する y / rev(y) の値のヒストグラム COLHIST を作っておく。
そうすれば、任意の x に対して、(x, y) が Lucky であるような y (1 ≦ y ≦ymax) の個数は log オーダーで引き出すことができる。
また、x / rev(x) の値を保持するためのヒストグラム ROWHIST も用意しておく。

次に、1 ≦ x ≦ xmax, 1 ≦ y ≦ ymax にある格子点を上手く走査することを考える。
もちろん、全部見ていたらそれだけで 1010 回の反復になるので TLE.

まず、(x, y) = (1, ymax) から始める。
x・y が最小になるものにだけ興味があるので、Lucky な個数に関する条件をみたしている間、y の値を 1 つずつ減らしていく。
これ以上 y を下げられなくなったら、x を 1 つ増やす。
同様にして、x = xmax まで繰り返す。
これは、x を横軸、y を縦軸にとった直交座標でいうなら、左上から右下にかけてジグザグに走査していることになる。
x, y を変化させるときに Lucky な個数がどのように変わるかは、座標を紙に書いて考えるとわかりやすい。

y を減らしたり、x を増やしたりする際に、ヒストグラムを更新しないといけない。
y を減らすときは、対応する y / rev(y) を COLHIST から削除すればいい。
x を増やすときは、対応する x / rev(x) を ROWHIST に追加すればいい。

計算量オーダーは、
前計算が O( ymax log(ymax) ).
本計算が O( xmax log(ymax) + ymax log(xmax) ).
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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