スポンサーサイト

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

Codeforces Beta Round #77

2011/07/09 0:00~2:00 (JST)
Codeforces Beta Round #77 (Div.1 Only) の参加記録

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

結果

A. WA
B. WA
C. -
D. -
E. -
Hacks : +-0 (0/0)
Standing : 273/429
Rating : 17921727


問題

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

A. Hockey
文字列 w, n 個の禁止ワード ai, 文字 letter が与えられる。
w を次の手順で置換するとき、結果としてありうるもののうち、含まれる letter の個数が最大のものを求めよ。

1. w の中で ai が含まれる位置をすべて列挙する。 ( i = 1, 2, ..., n)
2. 1. で列挙した位置にあるすべての文字に対して、それを異なる 1 文字に置換する。

※ 置換した結果、再び禁止ワードが現れるかもしれないが、それは考慮しない。

B. Lucky Numbers
十進数表示したとき、各桁に 4 or 7 しか現れない自然数を lucky number という。
lucky number で、現れる 4 と 7 の個数が等しいものを super lucky number という。

n 以上で最小の lucky number を求めよ。

1 ≦ n ≦ 105

C. Volleyball
n 個の交差点と m 本の道路 (一方通行) がある。
各交差点には 1 台のタクシーがいて、それぞれ、距離 ti の範囲にある交差点に、料金 ci で移動することができる。

一度乗ったタクシーに二度は乗れない。

スタート地点の交差点から目的地の交差点までに移動するための最小料金を求めよ。

1 ≦ n ≦ 1000
0 ≦ m ≦ 1000

D. Horse Races
l 以上 r 以下の nearly lucky number の個数を mod 1000000007 で求めよ。

自然数 n が nearly lucky number であるとは、
n の十進数表示を n = am...a1a0 と書くとき
∃ i, j ( i ≠ j ) s.t. ai = 4 or 7, aj = 4 or 7, | j - i | ≦ k
となることをいう。

1 ≦ k ≦ 1000
1 ≦ l ≦ r ≦ 101000

E. Lucky Country
n 個の島と m 本の橋がある。
ここにいくつかの橋を追加して、ある連結成分に含まれる島の数が lucky number になるようにしたい。
最小でいくつの橋を追加すればいいか。

1 ≦ n, m ≦ 105

解答

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

A. (時間外)
int main(){
int n; cin>>n;
string sub[100],w;
char letter;
rep(i,n){
cin>>sub[i];
rep(j,sub[i].length()) sub[i][j]=tolower(sub[i][j]);
}
cin>>w>>letter;

bool upper[100]={};
rep(i,w.length()) if(isupper(w[i])) {
w[i]=tolower(w[i]);
upper[i]=true;
}

bool change[100]={};
rep(i,n){
int slen=sub[i].length();
rep(j,(int)w.length()-slen+1){
if(sub[i]==w.substr(j,slen)) fill(change+j,change+j+slen,true);
}
}

rep(i,w.length()){
if(change[i]){
if(w[i]!=letter) w[i]=letter;
else w[i]=(w[i]!='a'?'a':'b');
}
if(upper[i]) w[i]=toupper(w[i]);
}
cout<<w<<endl;

return 0;
}

問題文がとても読みにくい。
がんばって英語を読みましょうという問題。

読めたらやるだけなんだけど、string::length が unsigned int を返すという仕様を忘れていて配列外参照をしてしまった。

B. (時間外)
int main(){
string n; cin>>n;
int len=n.length();

string n_max(len,'?');
rep(i,len) n_max[i]=(i<len/2?'7':'4');

if(len%2==1 || (len%2==0 && n>n_max)){
cout<<string(len/2+1,'4')<<string(len/2+1,'7')<<endl;
return 0;
}

bool big=false;
string ans(len,'?');
rep(i,len){
if(big || n[i]<='4'){
ans[i]='4';
if(n[i]<ans[i]) big=true;
}
else if(n[i]<='7'){
ans[i]='7';
if(n[i]<ans[i]) big=true;
}
else{
for(int j=i;j>=0;j--){
if(n[j]<'7'){
ans[j]='7';
break;
}
ans[j]='4';
}
big=true;
}
}

int cnt4=count(all(ans),'4'),cnt7=count(all(ans),'7');
if(cnt4<cnt7){
int i,c=0;
for(i=len-1;;i--){
if(ans[i]=='7') c++;
if(c>(cnt7-cnt4)/2 && ans[i]=='4' && ans[i+1]=='7') break;
}
ans[i++]='7';
c-=(cnt7-cnt4)/2+1;
fill(ans.begin()+i,ans.end()-c,'4');
fill(ans.end()-c ,ans.end() ,'7');
}
else if(cnt4>cnt7){
for(int i=len-1;;i--) if(ans[i]=='4') {
if(cnt4==cnt7) break;
ans[i]='7';
cnt4--;
cnt7++;
}
}

cout<<ans<<endl;

return 0;
}

前から Greedy に決めていくのが想定解らしいけど、自分のは少し違う。

まず、n の桁数が奇数のときは、明らかに 444...4777...7 が答え。
偶数のときが問題。

方針を大雑把に書くと、まず n 以上で最小の lucky number を求めた。
これは、この手のコードを書いたことがあればすぐにできる。

次に、ここから 4 と 7 の個数を調節して答えを得ようと考えた。
4 の方が多いときは簡単で、下位の桁にある 4 から順に 7 に変えていけばいい。
7 の方が多いときは、
ある位置の "47" というパターンを "74" に置き換えて、それより下位の桁を 444...4777...7 とすればいい。
この "ある位置" は、できるだけ下位の桁から選ぶようにする。
( 本番中はここの処理を間違えて WA になった。 )

C. (時間外)
const ll INF=1LL<<61;

template<class T> struct Edge{
int u,v;
T w;
Edge(int U,int V,T W):u(U),v(V),w(W){}
};

template<class T>
struct AdjList:public vector< vector< Edge<T> > >{
AdjList(int n,const vector< Edge<T> > &v=vector< Edge<T> >()):vector< vector< Edge<T> > >(n,v){}
};

template<class T>
void Dijkstra(const AdjList<T> &adj,int s,vector<T> &d){
int n=adj.size();
d.assign(n,INF); d[s]=0;

priority_queue< pair<T,int> > pq; pq.push(make_pair(0,s));
while(!pq.empty()){
pair<T,int> a=pq.top(); pq.pop();
int u=a.second;
if(d[u]<-a.first) continue;

rep(i,adj[u].size()){
int v=adj[u][i].v;
T w=adj[u][i].w;
if(d[u]+w<d[v]){
d[v]=d[u]+w;
pq.push(make_pair(-d[v],v));
}
}
}
}

int main(){
int n,m,s,g; scanf("%d%d%d%d",&n,&m,&s,&g);
s--, g--;
AdjList<ll> adj(n);
rep(i,m){
int u,v,w; scanf("%d%d%d",&u,&v,&w);
u--, v--;
adj[u].push_back(Edge<ll>(u,v,w));
adj[v].push_back(Edge<ll>(v,u,w));
}

vector<ll> d;
AdjList<ll> adj2(n);
rep(u,n){
int t,c; scanf("%d%d",&t,&c);
Dijkstra(adj,u,d);
rep(v,n) if(d[v]<=t) adj2[u].push_back(Edge<ll>(u,v,c));
}

Dijkstra(adj2,s,d);
printf("%I64d\n",d[g]<INF?d[g]:-1);

return 0;
}

まず、グラフの全点対間最短路を求める。
辺数が少ないので、Dijkstra を n 回回せば間に合う。 O(n m log n).
そのあと、タクシーで移動できる交差点間に辺を張って、そうやって新しく作ったグラフであらためて最短距離を求めてやればいい。

D.


E. (時間外)
class UnionFind{
vector<int> a;
public:
UnionFind(int n):a(n,-1){}
int find(int x){
if(a[x]<0) return x;
return a[x]=find(a[x]);
}
void unite(int x,int y){
x=find(x),y=find(y);
if(x!=y){ a[x]+=a[y]; a[y]=x; }
}
int size(int x){ return -a[find(x)]; }
};

void dfs(int v,int n,vector<int> &lucky){
if(v>n) return;
if(v>0) lucky.push_back(v);
dfs(10*v+4,n,lucky);
dfs(10*v+7,n,lucky);
}

int main(){
int n,m; scanf("%d%d",&n,&m);
UnionFind uf(n);
rep(i,m){
int u,v; scanf("%d%d",&u,&v);
u--; v--;
uf.unite(u,v);
}

static bool flg[100000];
map<int,int> a;
map<int,int>::iterator it;
rep(u,n){
int id=uf.find(u);
if(!flg[id]){
flg[id]=true;
++a[uf.size(u)];
}
}

static int dp[100001];
rep(i,n) dp[i+1]=INF;
for(it=a.begin();it!=a.end();++it){
int val,cnt=it->second;
for(int c=1;cnt;cnt-=c,c<<=1){
c=min(c,cnt);
val=c*it->first;
for(int j=n;j>=val;j--) dp[j]=min(dp[j],dp[j-val]+c);
}
}

vector<int> lucky;
dfs(0,n,lucky);

int ans=INF;
rep(i,lucky.size()) ans=min(ans,dp[lucky[i]]);
if(ans==INF) ans=-1; else ans--;
printf("%d\n",ans);

return 0;
}

各連結成分のサイズは、Union-Find を使えば簡単に調べられる。
ようは、
{ a1, a2, ..., an } から最小でいくつの数を足し合わせれば lucky number を作れますか?
という問題。
ナップザック問題に近い。

0-1 ナップザック問題の DP 解法と同じ方針でやろうとすると、O(n2) かかるのでダメ。

そこで、同じ数を一まとめに見て、有界ナップザック問題 (bounded knapsack problem) だと思う。
こうすると、品物の種類 (異なる数の個数) は O(√n) くらいになる。
有界ナップザック問題そのものは O(品物の種類 ・ コストの和) の DP 解法があったはずだけど、今回の問題には適用しにくかった。

ここまでは自分で思いついた。
以降は writer の解説cafelier さんのブログ を参考にした。

答えから書くと、品物を 1, 2, 4 ,8, ... 個ずつに分ければいい。
これは非常にうまい方法で、こうすれば、任意の数をこれらの組み合わせで作ることができる。
たとえば、
6 を分解すると 1, 2, 3.
24 を分解すると 1, 2, 4, 8, 9.
など。

全体をあわせると、計算量は O(n √n log n) となる。
スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

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

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

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