競プロ日記

プロコン参加記録とか解いた問題とか

ABC070 参加記録

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

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(n2)となるので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(n2)となり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->(a2)×(a2)->(a4)×(a4)というように掛け算した結果を使用した方が早い。a ×= aを3回計算すれば終わる。 100乗の場合100 = 64(26) + 32(25) + 4(22)であり、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;
}

問題集(随時更新)

全探索(工夫して全探索も)

http://arc020.contest.atcoder.jp/tasks/arc020_2

https://www.hackerrank.com/challenges/two-characters

http://poj.org/problem?id=3279

http://abc002.contest.atcoder.jp/tasks/abc002_4

http://arc074.contest.atcoder.jp/tasks/arc074_b

深さ優先全探索dfs

http://arc001.contest.atcoder.jp/tasks/arc001_3

http://arc009.contest.atcoder.jp/tasks/arc009_3

メモ化再帰

http://tenka1-2012-final.contest.atcoder.jp/tasks/tenka1_2012_final_a

http://wupc2nd.contest.atcoder.jp/tasks/wupc_02

幅優先全探索

http://arc005.contest.atcoder.jp/tasks/arc005_3

http://arc001.contest.atcoder.jp/tasks/arc001_2

https://www.hackerrank.com/contests/w32/challenges/circular-walk

動的計画法dp

http://wupc2nd.contest.atcoder.jp/tasks/wupc_02

http://abc054.contest.atcoder.jp/tasks/abc054_d

https://www.hackerrank.com/contests/world-codesprint-10/challenges/permutation-happiness

bit

http://arc007.contest.atcoder.jp/tasks/arc007_3

bit , nCrの計算

https://www.hackerrank.com/contests/world-codesprint-10/challenges/maximal-and-subsequences

bit+dp

http://arc010.contest.atcoder.jp/tasks/arc010_3

メモ化再帰+dp+bit???!!! - > 再帰関数の中にdp…

https://www.hackerrank.com/contests/rookierank-3/challenges/max-score

貪欲法

http://arc006.contest.atcoder.jp/tasks/arc006_3

http://abc003.contest.atcoder.jp/tasks/abc003_3

ベルマンフォード法

http://abc061.contest.atcoder.jp/tasks/abc061_d

Union-Find tree

http://poj.org/problem?id=1182

クラスカル

http://poj.org/problem?id=3723

しゃくとり法

http://abc038.contest.atcoder.jp/tasks/abc038_c

http://poj.org/problem?id=3061

累積和

http://abc037.contest.atcoder.jp/tasks/abc037_c

二次元累積和

http://agc015.contest.atcoder.jp/tasks/agc015_c

クラスカル法, 自作の評価関数でsort, 最小公倍数, 平均最大化with二分探索

https://www.hackerrank.com/contests/w31/challenges/spanning-tree-fraction

関数の最大化最小化with二分探索

http://poj.org/problem?id=1064

http://poj.org/problem?id=2456

https://www.codechef.com/SNCKPA17/problems/CONSESNK

stack (使う必要ないやつもある)

https://www.hackerrank.com/challenges/reduced-string

https://www.hackerrank.com/challenges/counting-valleys

いもす法

http://abc001.contest.atcoder.jp/tasks/abc001_4

半分全列挙

http://poj.org/problem?id=2785

強連結成分分解, トポロジーソート??!!, bitset

https://www.hackerrank.com/contests/world-codesprint-11/challenges/hackerland

【AtCoder】ABC038 C. 単調増加

AtCoderの問題

C: 単調増加 - AtCoder Beginner Contest 038 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方***

・実装**

・面白さ***

問題概要

・N個の数からなる数列{a_1, a_2, \dots , a_N}が与えられる.
{a_l, a_l+1, \dots , a_r}が単調増加、すなわち l≦r であってa_i<a_i+1がl≦i<r を満たす全てのiに対して成り立つような(l,r)の数を求めよ.

制約
1 ≦ N ≦ 105

方針

・普通にあるlに対して最大のrを求める方法だと最悪O(N2).
・あるlに対して最大のrを求めたら、l+1<rの時l+1に対しても同じrとなる.
・l+1=rとなったら再び最大のrを求める.
・よって全てのlの合計でrを探すのにN回しかループしないのでO(N)となり間に合う.

コード

#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>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//答え見た

int main(){
    int N;
    cin >> N;
    int a[N+1];
    FOR(i, 0, N) cin>>a[i];
    a[N] = 0;
    int l = 0, r = 0;
    ll ans = 0;
    while(l < N){
        while(a[r+1] > a[r]) r++;
        ans += r - l + 1;
        l++;
        if(l==r+1) r++;
    }
    cout << ans << endl;
}

【AtCoder】ABC040 C. 柱柱柱柱柱

AtCoderの問題

C: 柱柱柱柱柱 - AtCoder Beginner Contest 040 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方**

・実装***

・面白さ**

問題概要

・柱が1列にN本並んでいる.
・それぞれの柱の高さは{a_1, a_2, \dots , a_N}である.
・1本目からN本目まで飛び移りながら移動したい.
・飛び移るには飛び移る前と後の柱の高さの差の絶対値の体力を消耗する.
・最大1本飛ばしできる.
・消費する体力を最小にしたい、最小値を求めよ.

方針

動的計画法か深さ優先全探索(メモ化再帰)で解くことができる.好みだと思う.

動的計画法の場合

dp[i]:=i番目の柱に行くために消費する体力の最小値とする.
これは1個前から来た方が良いのか2個前から来た方が良いのかの二択である(1個前と2個前の柱に行くために消費する体力はすでに最小値を求めているので).
つまり dp[i] = min(dp[i-1]+1個前の柱との差の絶対値, dp[i-2]+2個前の柱との差の絶対値)
2本目の柱は1本目の柱からしか来れないことに注意.

深さ優先全探索の場合

メモ化再帰を用いてとく.

動的計画法コード

#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>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

//動的計画法
//dp[i]:=i番目の柱に行く最小値

int a[100000];
int N;
ll dp[100001];
int main(){
    cin>>N;
    FOR(i, 0, 100000) a[i] = 0;
    FOR(i, 0, N) cin>>a[i];
    FOR(i, 0, 100001) dp[i] = 999999999999;
    dp[0] = 0;
    dp[1] = 0;//1番目の柱に行く最小値はもちろん0
    dp[2] = abs(a[1] - a[0]);//2番目の柱には1番目からくるしかない
    FOR(i, 3, N+1){
        //1個前と2個前どっちからきた方がi番目は最小値になるか
        dp[i] = min(dp[i-2]+abs(a[i-1]-a[i-3]), dp[i-1]+abs(a[i-1]-a[i-2]));
    }
    cout << dp[N] << endl;
}

メモ化再帰コード

#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>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int a[100000];
int N;
ll INF = -1;
//再帰関数+メモ化
//位置は0~N-1
ll dp[100000][2];
ll dfs(int n, int bef){
    //N本目についたらおしまい
    if(n == N-1) return abs(a[N-1] - a[n-bef]);
    //N本目を超えてしまう場合注意
    if(n == N) return abs(a[N-1] - a[N-2]);
    //すでに計算済みならそれを返す
    if(dp[n][bef-1]!=INF) return dp[n][bef-1];
    
    ll ret = abs(a[n] - a[n-bef]);
    ret += min(dfs(n+1, 1), dfs(n+2, 2));
    return dp[n][bef-1] = ret;
}

int main(){
    cin>>N;
    FOR(i, 0, 100000) a[i] = 0;
    FOR(i, 0, N) cin>>a[i];
    FOR(i, 0, 100000) FOR(j, 0, 2) dp[i][j] = INF;
    cout << min(dfs(1, 1), dfs(2, 2)) << endl;
}

【AtCoder】ABC042 C. こだわり者いろはちゃん

AtCoderの問題

C: こだわり者いろはちゃん / Iroha's Obsession - AtCoder Beginner Contest 042 | AtCoder

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方*

・実装**

・面白さ*

問題概要

{1\leq N \leq10000}が与えられる.
・0~9までのうち使用できない数字が与えられる.
・使用できる数値でN以上の最小値を求めよ.

方針

・Nが小さいので全探索できる(1~10*Nまで調べていく).
・1桁ずつ小さい数字から使用できるかを調べていく方法だとN=999で9が使えない時に繰り上がりを考えないといけないので面倒.

コード

#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>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int N;
    int K;
    cin>>N>>K;
    bool D[10];//嫌な数字ならtrue
    FOR(i, 0, 10) D[i] = false;
    FOR(i, 0, K){
        int d;
        cin>>d;
        D[d] = true;
    }
    //全探索
     FOR(i, 0, 10*N){
        if(N<=i){
            int check = true;
            string s = to_string(i);
            FOR(j, 0, s.length()){
                if(D[s[j]-'0']) check = false;
            }
            if(check){
                cout << i << endl;
                return 0;
            }
        }
     }
}

【GCJ】2009_1C Problem C. Bribe the Prisoners

AtCoderの問題

Dashboard - Round 1C 2009 - Google Code Jam

参考書

プログラミングコンテストチャレンジブック [第2版]

難しさ(初心者目線)

・考え方*****

・実装***

・面白さ****

問題概要

・P人の囚人が一列の牢屋にいる(独房)
・あなたはQ人を解放したい
・解放する囚人は{a_1,a_2,\dots,a_q}番目の牢屋にいる(1~P番目の内Q人)
・解放する順番は自由で1人ずつ
・解放する際に隣の囚人に解放がバレるので金貨を1枚渡さなければならない
・ただし、隣の隣にも伝達して伝わるので伝達する囚人全てに1枚渡す必要がある
・必要な金貨の最小値を求めよ

方針

dp[i][j]:={a_i}番目の牢屋と{a_j}番目の牢屋の間にいる解放したい囚人を解放する(両端は含まない)時に必要な金貨の最小値とする.
簡単のために0番目とP+1番目の牢屋を追加する.
dp[k][k+1]は間に1人も解放したい囚人がいないので0である.
まずはdp[k][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>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int P,Q;
int A[100+2];//両端追加

int dp[101][102];
void solve(){
    //幅が1以下の時は0
    FOR(i, 0, Q+1) dp[i][i+1] = 0;
    //幅
    FOR(w, 2, Q+2){
        //左端
        for(int i=0; i+w<=Q+1; ++i){
            //右端
            int j = i + w;
            //2番目以降で解放に必要な金貨
            int t = 99999999;

            //全探索
            for(int k=i+1; k<j; ++k){
                t = min(t, dp[i][k]+dp[k][j]);
            }

            //i-jの間の1人目の囚人を解放するのに必要な金貨は場所によらない
            dp[i][j] = t + A[j] - A[i] - 2;
        }
    }
    cout << dp[0][Q+1] << endl;;
}

int main(){
    cin >> P >> Q;
    A[0] = 0;
    A[Q+1] = P + 1;
    FOR(i, 1, Q+1) cin >> A[i];
    solve();
}