Codeforces 154 div2

今日はめずらしく19:00からで参加しやすかった。
ていうかなんか始まる10分前になんか友人Aがきた。
ずっといた。太鼓の達人してた。それで帰った。なんかごめんね。
ただし、いつもと違ってFile IOだった。

今日の結果は、A,B,Cが解けた。はじめてCまで解けた。うれしい。
レートは、1410 -> 1527になって、青くなった。この前、-87とかしたのが痛い。
http://codeforces.com/profile/tomoki

肝心の問題は、こんな感じだった。

A. Boys and Girls
http://codeforces.com/contest/253/problem/A
場合分けするだけ。なんか'G','B'を交換したりしてる人いて、ちょっと賢いなって思った。

#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <algorithm>

#include <functional>
#include <cctype>

#include <complex>
#include <string>
#include <sstream>

#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
#define sz(a) ((int)a.size())

typedef long long ll;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;

using namespace std;

int main(){
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    int n,m;
    fin >> n >> m;

    int mi = min(n,m);
    if(mi == n){
        rep(i,mi){
            fout << "GB";
        }
        rep(i,m-mi){
            fout << "G";
        }
        fout << endl;
    }else{
        rep(i,mi){
            fout << "BG";
        }
        rep(i,n-mi){
            fout << "B";
        }
        fout << endl;
    }
    return 0;
}

B. Physics Practical
http://codeforces.com/problemset/problem/253/B
なんか単純に前から探索したらだめだけど、upper_boundとか使えばいい。
2分探索だからはやい。

#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <algorithm>

#include <functional>
#include <cctype>

#include <complex>
#include <string>
#include <sstream>

#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
#define sz(a) ((int)a.size())

typedef long long ll;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;

using namespace std;

int main(){
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    int n;
    fin >> n;
    vector<int> C(n);
    rep(i,n) fin >> C[i];
    sort(all(C));

    int mi = 1000000;
    rep(i,n) cerr << C[i] << endl;
    for(int i=0;i<n;i++){
        vector<int>::iterator u = upper_bound(all(C),2*C[i]);
        int x = u - C.begin();
        cerr << i << " " << x << endl;
        if(u == C.end()){
            mi = min(i,mi);
        }else{
            mi = min((n-x)+i,mi);
        }
    }
    fout << mi << endl;
    return 0;
}

C. Text Editor
http://codeforces.com/problemset/problem/253/C
なんかカーソル移動する。
BFSしてみた。とおった。

#include <iostream>
#include <fstream>
#include <iomanip>

#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <numeric>
#include <algorithm>

#include <functional>
#include <cctype>

#include <complex>
#include <string>
#include <sstream>

#define pb push_back
#define all(c) c.begin(),c.end()
#define rall(c) c.rbegin(),c.rend()

#define rep(i,n) for(int i=0;i<(n);i++)
#define tr(container, it) \
    for(typeof(container.begin()) it = container.begin(); it != container.end(); ++it)
#define present(container, element) (container.find(element) != container.end())
#define cpresent(container, element) (find(all(container),element) != container.end())
#define sz(a) ((int)a.size())

typedef long long ll;
const int dx[] = {1,0,-1,0};
const int dy[] = {0,-1,0,1};
const double EPS = 1e-9;

using namespace std;

typedef struct TTAG{
    int x;int y;int k;
} T;

int main(){
    ifstream fin("input.txt");
    ofstream fout("output.txt");

    int n;
    fin >> n;
    vector<int> A(n);
    rep(i,n) fin >> A[i];

    int haba = *max_element(all(A));
    int r1,c1,r2,c2;
    fin >> r1 >> c1 >> r2 >> c2;
    r1 -= 1;
    r2 -= 1;
    c1 -= 1;
    c2 -= 1;


    vector<vector<char> > V(n+1,vector<char>(haba));
    queue<T> Q;
    //Q.push({r1,c1,0});
    Q.push({c1,r1,0});
    while(!Q.empty()){
        T t = Q.front();
        if(V[t.y][t.x]){
            Q.pop();
            continue;
        }
        V[t.y][t.x] = true;

        if(t.y == r2 && t.x == c2){
            fout << t.k << endl;
            return 0;
        }
        if(t.x != 0){
            Q.push({t.x-1,t.y,t.k+1});
        }
        if(t.x != A[t.y]){
            Q.push({t.x+1,t.y,t.k+1});
        }
        if(t.y != n-1){
            Q.push({min(t.x,A[t.y+1]),t.y+1,t.k+1});
        }
        if(t.y != 0){
            Q.push({min(t.x,A[t.y-1]),t.y-1,t.k+1});
        }
        Q.pop();
    }
    return 0;
}