Codeforces Round #68 (Div2 only)

Result

436 / 816 / 1374 / (WA) / -
67位 no rated


実装速度の低下を感じる。。。

C. Modified GCD

問題

a,bが与えられる。これに対して以下のクエリn個を処理せよ。
クエリ:
与えられた2数low,highに対してlow以上high以下のa,bの公約数のうち最大のものを求める。


a,b,low,high≦10^9
n≦10^4

試行錯誤

Cから解いてみることにする。
公約数は最大公約数の約数。よって最大公約数を求めて、その約数を全部列挙して、low以上high以下のものを拾えばよさそう。


書いてみる。イテレータの操作が久しぶりでかなりハマる。
pretest passed.

ソースコード
int ans, l, h;
void rec(map<int,int> &d, map<int,int>::iterator it,int cur){
  if(cur>h)return;
  if(it==d.end()){
    if(l<=cur)ans=max(ans,cur);
    return;
  }
  int mx=it->second+1, k=it->first;
  it++;
  rep(i,mx){
    rec(d,it, cur);
    cur*=k;
   }
}
void run(){
  int a,b,n; cin>>a>>b>>n;
  int g=__gcd(a,b);
  map<int,int> d;
  for(int i=2;i*i<=g;i++)if(g%i==0)
  {
    int cnt=0;
    while(g%i==0)cnt++, g/=i;
    d[i]=cnt;
  }
  if(g>1)d[g]++;
  rep(i,n){
    cin>>l>>h;
    ans=-1;
    rec(d, d.begin(),1);
    cout<<ans<<endl;  
  }
}

A. Life Without Zeros

問題

10進数のa,bが与えられる。
a,bからすべての0の数字を取り除いた数の和と、
a+bからすべての0の数字を取り除いた数が等しいかを判定せよ。

試行錯誤

文字列操作。
文字列から0を取りのぞく関数と文字列⇔数値変換の関数を書いた。
なんだか実装に時間かかった……

提出。pretest passed.

ソースコード
int toint(string a){
  int ret;
  stringstream ss(a);
  ss>>ret;
  return ret;
}
string rmzero(string a){
  string ret;
  rep(i,a.size())if(a[i]!='0')ret.pb(a[i]);
  return ret;
}
string tostr(int a){
  stringstream ss; ss<<a;
  return ss.str();
}
void run(){
  string a,b;
  int p,q,r,s;
  cin>>a>>b;
  cout<<(tostr(toint(rmzero(a))+toint(rmzero(b)))==
    rmzero(tostr(toint(a)+toint(b)))?"YES":"NO")<<endl;
}

B. Facetook Priority Wall

問題

以下のような文章が与えられると、XとYの関係に得点がつく。(得点は対称で、YとXの関係にも得点がつく)

  • "X posted on Y's wall" (15 points),
  • "X commented on Y's post" (10 points),
  • "X likes Y's post" (5 points).

文章がいくつかと、自分の名前が与えられるとき、自分と関係の高い順に出てきた人の名前を出力せよ。引き分けの場合は辞書順で並べよ。

試行錯誤

mapとか使って書いた。
サンプル合わない。関係が0点の人を出力するのを忘れていた。
訂正して提出。 pretest passed.

D. Big Maximum Sum

問題

小数列がいくつか与えられる。
小数列をいくつかつなげた大数列が、小数列の番号の列により与えられる。

このとき、大数列において連続する項の和の最大値を求めよ。
小数列の数は50以下、それぞれの項数は5000以下、
大数列を作る小数列の番号の列の長さは250000以下である。

試行錯誤

数列の連続する項の和の最大値を求める問題は典型DP.ちょっと変更すればできるはず。
大数列の連続する項は、中間は小数列全体になっていて、
両端だけは小数列の端から連続するいくつかの項になっているはず。


DPをそういう風に変更してみればいいのでは。
書いた。pretest failed.

あ、答えがどっか一つの小数列だけになっている場合を忘れてた。
訂正。 pretest passed.


残り30分くらいだったのでEを解く時間なし。

System Test

DがTLEにより落ちた。
小数列の最大を求めるのをDP使わず手抜きでO(l^2)でやっていたら、
lの最大値は5000だったので、5000^2 * 50 = 6億となって落ちた模様orz
lの最大値50だと思ってた……(酷