2017-03-01

【CODEFORCES】Pupils Redistribution

CODEFORCES 競技プログラミング

CODEFORCEの問題を解きました.

http://codeforces.com/contest/779/problem/A

難しさ（初心者目線）

・考え方**

・実装*

・面白さ*

問題

幸多高校には2つのクラス（A,B）があります.
クラスの人数は共にn人です.
クラス対抗プログラミングコンテストを行ったところ、クラスAとクラスBのそれぞれの人の成績がa_1,a_2,…,a_n,b_1,b_2,…,b_nとなりました.
成績は1,2,3,4,5点でつけられます.
片方のクラスが極端に強くなってしまってはつまらないので、それぞれのクラスの人の成績の和が等しくなるように生徒を交換したいです.
交換は1人対1人で行います.
それぞれのクラスの生徒の成績が与えられるので、最小で何回の交換を行うことで、クラスAとクラスBの生徒の成績の和を等しくできるか求めてください.

制約

1≦n≦100（整数）
1≦a_i,b_i≦5（整数）

入力

n
a_1 a_2 … a_n
b_1 b_2 … b_n

出力

最小値を出力
等しくできない場合は-1を出力

方針

・それぞれの成績の人の人数が偶数でないといけない
・それぞれの成績の人の人数が偶数の場合O(n)で解くことができる

コード

WhyamIhereさんのコード参考にしました.

#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 pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    int n;
    cin >> n;

    //a[i]:クラスAの成績iが何人いるか
    //total[i]:クラスA,Bで成績iが何人いるか
    int a[6] = {0}, b[6] = {0}, total[6] = {0};
    FOR(i, 0, n){
        int input;
        cin >> input;
        a[input]++;total[input]++;
    }
    FOR(i, 0, n){
        int input;
        cin >> input;
        b[input]++;total[input]++;
    }

    //それぞれの成績の人が偶数でないと二つのクラスに分けられない
    FOR(i, 1, 6){
        if(total[i]%2==1){
            cout << -1 << endl;
            return 0;
        }
    }

    //分けられる場合
    //目指す値との差が2*xならx回交換すれば良い
    int ans = 0;
    FOR(i, 1, 6){
        ans += abs(total[i] / 2 - a[i]);
    }
    ans /= 2;
    cout << ans << endl;
}

2017-03-01

【CODEFORCES】Weird Rounding

CODEFORCES 競技プログラミング

CODEFORCEの問題を解いた.

http://codeforces.com/contest/779/problem/B

難しさ（初心者目線）

・考え方*

・実装*

・面白さ*

問題

コウタ君は数を $10^{k}$ で割るのが大好きです.
今日は整数nを $10^{k}$ で割ろうと思います.
コウタ君はnが $10^{k}$ で割り切れないと怒るので、割り切れるようにいくつかの桁の数字を削除してあげてください.
削除すべき数の最小値を出力してください.
最上位の桁は0ではありません.
削除したら桁が1つ少なくなります.
例えば30020で十の位の2を削除したら3000になります.
削除する必要がない場合は0を出力してください.

入力

0≦n≦2 000 000 000（整数）
1≦k≦9（整数）

出力

最小値を出力

ヒント

コード

WhyamIhereさんのコード参考にしました.

#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 pb         push_back
#define mp         make_pair
#define ll         long long
#define PI         acos(-1.0)
#define ALL(A)     ((A).begin(), (A).end())
#define vsort(v)   sort(v.begin(),v.end())
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

int main(){
    //stringに格納した方が楽
    string s;
    int k;
    cin >> s >> k;

    //0の数を数える
    int zero = 0;
    FOR(i, 0, s.length()){
        if(s[i]=='0') zero++;
    }

    int dels = 0;
    //0の数が1の位から数えてkになると割り切れる
    if(k <= zero){
        zero = 0;
        for(int i=s.length()-1; i>=0; --i){
            if(s[i]=='0'){
                zero++;
            }else{
                dels++;
            }
            if(zero>=k) break;
        }
        cout << dels << endl;
        return 0;
    }
    //0にしないと割り切れない(0はどんな数字でも割り切れる)
    else{
        cout << s.length()-1 << endl;
        return 0;
    }
}

string使えばよかった.

2017-03-01

【yukicoder】No.47 ポケットを叩くとビスケットが２倍

yukicoder 競技プログラミング

yukicoderさんの問題です.

http://yukicoder.me/problems/no/47

難しさ（初心者目線）

・考え方*

・実装

・面白さ**

ヒント

コード

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

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

//最初は1枚しかないのでN-2^k>=0を満たす最大のkを求める
//=0がなり立てばkが答え
//>ならば足りない枚数をポケットに入れて叩けばOK
//持っている枚数>足りない枚数を満たしている
//答えはk+1
int main(){
    ll int N;
    cin >> N;
    int k = 0;
    while(N-pow(2, k)>0) k++;
    cout << k << endl;
}

2017-03-01

【yukicoder】No.3 ビットすごろく

yukicoder 競技プログラミング幅優先全探索

yukicoderさんの問題

http://yukicoder.me/problems/no/3

参考書

プログラミングコンテストチャレンジブック [第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>
using namespace std;

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

//方針
//2進数にした時の1の個数はbitsetか1<<iを使えば良い?
//----> __builtin_popcountめちゃ便利だった
//各マスに到達できる最小の回数を設定（初期値はINF）
//移動した時に最小値を更新できたらqueueに保存(1~N以外はcontinue)
//queueから一個取り出して次のマスを考える
//queueが空になったら終わり

int main(){
    int N;
    cin >> N;

    int bit1[N+1];
    //マスごとの2進数にした時の1の数を保存しておく
    FOR(i, 0, N+1){
        bit1[i] = __builtin_popcount(i);
    }

    //quに次に始点となるマス番号を保存
    queue<int> qu;
    qu.push(1);

    //マスまで行くための最小値初期はINF
    int d[N+1];
    int INF = 99999999;
    fill(d, d+N+1, INF);
    d[1] = 0;

    while(!qu.empty()){
        //今見ている場所
        int now_x = qu.front();
        qu.pop();

        //Nに着いてたら次は調べない
        if(now_x == N) continue;

        //次に見る場所の候補
        int next_x1 = now_x + bit1[now_x];
        int next_x2 = now_x - bit1[now_x];

        //次見る場所が1~Nの中にあるかどうか
        if(next_x1 >= 1 && next_x1 <= N){
            //短い経路だったら次も調べる
            if(d[next_x1] > d[now_x] + 1){
                qu.push(next_x1);
                d[next_x1] = d[now_x] + 1;
            }
        }
        if(next_x2 >= 1 && next_x2 <= N){
            if(d[next_x2] > d[now_x] + 1){
                qu.push(next_x2);
                d[next_x2] = d[now_x] + 1;
            }
        }
    }
    cout << (d[N]==INF ? -1 : d[N]+1) << endl;
}

2進数にした時の1の数を求める方法どうやるか迷ってたけど
__builtin_popcountめちゃ便利だった.
bitset使ってもできるようです
1の数が求められたらあとは幅優先全探索すればOK

2017-03-01

【CODEFORCES】Code For 1

CODEFORCES 競技プログラミング深さ優先全探索面白い

CODEFORCESの問題

http://codeforces.com/contest/768/problem/B

プログラミングコンテストの参考書

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

難しさ

・考え方***

・実装***

・面白さ*****

問題文（日本語訳）

コウタ君はある整数xを $\frac{x}{2}$ ,x mod 2, $\frac{x}{2}$ に分解するのが好きです.
コウタ君は整数nが与えられたので、nが0か1になるまで上記の分解をし1が何個あるか知りたいと思いました.
例えばn=10の場合は[10]->[5 0 5]->[2 1 2 0 2 1 2]->[1 0 1 1 1 0 1 0 1 0 1 1 1 0 1]となり、1の数は10です.
しかし昨夜徹夜でゲームをしていたコウタ君は眠いです.
そこであなたはコウタ君の代わりに[n]を0か1になるまで分解した時に左からlとrの間にある1の数を数えてください.

入力
$0≦n≦2^{50}$
$1≦l$
$1≦r$

ただし、[tex:r-l≦10⁵]

出力
lからrの間にある1の数
lとrにある1も含む

方針

・愚直に実装して全部の01求めようとしたら地球爆発するのでlとrの間だけ調べるように工夫する

・深さ優先全探索？再帰関数使う

コード

色々な方のコードを参考にしています.

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

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

//入力
ll int l, r;

//全部分解したら長さがどのくらいになるか
ll getLength(ll x){
    return (x <= 1) ? 1 : (getLength(x/2)) * 2 + 1 ;
}

//nを分解,Lはnが広がるであろう左端,Rは右端
int dfs(ll n, ll L, ll R){

    //範囲外ならこれ以上探索しない
    if(L > r || R < l) return 0;

    //おかしいのでreturn 0
    if(L>R) return 0;

    //0か1になったら出力
    if(n<=1){
        if(L>=l && R<=r) return n;
        else return 0;
    }

    //分解した時の中心
    ll m = (L + R) / 2;
    return dfs(n/2, L, m-1) + dfs(n%2, m, m) + dfs(n/2, m+1, R);
}

int main(){
    ll n;
    cin >> n >> l >> r;
    cout << dfs(n, 1, getLength(n)) << endl;
}

競プロ日記

nenuon

【CODEFORCES】Pupils Redistribution

難しさ（初心者目線）

問題

方針

コード

【CODEFORCES】Weird Rounding

難しさ（初心者目線）

問題

ヒント

コード

コメント

【yukicoder】No.47 ポケットを叩くとビスケットが２倍

難しさ（初心者目線）

ヒント

コード

コメント

【yukicoder】No.3 ビットすごろく

難しさ（初心者目線）

ヒント

コード

コメント

【CODEFORCES】Code For 1

難しさ

問題文（日本語訳）

方針

コード