【AtCoder】ABC038 C. 単調増加

AtCoder 競技プログラミング

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 競技プログラミング 動的計画法 深さ優先全探索 メモ化再帰

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 競技プログラミング 全探索

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

GCJ 競技プログラミング 面白い 動的計画法

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

【AtCoder】ABC040 B. □□□□□

AtCoder 競技プログラミング 全探索

AtCoderの問題

B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder

参考書

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

難しさ（初心者目線）

・考え方**

・実装*

・面白さ***

問題概要

・大きさが同じn枚の正方形の紙がある
・何枚かを使って長方形(正方形も含む)を作る
・その時|縦の長さ-横の長さ|+使わないカードの枚数を最小にしたい
・最小値を求めよ

n≦100,000

方針

作れる長方形と余りを全探索で求める.
縦の長さを1からsqrt(n)まで探索する.
nまで探索する必要はない.
例えばn=10の時、 {1 \times 10}も{10 \times 1}も同じだから.
このようにすれば {n \leq 10^{12}}くらいでも時間内に終わる.
素数かどうかの判定で使われる手法.

コード

#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 min_amari = 999999999;
    //全探索
    for(int i=1; i<=sqrt(n); ++i){
        int w, h, amari;
        w = i;
        h = n / i;
        amari = n % i;
        min_amari=min(min_amari,abs(w-h)+amari);
    }
    cout<<min_amari<<endl;
}

【AtCoder】ABC044 C. 高橋君とカード

AtCoder 競技プログラミング 動的計画法

AtCoderの問題

C: 高橋君とカード / Tak and Cards - AtCoder Beginner Contest 044 | AtCoder

参考書

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

現在AtCoderの過去問AB(たまにC)解いてます.

難しさ（初心者目線）

・考え方***

・実装**

・面白さ**

問題概要

・数字がN個ある(x_1,x_2,\dots,x_N)
・何個か使ってAで割り切れる数を作りたい
・何通りあるか?

方針

・動的計画法
・dp[i][j][k]:=x_1,x_2,\dots,x_iまででj個使ってkを作れる総数

x_iを使うか使わないかの漸化式が考えられる
- 使わない場合は使う個数jとkは変わらない
dp[i+1][j][k] += dp[i][j][k]
- 使う場合は使う個数+1、kはk+x[i]
dp[i+1][j+1][k+x[i]] += dp[i][j][k]

コード

#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)

ll dp[60][60][3000];
ll N,A;
ll x[60];

int main(){
    cin>>N>>A;
    FOR(i, 0, N) cin>>x[i];
    FOR(i, 0, 60) FOR(j, 0, 60) FOR(k, 0, 3000) dp[i][j][k] = 0;
    dp[0][0][0] = 1;
    FOR(i, 0, N){
        FOR(j, 0, N){
            FOR(k, 0, 3000){
                if(dp[i][j][k]==0) continue;
                //使わない時
                dp[i+1][j][k] += dp[i][j][k];
                //使う時
                dp[i+1][j+1][k+x[i]] += dp[i][j][k];
            }
        }
    }
    ll ans = 0;
    FOR(i, 1, N+1){
        ans += dp[N][i][i*A];
    }
    cout << ans << endl;
}

【RCO】日本橋ハーフマラソン予選 A問題

AtCoder マラソン RCO 競技プログラミング

AtCoderで開催された日本橋ハーフマラソンの予選のA問題です.
A問題に時間をかけすぎてBが悲惨なことになりました.
ちなみに予選115位でした…

A: Multiple Pieces - RCO presents 日本橋ハーフマラソン 予選 | AtCoder

参考書

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

問題概要

・50*50のマスに0~9の数字が書いてある
・9個の連結したマスを1グループとする
・グループ内の数同士の掛け算をそのグループの得点とする
・全てのグループの得点の和が最終的なスコア
・スコアを最大化するようにグループを作ってください

方針

・なるべく大きい数同士同じグループにしたい
と思ったので、実装しやすそうな9の周りから大きい数字を選んで行くという方法をとりました。

実装例

焦って書いたコードなので汚いです.
このコードだとA問題だけでは75位でした.

#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 H, W, K;
vector<string> inputmass;
int mass[51][51];
bool used[51][51];
typedef pair<int, int> YX;//座標
typedef pair<int, YX> P;//値,座標

int main(){
    cin >> H >> W >> K;
    cin.ignore();
    FOR(i, 0, H){
        string s;
        getline(cin, s);
        inputmass.push_back(s);
    }
    FOR(i, 1, 51){
        FOR(j, 1, 51){
            mass[i][j] = inputmass[i-1][j-1] - '0';
        }
    }
    //連結できるならqueに入れておく
    //4方向を見る
    int vx[4] = {0, 1, 0, -1};
    int vy[4] = {-1, 0, 1, 0};
    priority_queue<P> que;
    stack<YX> output;
    int C = 0;
    //9の周りでグループ作る->8の周りで->...
    for(int num = 9; num > 0; --num){
    FOR(yi, 1, H+1){
        FOR(xi, 1, W+1){
            //すでに使われていたらもしくわnum(9->8->7->...)でなければcontinue
            if(used[yi][xi]==true || mass[yi][xi] != num) continue;
            while(!que.empty()) que.pop();
            que.push(P(mass[yi][xi],YX(yi, xi)));
            used[yi][xi] = true;
            //queの周りを調べる
            //0出なければ連結させる
            int k = 0;//グループ内の数の個数-1
            while(1){
                if(k==8){
                    C++;
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;//あまりは戻す
                    }
                    break;
                }
                //8個できるまでに連結できなかったら戻す
                if(que.empty()){
                    FOR(kesu, 0, k){
                        YX yx = output.top();output.pop();
                        used[yx.first][yx.second] = false;//グループにできてないので戻す
                    }
                    while(!que.empty()){
                        P p = que.top();que.pop();
                        used[p.second.first][p.second.second] = false;
                    }
                    break;
                }
                //使うところを保存
                P p = que.top();que.pop();
                output.push(p.second);//あとで出力する
                k++;
                //周りを調べる
                int y0 = p.second.first;
                int x0 = p.second.second;
                FOR(vi, 0, 4){
                    if(y0 + vy[vi] <= 0 || y0 + vy[vi] > H || x0 + vx[vi] <= 0 || x0 + vx[vi] > W) continue;
                    if(mass[y0+vy[vi]][x0+vx[vi]]==0 || used[y0+vy[vi]][x0+vx[vi]]==true) continue;
                    que.push(P(mass[y0+vy[vi]][x0+vx[vi]],YX(y0+vy[vi], x0+vx[vi])));
                    used[y0+vy[vi]][x0+vx[vi]] = true;
                }
            }
        }
    }
    }
    cout << C << endl;
    while(!output.empty()){
        YX yx = output.top();output.pop();
        cout << yx.first << " " << yx.second << endl;
    }
}

コメント

1個隣だけでなく何個か先も見て得点が大きくなる場合を探す方法でやってみようと思います。