TopCoder SRM 614 Div1 Easy MinimumSquare [1人競技プログラミング Advent Calendar 2016 14日目]

この記事は1人競技プログラミング Advent Calendar 2016 14日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
N(1<=N<=100)個の点のX座標とY座標が与えられる。(-1,000,000,000 <= x[i],y[i] <= 1,000,000,000)
K個(1<=K<=N)の点を含み、軸に平行で四隅の点の座標が整数である正四角形の最小の面積を求めよ。

解いた方法：
最初、ある1点を四隅に決め打ちして残りのもう1点を探索し、内包する点の数を数えればいいかと思ったらコーナーケースを見つけて断念。(十字に4点が置かれているケース)
K=1,K=2,K=3,それ以外の4つのケースで場合分けして計算。
・K=1のとき
適当などっかの点が含まれていればいいので4を返す。

・K=2のとき
2つの点を全探索して最小の面積を探す。

・K=3のとき
3つの点を全探索して最小の面積を探す。

・K<=4のとき
4点決め打ちしてその中にある点の数を数える。
こうすれば十字のケースの際をカバーできる。
O(NC4*N)で約4000万となり、頑張れば通る。(実際には1.4秒ぐらいのケースが最大だったっぽい)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class MinimumSquare {
    public:
    vector<int> x;
    vector<int> y;
    int K;
    LL minArea(vector<int> _xx, vector<int> _yy, int _KK) {
        x = _xx, y = _yy, K = _KK;

        LL ans,minx,miny,maxx,maxy,xx,yy,ss;
        ans = INFL;

        if(K == 1) return 4;
        if(K == 2){
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    xx = max(x[i],x[j]) - min(x[i],x[j]);
                    yy = max(y[i],y[j]) - min(y[i],y[j]);
                    ss = max(abs(xx), abs(yy)) + 2;
                    ans = min(ans, ss*ss);
                }
            }
        }else if(K == 3){
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    REP2(k, j+1, x.size()){
                        xx = max(max(x[i],x[j]),x[k]) - min(min(x[i],x[j]),x[k]);
                        yy = max(max(y[i],y[j]),y[k]) - min(min(y[i],y[j]),y[k]);
                        ss = max(abs(xx), abs(yy)) + 2;
                        ans = min(ans, ss*ss);
                    }
                }
            }
        }else{
            REP(i, x.size()){
                REP2(j, i+1, x.size()){
                    REP2(k, j+1, x.size()){
                        REP2(l, k+1, x.size()){
                            maxx = max(max(x[i],x[j]),max(x[k],x[l]));
                            minx = min(min(x[i],x[j]),min(x[k],x[l]));
                            maxy = max(max(y[i],y[j]),max(y[k],y[l]));
                            miny = min(min(y[i],y[j]),min(y[k],y[l]));
                            ss = max(abs(maxx-minx), abs(maxy-miny)) + 2;

                            int cnt = 0;
                            REP(m, x.size()){
                                cnt += (minx <= x[m] && x[m] <= maxx && miny <= y[m] && y[m] <= maxy);
                            }
                            if(K <= cnt){
                                ans = min(ans, ss*ss);
                            }
                        }
                    }
                }
            }
        }

        return ans;
    }
};

メロン・アップル / ブラック・ローズ [1人おうちカクテル Advent Calendar 2016 12・13日目]

昨日サボってしまったのでまとめて更新！

この記事は 1人おうちカクテル Advent Calendar 12・13日目の記事です。

名前：メロン・アップル
材料：メロンリキュール 1/4、アップルジュース 3/4
技法：ビルド

メロンリキュールでおすすめの飲み方を聞かれたら真っ先に答えたいのがこのカクテル！
メロンリキュールとアップルジュースを混ぜただけですが、メロンとアップルの甘さが非常にマッチしていて甘いカクテル好きな人には本当にオススメしたい一杯です！！

名前：ブラック・ローズ
材料：ホワイト・ラム 45ml、ブラックコーヒー 適量
技法：ビルド

コーヒーを使う珍しいカクテルです。初めてコーヒーを使ったカクテルを作りました。(コーヒーリキュールは除く)
ラムと混ぜていけるのか？と不安に思いながら口にしましたが、意外にありな味をしていて結構ビックリしています！
ラムを持っている人は是非一度試してみてください！

TopCoder SRM 613 Div1 Easy TaroFriends [1人競技プログラミング Advent Calendar 2016 13日目]

この記事は1人競技プログラミング Advent Calendar 2016 13日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
猫がN匹存在し、i番目の猫はx座標がcoordinates[i]の位置にいる。
全ての猫は、それぞれの位置から正の方向か負の方向にX(0<=X<=100,000,000)歩分移動させる必要がある。
両端の猫の位置が最も近くなるように移動した際の両端の猫の距離を求めよ。

解いた方法：
最初に猫の座標でソートする。
全ての猫が同じ座標でなければ、お互い中心に向かうように移動するのが最も猫の距離が近くなる。
ソート後折り返す位置を探索し、一番近い距離を探索すると解が出てくる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class TaroFriends {
    public:
    vector<int> coordinates;
    int X;
    int getNumber(vector<int> _coordinates, int _XX) {
        coordinates = _coordinates, X = _XX;

        sort(ALL(coordinates));
        int result = 2000000000;
        REP(i, coordinates.size()){
            int min_x = INF;
            int max_x = -INF;

            REP(j, i){
                int tmp = coordinates[j] + X;
                min_x = min(min_x, tmp);
                max_x = max(max_x, tmp);
            }
            REP2(j, i, coordinates.size()){
                int tmp = coordinates[j] - X;
                min_x = min(min_x, tmp);
                max_x = max(max_x, tmp);
            }

            result = min(result, max_x - min_x);
        }
        return result;
    }
};

TopCoder SRM 612 Div1 Easy EmoticonsDiv1 [1人競技プログラミング Advent Calendar 2016 12日目]

今日の分はサクッと解けた。

この記事は1人競技プログラミング Advent Calendar 2016 12日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
コンテストで良い成績を得たので友人に笑顔の絵文字を大量に送り付けます。
最初に絵文字が1つ入力された状態で、下記の3つのどれか1つを時間1で行う事が出来る。
・今書かれている絵文字全てをコピーする
・コピーした絵文字を貼り付ける
・終端から1文字削除する

N個の絵文字を送り付ける際の最小の時間を求めよ。

解いた方法：
Nが小さい(2<= N <= 1000)ので、全部試す。
i文字文コピーした際にペーストして、最小手を更新する際に戻れるだけ戻り、またペーストして…といった感じで配列に最小で移動できる手数を保持しておけばよい。
折り返しが発生する可能性があるので十分に要素数を持っておくといいかも？(例えば1002から折り返したら最短手になる可能性とかありそう。)

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class EmoticonsDiv1 {
    public:
    int smiles;
    int printSmiles(int _smiles) {
        smiles = _smiles;

        int memo[2002];
        REP(i, 2002){ memo[i] = INF; }

        memo[0] = 0;
        REP(i, smiles){
            int paste = i+1;
            int cost = memo[i] + 1;

            for(int j=i+paste; true; j += paste){
                cost++;
                memo[j] = min(memo[j], cost);
                for(int k=j-1; k>=0; k++){
                    if(memo[k] <= memo[k+1]) break;
                    memo[k] = memo[k+1] + 1;
                }
                if(j >= smiles) break;
            }
        }

        return memo[smiles-1];
    }
};

TopCoder SRM 611 Div1 Easy LCMSet [1人競技プログラミング Advent Calendar 2016 11日目]

死ぬ程汚いコードを生み出してしまった…。

この記事は1人競技プログラミング Advent Calendar 2016 11日目の記事です。

問題概要：

TopCoder Statistics - Problem Statement

2以上1,000,000,000以下の整数がN(1<=N<=50)個入った整数の配列A、Bが与えられる。
配列Aの中の数字を任意に選択した際に作ることが出来る最小公倍数の集合と配列Bの中の数字を任意に選択した際に作ることが出来る最小公倍数の集合が一致しているかを判定せよ。

解いた方法：
全ての組み合わせを生成すると物凄いオーダーになり死ぬので別の方法を考える。
Bの配列にある全ての数をAの配列にある数の最小公倍数で作ることができ、Aの配列にある全ての数をBの配列にある数の最小公倍数で作ることが出来れば
お互いに作ることが出来る最小公倍数は一致する。

各数の素因数をmapで持っておき、ゴニョゴニョすればいけます…。(日本語にうまくまとめることが出来なかった。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

class LCMSet {
    public:
    vector<int> A;
    vector<int> B;
    string equal(vector<int> _AA, vector<int> _BB) {
        A = _AA, B = _BB;

        vector<map<int,int>> A_map,B_map;

        REP(i, A.size()){
            int a = A[i];
            map<int, int> map_tmp;
            for(int j=2; j*j<= A[i]; j++){
                while(a % j == 0){
                    a /= j;
                    if(map_tmp.count(j) == 0) map_tmp.insert(MP(j,1));
                    else map_tmp[j] += 1;
                }
            }
            if(a != 1) map_tmp[a] = 1;
            A_map.PB(map_tmp);
        }

        REP(i, B.size()){
            int b = B[i];
            map<int, int> map_tmp;
            for(int j=2; j*j<= B[i]; j++){
                while(b % j == 0){
                    b /= j;
                    if(map_tmp.count(j) == 0) map_tmp.insert(MP(j,1));
                    else map_tmp[j] += 1;
                }
            }
            if(b != 1) map_tmp[b] = 1;
            B_map.PB(map_tmp);
        }

        REP(i, A.size()){
            map<int, int> now;
            REP(j, B.size()){
                bool flag = true;
                for(auto b : B_map[j]){
                    if(A_map[i].count(b.first) == 0 || A_map[i][b.first] < b.second){
                        flag = false;
                        break;
                    }
                }

                if(!flag) continue;

                for(auto b : B_map[j]){
                    if(A_map[i].count(b.first) == 1 && A_map[i][b.first] >= b.second){
                        if(now.count(b.first) == 0) now.insert(MP(b.first, b.second));
                        else now[b.first] = max(now[b.first], b.second);
                    }
                }
            }

            if(now != A_map[i]) return "Not equal";
        }

        REP(i, B.size()){
            map<int, int> now;
            REP(j, A.size()){
                bool flag = true;
                for(auto a : A_map[j]){
                    if(B_map[i].count(a.first) == 0 || B_map[i][a.first] < a.second){
                        flag = false;
                        break;
                    }
                }

                if(!flag) continue;

                for(auto a : A_map[j]){
                    if(B_map[i].count(a.first) == 1 && B_map[i][a.first] >= a.second){
                        if(now.count(a.first) == 0) now.insert(MP(a.first, a.second));
                        else now[a.first] = max(now[a.first], a.second);
                    }
                }
            }

            if(now != B_map[i]) return "Not equal";
        }

        return "Equal";
    }
};

メロン・アップル / ブラック・ローズ [1人おうちカクテル Advent Calendar 2016 11日目]

間違って記事を上書きしてしまった…。修正です。

この記事は 1人おうちカクテル Advent Calendar 11日目の記事です。

名前：トーキョー・ジョー
材料：ウオッカ 3/5、メロンリキュール 2/5
技法：ビルド

TopCoder SRM 610 Div1 Easy TheMatrix [1人競技プログラミング Advent Calendar 2016 10日目]

昨日寝落ちしながら解法を生み出していた。

この記事は1人競技プログラミング Advent Calendar 2016 10日目の記事です。

問題概要：
TopCoder Statistics - Problem Statement
白と黒のマスのグリッドが与えられる。
任意の四角形のグリッドを切り抜くことが出来る。
切り抜いた際に四角形のグリッドの全てのマスが「隣接マスが自身のマスと違う色である」という条件を満たしている必要がある。
上記の条件を満たした上で、最も大きく切り抜けるマスの数の個数を答えよ。

解いた方法：
下から累積和して
memo[i][j] = j列目のi行目のマスからスタートした際に、j列で取れるマスの個数
を保持しておく。

全てのマスからスタートし、列を増やすごとに作る事の出来る四角形の最大サイズをほぼO(1)で計算することが出来るようになる。

#include<bits/stdc++.h>

#define MP make_pair
#define PB push_back
#define ALL(x) (x).begin(),(x).end()
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n) for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};

int memo[101][101];

class TheMatrix {
    public:
    vector<string> board;
    int MaxArea(vector<string> _board) {
        board = _board;
        REP(i, 101) REP(j, 101) memo[i][j] = 0;

        REP(i, board[0].length()){
            memo[board.size()-1][i] = 1;
        }

        for(int i=(int)board.size()-2; i>=0; i--){
            REP(j, board[0].length()){
                if(board[i+1][j] == board[i][j]) memo[i][j] = 1;
                else memo[i][j] = memo[i+1][j] + 1;
            }
        }

        int ans = 0;
        REP(i, board.size()){
            REP(j, board[0].length()){
                int min_cnt = memo[i][j];
                REP2(k, j, board[0].length()){
                    if(k != j && board[i][k-1] == board[i][k]) break;
                    min_cnt = min(min_cnt, memo[i][k]);
                    ans = max(ans, min_cnt * (k-j+1));
                }
            }
        }


        return ans;
    }
};