yukicoder 171 参加記録 - 競プロ日記

yukicoder 171に参加しました。

5/6完で45位でした。

星3のDPが解けなかった。

No.552 十分簡単な星1の問題

long long でもオーバーフローするのでstringで受け取って+“0"する。

ただし、0が入力される場合はそのまま出力することに注意。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  string s;
  cin >> s;
  if(s.length() == 1 && s[0] == '0') cout << 0 << endl;
  else cout << s << 0 << endl;
  return 0;
}

No.553 AlphaCoder Rating

やるだけだけど数式が複雑でめんどくさそうなので後回しにした。

誤差±1までOKなので誤差を気にせず実装して大丈夫だった。

逆関数の知識が必要。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
int main()
{
  int N; cin >> N;
  double r[N];
  FOR(i,0,N) cin >> r[i];
  double Fn, fn, f1, finf;
  FOR(i,1,N+1) Fn += pow(0.81, i);
  Fn = sqrt(Fn);
  double tmp = 0;
  FOR(i,1,N+1) tmp += pow(0.9, i);
  Fn /= tmp;
  f1 = sqrt(0.81) / 0.9;
  finf = sqrt(0.81 / 0.19) / (0.9 / 0.1);
  fn = (Fn - finf) / (f1 - finf) * 1200;
  double ans = 0;
  FOR(i,1,N+1) {
    ans += pow(2, r[i-1] / 800.0) * pow(0.9, i);
  }
  ans /= tmp;
  ans = 800 * log(ans) / log(2);
  ans -= fn;
  cout << int(ans) << endl;
  return 0;
}

No.554 recurrence formula

第2項から順に求めていく。

和の部分を毎回求めていたらO(n²)となるのでTLE。

累積和を保存しておけばO(n)となってAC。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const ll mod = 1e9 + 7;
int main()
{
  int n; cin >> n;
  ll oddsum = 1, evensum = 0;
  ll a = 1;
  FOR(i,2,n+1) {
    if(i % 2 == 0) {
      a = i * oddsum;
      a %= mod;
      evensum += a;
      evensum %= mod;
    } else {
      a = i * evensum;
      a %= mod;
      oddsum += a;
      oddsum %= mod;
    }
  }
  cout << a % mod << endl;
  return 0;
}

No.555 世界史のレポート

DPぽいなと思ったけどできなかった問題。

dp[i] := 長さをi以上にするのに必要な最小コストとしてしまうとO(n²)となりTLE。

dp[i] := 長さをちょうどiにするのに必要な最小コストとする。長さをiにするには、長さがiの約数dになった時にコピーしてペーストを(i - d) / d回する。 iの約数の個数は高々 ${ 2\sqrt n }$ らしいのでO( ${ n\sqrt n }$ )となりAC。

長さがn-1の時にコピーしてペースとしたら2n-2になるので、dp[2n-2]まで計算する。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;

int main()
{
  int N, C, V; cin >> N >> C >> V;
  ll dp[2*N]; FOR(i,0,2*N) dp[i] = 1e9;
  dp[0] = dp[1] = 0;
  // ちょうどiにする
  FOR(i, 1, 2*N) {
    // Aの個数がiの約数dになったらコピーしてそのあとペースト
    // (i / d - 1) 回足せばちょうどiになる
    for(int d = 1; d * d <= i; d++) {
      if(i % d == 0) {
        dp[i] = min(dp[i], dp[d] + C + V * (i / d - 1));
        dp[i] = min(dp[i], dp[i/d] + C + V * (d - 1));
      }
    }
  }
  ll ans = dp[N];
  FOR(i, N, 2 * N) ans = min(ans, dp[i]);
  cout << ans << endl;
  return 0;
}

No.556 仁義なきサルたち

Union-Findを使う。子分の数を保存しておく。

xとyが喧嘩したらxとyを同じグループにする。この時子分の数が多い方を親とする。子分の数が同じ時はx<yならxを親にする。x>yならyを親にする。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
// union - find tree !!!!!!!!!!!!!!!!!!!!!!!!!
vector<int> par; //oya
vector<int> rnk; //子分の数
// n要素で初期化
void init(int n){
    par.resize(n);rnk.resize(n);
    FOR(i, 0, n){par[i] = i;rnk[i] = 1;}
}
//木の根を求める
int find(int x){
    if(par[x] == x) return x;
    else return par[x] = find(par[x]);
}
//xとyの属する集合を併合
void unite(int x, int y){
    x = find(x);y = find(y);
    if(x == y) return;
    if(rnk[x] < rnk[y]) swap(x, y);
    if(rnk[x] == rnk[y] && x > y) swap(x, y);
    par[y] = x;
    rnk[x] += rnk[y];
    rnk[y] = 0;
    return;
}
int main()
{
  int N, M;
  cin >> N >> M;
  init(N+1);
  FOR(i,0,M) {
    int a, b; cin >> a >> b;
    unite(a, b);
  }
  FOR(i,1,N+1) {
    cout << find(i) << endl;
  }
  return 0;
}

No.557 点対称

それぞれの桁に何通りの数字がありえるのか考える。

そして全てかける。

ただし、最大で ${ 5^{10^{18}} }$ くらいの計算をする必要が出てくるのでTLEに注意。

高速に(O(log n))累乗を計算するテクニックを使う必要がある。

例えば、aの8乗を計算する時はaを8回かけるよりa->a×a->(a²)×(a²)->(a⁴)×(a⁴)というように掛け算した結果を使用した方が早い。a ×= aを3回計算すれば終わる。 100乗の場合100 = 64(2⁶) + 32(2⁵) + 4(2²)であり、a ×= aを5回計算すれば終わる。100を2進数にした時に右のbitから調べていき1になっている時にaを足せば良い。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
const int mod = 1e9 + 7;
int main()
{
  ll N; cin >> N;
  if(N == 1) {
    cout << 2 << endl;
    return 0;
  }
  ll ans;
  if(N % 2 == 1) ans = 3;
  else ans = 1;
  // 5^(N/2-1)を高速に計算
  ll j = 0;
  ll fi = 5;
  ll p = N / 2 - 1;
  while((1LL<<j) <= p) {
    if((p>>j)&1) {
      ans *= fi;
      ans %= mod;
    }
    fi *= fi;
    fi %= mod;
    j++;
  }
  ans *= 4;
  cout << ans % mod << endl;
}