2017-09-28

SRM602 div2 Med PilingRectsDiv2

SRM 競技プログラミング

問題読み間違えて詰んでた

問題概要

・幅Xi高さYiの長方形がN個ある
・面積がlimit以上となるように長方形を重ねる(はみ出して良い、はみ出したらいけないと思っていた)
・90度回転して良い
・最大で何枚重ねられるか

方針

まず幅>高さとなるようにし、幅で昇順に並び替える。重ねる長方形の最小の幅を固定し重ねた時にlimitを超えるかどうか調べる。超えるなら重ねる。

最小の幅がO(N)。それぞれの最小の幅について幅が最小の幅以上の長方形についてlimitを超えるかどうかの計算でO(N)。よって計算量はO(N²)。

コード

typedef pair<int, int> P;
class PilingRectsDiv2 {
public:
  int getmax(vector <int> X, vector <int> Y, int limit) {
    int n = X.size();
    vector<P> v(n);
    FOR(i,0,n) {
      if(X[i] < Y[i]) swap(X[i], Y[i]);
      v[i] = P(X[i], Y[i]);
    }
    sort(v.begin(), v.end());
    int ans = -1;
    FOR(i,0,n) {
      int cnt = 0;
      FOR(j,i,n) if(v[i].first * min(v[i].second, v[j].second) >= limit) cnt++;
      if(cnt) ans = max(ans, cnt);
    }
    return ans;
  }
};

英語難しい

2017-09-27

SRM601 div2 Med WinterAndCandies

SRM 競技プログラミング

問題概要

・i番目のキャンディーのタイプはa_i

・タイプが1,2,3...,Kまで1つずつになるようにキャンディーを選ぶ選び方は何通りか

方針

・K = 1の時

1の個数

・K = 2の時

1の個数×2の個数

・K = xの時

1の個数×2の個数×...×xの個数

となるのでこれらを全て足した値が答え。

コード

class WinterAndCandies {
  public:
    int getNumber(vector <int> type) {
      int ret = 0;
      int num[51]; CLR(num);
      FOR(i,0,(int)type.size()) {
        num[type[i]]++;
      }
      int t = 1;
      FOR(i,1,51) {
        t *= num[i];
        ret += t;
      }
      return ret;
    }
};

2017-09-24

SRM600div2 Med ORSolitaireDiv2

SRM 競技プログラミング

今日からSRMdiv2med埋め開始(atcoderレート1469)

TopCoder Statistics - Match Overview

例えばgoal = 00101110の時、goalのbitが0となっている桁が1になっている数字は取り除く必要はない。 10001111は取り除く必要なし。00101000は取り除く可能性がある。取り除く可能性がある数字の集合からgoalを作れないようにするには最小で何個の数字を取り除けば良いかという問題。

集合の数字にについて、桁ごとに1が立っている数字が何個あるか調べて、その最小値を答えれば良い。

class ORSolitaireDiv2{
  public: int getMinimum(vector <int> numbers, int goal) {
    int n = numbers.size();
    int ret = 1e9;
    int bit[30]; CLR(bit);
    FOR(i,0,n) {
      bool ok = true;
      FOR(j,0,30) {
        if((numbers[i]>>j)&1 && !((goal>>j)&1)) ok = false;
      }
      if(!ok) continue;
      FOR(j,0,30) {
        if((numbers[i]>>j)&1) bit[j]++;
      }
    }
    FOR(j,0,30) if((goal>>j)&1) ret = min(ret, bit[j]);
    return ret;
  }

2017-09-23

ディスカバリーチャンネルコードコンテスト2016 C - ロト2

やり直し AtCoder 数学

できなかったのでやり直し。

C: ロト2 - DISCO presents ディスカバリーチャンネルコードコンテスト2016 予選 | AtCoder

x * y が kの倍数 <=> gcd(x, k) * gcd(y, k) が kの倍数という性質を用いる。

計算量はO(N²) -> O(Kの約数の個数²)になる。

今回Kの約数は1344個らしい。

gcd(Ai, K)の値をmapに保存しておいて、Kの倍数になるか2重ループで調べる。 gcd(Ai, K) * gcd(Aj, K) % K == 0となる時、 map[gcd(Ai, K)] == map[gcd(Aj, K)] の時はmap[gcd(Ai, K)]個から2個選ぶ選び方の数、そうでない時はmap[gcd(Ai, K)] * map[gcd(Aj, K)]。ただし、二重ループで重複して数えてしまうので最後に2で割って足した。

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
//最大公約数
ll gcd(ll a, ll b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll N, K; cin >> N >> K;
  map<ll, ll> MAP;
  FOR(i,0,N) {
    ll in; cin >> in;
    MAP[gcd(K, in)]++;
  }
  ll ans = 0;
  ll ans2 = 0;
  for(auto m1 : MAP) {
    for(auto m2 : MAP) {
      if((m1.first * m2.first) % K == 0) {
        if(m1.first != m2.first) {
          ans2 += m1.second * m2.second;
        } else {
          ans += m1.second * (m2.second - 1) / 2;
        }
      }
    }
  }
  cout << ans + ans2 / 2 << endl;
  return 0;
}

2017-08-12

ABC070 参加記録

AtCoder 競技プログラミング

ABCしかなかったのでABC070に参加しました。

100-200-300-400なので全完できた。

A - Palindromic Number

やるだけ。

int main()
{
  string s;
  cin >> s;
  if(s[0] == s[2]) {
    puts("Yes");
  } else {
    puts("No");
  }
  return 0;
}

B - Two Switches

場合分けしまくればO(1)でできるんだろうけどめんどくさいのでいもす法ぽくやった0(N)。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
int main()
{
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  int sw[111]; FOR(i,0,111) sw[i] = 0;
  sw[a]++;sw[b]--;sw[c]++;sw[d]--;
  FOR(i,1,111) sw[i] += sw[i-1];
  int ans = 0;
  FOR(i,0,111) if(sw[i] == 2) ans++;
  cout << ans << endl;
  return 0;
}

C - Multiple Clocks

次に全ての針が上むきで揃うのは全ての針の周期の最小公倍数秒後になる。

最小公倍数求めるライブラリ作っておくと良い。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
//最大公約数
ll gcd(ll a, ll b) {
  while (a && b) {
    if (a >= b) a %= b;
    else b %= a;
  }
  return a + b;
}
//最小公倍数
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b;}
int main()
{
  int N; cin >> N;
  ll ans = 1;
  FOR(i,0,N) {
    ll in; cin >> in;
    ans = lcm(ans, in);
  }
  cout << ans << endl;
  return 0;
}

D - Transit Tree Path

絶対にKを経由するのでKからそれぞれの頂点iまでの最短距離d[i]を求めておいてd[x]+d[y]を出力すればOK。

今回のグラフは木なので最短距離を求めるのはdfsでもダイクストラでもどっちでも良さそう。

#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
typedef long long ll;
typedef pair<ll, ll> P;
const ll inf = 1e15;
struct edge{
  ll to, cost;
  edge(ll t, ll c) {
    to = t, cost = c;
  }
};
// Kからの距離を求めておく
int N;
vector<edge> G[100005];
ll d[100005];
void dijkstra(int s){
  priority_queue<P, vector<P>, greater<P> >que;
  FOR(i,1,N+1) d[i] = inf;
  d[s] = 0;
  que.push(P(0, s));
  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[v] < p.first) continue;
    for(auto &e : G[v]){
      if(d[e.to] > d[v] + e.cost){
        d[e.to] = d[v] + e.cost;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}
int main()
{
  cin >> N;
  FOR(i,0,N-1) {
    ll a, b, c;
    cin >> a >> b >> c;
    G[a].push_back(edge(b, c));
    G[b].push_back(edge(a, c));
  }
  int Q, K; cin >> Q >> K;
  // Kからの距離
  dijkstra(K);
  FOR(i,0,Q) {
    int x, y; cin >> x >> y;
    cout << d[x] + d[y] << endl;
  }
  return 0;
}

2017-08-12

yukicoder 171 参加記録

競技プログラミング yukicoder

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;
}