スポンサーサイト

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

Codeforces Beta Round #33

10/8 0:00~2:00 (JST)
久しぶりのcodeforces.
いつものように、結果報告と解けた問題の簡単な解説とか。

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

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

A. What is for dinner?
サメのValerieは n 本の歯を持っている。
それらの歯は m 列に並んでいる。
Valerieの餌はフナであり、彼女はそれをできるだけ多く食べたいと思っている。
各歯には耐久力が設定されており、それが負になると虫歯になってしまう。

彼女は、フナ1匹を食べるごとにただ1つの歯列しか使わない、という変わった食べ方をする。
使った歯列に属する歯は耐久力が 1 下がる。

歯の本数 n, 歯列の数 m, フナの総数 k, 各歯がどの歯列に属するかの情報, 各歯の耐久力が与えられたときに、彼女が食べることのできるフナの最大数を答える。

B. String Problem
2つの文字列 a, b と、以下のような置換規則が n コ与えられる。
a, b は共にアルファベット小文字のみからなり、105文字以下である。
a にいくつかの置換をほどこした結果を a'
b にいくつかの置換をほどこした結果を b' とすると、
a'=b' となるための最小の置換コストと置換後の文字列を答える。答えが複数ある場合はどれを出力してもいい。
そのような変換が存在しなければ -1 と答える。

n コの置換規則は、それぞれ
『文字列中に文字 c があれば、コスト w でそれを d に置換してもよい』
という形で与えられる。

C. Wonderful Randomized Sum
n コの整数からなる数列 {an} を考える。

{an} の prefix を次のように定義する。
『初項a1を含む、{an} の連続する部分列』
(たとえば、{a1, a2, a3} は prefix である)

{an} の suffix を次のように定義する。
『末項anを含む、{an} の連続する部分列』
(たとえば、{an-1, an} は suffix である)

prefix, suffix のいずれも、空集合であってもいい。

prefix と suffix を適当に選んで、それらのすべての要素に -1 をかける。
なお、選んだ prefix, suffix は重なっていてもいい。(その場合、重なった部分は -1×-1 倍されるので、値は変わらない)
このとき、{an} の要素の和の最大値を求める。

D. Knights
Berland国には n コの拠点と m コの円形の柵がある。
※ 拠点の座標は重なっているものがあるかもしれない。
※ どの2つの柵も共有点を持たないことが保証されている。

各制御点の座標、各柵の半径と中心が与えられる。
k組の拠点の対が指定されるので、各々の点対に対して、それらを行き来するのに越えなければならない柵の最小数を答える。

1≦n, m≦103, 0≦k≦105

E. Helper


[ 解答 ]
言語は C++。include文とusing文は省略。

A. (時間外)
typedef vector<int> vi;

const int inf=1000000000;

int main()
{
int n,m,k; cin>>n>>m>>k;
vi via(m,inf);
for(int i=0;i<n;i++){
int r,c; cin>>r>>c;
via[r-1]=min(via[r-1],c);
}
cout<<min(accumulate(via.begin(),via.end(),0),k)<<endl;

return 0;
}

英語がなかなか読めなくて、何言ってるのかわからず苦戦。
何とか意味を理解して、コードを書き上げ、PreTestを通す。
...
SystemTestで落ちる。歯の耐久力が始めから 0 であるケースを見逃していただけだった。
上のは本番終了後に修正したコード。

各歯列について、一番耐久力のない歯を覚えておいて、それを全列分足し合わせるだけ。

B. (時間外)
const int inf=1000000000;
int wf[128][128];

int main()
{
for(int a='a';a<='z';a++)for(int b='a';b<='z';b++)wf[a][b]=(a==b?0:inf);

string s1,s2; cin>>s1>>s2;
int n; cin>>n;
for(int i=0;i<n;i++){
char a,b;
int cost;
cin>>a>>b>>cost;
wf[a][b]=min(wf[a][b],cost);
}

if(s1.length()!=s2.length()){
cout<<-1<<endl;
return 0;
}

// Warshall-Floyd
for(int k='a';k<='z';k++)for(int i='a';i<='z';i++)for(int j='a';j<='z';j++){
wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
}

int costsum=0,len=s1.length();
for(int i=0;i<len;i++){
if(s1[i]==s2[i]) continue;

int costmin=inf,jmin;
for(int j='a';j<='z';j++){
int cost=wf[s1[i]][j]+wf[s2[i]][j];
if(cost<costmin){
costmin=cost;
jmin=j;
}
}
if(costmin==inf){
cout<<-1<<endl;
return 0;
}

costsum+=costmin;
s1[i]=jmin;
}

cout<<costsum<<endl<<s1<<endl;

return 0;
}

文字列の i 文字目と j 文字目は決して交わらないので、各文字について最小コストを計算して足し合わせればいい。
アルファベットをノード、変換規則を有向辺とみてグラフを作ると、最小の置換コストを求める問題はグラフの最短経路を求める問題に帰着できる。

ここまではよかったが、本番では各文字ごとに最短経路を求め直すということをやってしまって、最悪ケースでは105回 Dijkstra が呼ばれてしまい、見事にTLE。
なまじPreTestは通ってしまったからこのことに気付かず、この問題も落とした。
前計算しておけばよかっただけだし、Warshall-Floyd でも十分間に合った。

C. (時間外)
int main()
{
int n,sum[3]={}; cin>>n;
for(int i=0;i<n;i++){
int a; cin>>a;
sum[2]=max(sum[2],sum[1])-a;
sum[1]=max(sum[1],sum[0])+a;
sum[0]-=a;
}
cout<<*max_element(sum,sum+3)<<endl;

return 0;
}

解法が思いつかず、嘘解答でお茶を濁すもやっぱり落ちる。(PreTestは通る)

[2010/10/12 追記]
気付いてしまえばシンプルなDPだった。

まず、prefixとsuffixが重なる場合は、重ならない場合に含まれるので考えなくていいことに注意する。

たとえば、n=5 のとき
prefix が {a1, a2, a3}
suffix が {a3, a4, a5}
であれば、{an} の総和は
prefix が {a1, a2}
suffix が {a4, a5}
であるときの総和と何も変わらない。


なので、位置 p における項 ap の状態は
(1) ap は prefix 中にある
(2) ap は prefix 中にも suffix 中にもない
(3) ap は suffix 中にある
の3通りしか考えられない。

これら3通りすべてについて、逐次、とりうる最大値を更新していけばいい。

・余談
sum[2]=max(sum[2],sum[1])-a;
よりも
sum[2]=max(max(sum[2],sum[1]),sum[0])-a;
とした方が意味は分かりやすいが、ケース(1)から(3)に直接遷移する場合は、ずっと(1)である場合と同じなので考えなくていい。

偶然にも、この回のcodeforcesが終わった2日後にPKUで類題(2181,2385)を解いていた、とか。

D. (時間外)
#define    X   first
#define Y second

typedef pair<int,int> pii;

bool in[1000][1000];

int main()
{
int n,m,k; scanf("%d%d%d",&n,&m,&k);
pii pt[1000];
for(int i=0;i<n;i++) scanf("%d%d",&pt[i].X,&pt[i].Y);
for(int i=0;i<m;i++){
int r,cx,cy; scanf("%d%d%d",&r,&cx,&cy);
for(int j=0;j<n;j++)
in[i][j]=(1LL*(cx-pt[j].X)*(cx-pt[j].X)+1LL*(cy-pt[j].Y)*(cy-pt[j].Y)<1LL*r*r);
}

while(k--){
int a,b,cnt=0; scanf("%d%d",&a,&b);
a--; b--;
for(int i=0;i<m;i++) if(in[i][a]^in[i][b]) cnt++;
printf("%d\n",cnt);
}

return 0;
}

[2010/10/23 追記]
1クエリ O(m) のシンプルな解法で通った。
点が各円の内か外かを考えて、それらが一致しないものの個数が答え。
in[i][j] は、円 i の内側に点 j があれば true.
bit演算による高速化とか、クエリを O(1) で処理できるアルゴリズムとかもあるようだ。(試してないけど

E.


やってない。


まさかの0完で、
Ratingは16031508
こんなことならあと9点落ちててくれれば、次の Div2 Only に参加できたのに...

解けてない問題は、解決し次第 追記予定。
スポンサーサイト

コメントの投稿

非公開コメント

No title

codeforces面白そうですね!
Ratingの仕組みがT○pC○derのパクリな感がありますが・・・

No title

ぜひ参加されてみては?
PKU の問題を解かれているのなら英語がネックになることもないでしょうし。

開催予定は
http://www.codeforces.com/contests
で確認できますが、ただ、なかなか時間が合わないかもしれません。
(ちなみに、時差の関係で、日本時間では表示より5時間後に開かれます。)
プロフィール

fura2

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

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

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