読者です 読者をやめる 読者になる 読者になる

ドメインを買って hugo のブログを建ててみた

tubo28.me というドメインを買いました。以前から tubo028.net は持っていましたが、妙に長いので変えたいと思っていました。 ccTLDyukicoder.me をリスペクトしています。

わざわざはてなダイアリーを使わない理由は

  • 読むにも書くにも JavaScript 重すぎ
  • URL を貼るときなどに MSWord 的おせっかいが発動
  • 数式が激烈に書きづらい (div さんの記事参照)
  • 文字列を選択したときに出るスターボタンの位置が絶妙に誤爆しやすい
  • 非課金だと自由度がない (これは仕方ない)

といったことです。

で、かなり前から hugo を試してみていますが、かなり良いです。 hugo とは go でできた静的サイトジェネレータです。 tubo28.me/blog に生成したブログ兼競プロライブラリを置いています(後者は要認証)。 記事データや css, html を決められた場所においてコマンドを実行すると、そのままサーバに上げられるディレクトリができます。 ディレクトリ構造や taxonomy というしくみを使って構造的なサイトを楽に作れるのがよいです。 markdown も書けますし、localhost にサーバーを建てて変更を確認しながら更新できます。快適です。 サイト全体を git で管理できるのも良いです。

検索エンジンに拾われにくいとか Jekyll ほどの自由度はないという欠点もありますが、インストールも簡単なので是非試してみてはどうでしょうか。

移転

少し前からブログを移転しています。 → http://d.tubo028.net/

さらに移転しました → http://hugo.tubo028.net/about/

TopCoder SRM #629 Div2

ox- でした。1107 -> 1134? くらい(覚えてない)
Med通らなかったけどシステムテストケースが Constraints を満たしていなく、これを考慮すると通っていた。

http://apps.topcoder.com/forums/?module=Thread&threadID=829554&start=0
リジャッジがかかったようです。oo- 1107->1192 (+85) でした。

Easy 250

問題

W,Bのどちらかで埋められた {n \times n} のグリッドが与えられる。縦方向に連続する同じ文字の数の最大値は?

解法

普通に数えた。転置するとやりやすくなった。

class TaroGrid {
public:
   int getNumber( vector <string> g ) {
       int n=g.size();
       rep(i,n)loop(j,i+1,n) swap(g[i][j],g[j][i]);
       int ans=1;
       rep(i,n){
           ans=max(ans,f(g[i]));
       }
       return ans;
   }
    int f(string s){
        int res=1;
        rep(i,s.size()){
            int j=i;
            while(j<s.size() && s[i]==s[j]) j++;
            res = max<int>(j-i,res);
        }
        return res;
    }
};

Med 500

問題

座標 { position(i) }{ count(i) } 匹の猫がいる。それぞれの猫は1秒毎に次の動作のうちいずれかを個別に行う。

  • 動かない
  • 正の方向に1だけ動く
  • 負の方向に1だけ動く

移動できる座標に上限と下限はない。同じ座標に2匹以上の猫がいないという条件を満たすように時間 {T} 以内に分散できるか?

解法

貪欲法。
猫を座標で昇順ソートした後、0番目の猫から順に時間 {T} で行け、かつ1つ前の猫と同じ座標にならない限界まで負の方向に移動する。最後の {n-1} 番目の猫までこの方法で配置できたらPossibleできなければImpossible

問題文に { count(i) \ge 1 } と書いてあるのに、システムテストケースには {count(i) = 0} であるようなデータが含まれている。 これに対応するように直したら通るのは納得がいかない… -> リジャッジされました。

class CatsOnTheLineDiv2 {
public:
    string getAnswer( vector <int> pos, vector <int> cnt, int T ) {
        int n=pos.size();
        vector<pii> v(n);
        rep(i,n) v[i]=make_pair(pos[i], cnt[i]);
        return solve(v,T) ? "Possible" : "Impossible";
    }

    bool solve(vector<pii> v, int time){
        sort(all(v));
        int n=v.size();
        int last = -inf;
        rep(i,n){
            int p=v[i].first;
            int l=v[i].second;
            int beg = max(last+1,p-time);
            int en = beg+l-1;
            // dump(beg,en);
            if(abs(p-en) <= time){
                last = en;
            }else{
                return false;
            }
        }
        return true;
    }
};

Hard 950

DPかな…?と思って考えてたけど解けませんでした。

Code Formula 2014 予選B

http://code-formula-2014-qualb.contest.atcoder.jp/

ooo- で 115位です。Cでバグってかなり時間をかけてしまった。

A

irb (Rubyの対話環境) でちゃんとテストしてから出したら36秒でした。15秒で出す人の頭と手の動きはどうなっているんだろう。

puts 7-gets.to_i

B

int main(){
    string s;
    while (cin >> s){
        reverse(all(s));
        ll e = 0;
        ll o = 0;
        rep(i, s.size()){
            int d = s[i] - '0';
            if (i & 1)e += d;
            else o += d;
        }
        cout << e << " " << o << endl;
    }
}

C

6文字以下なら全探索。
そうでないなら、まず {A_i = B_i} になっている箇所を取り除く。このときの長さが7以上なら目標は達成できないのは明らかで、6以下なら適当に等しい箇所の文字を付け足して6文字にする。その後に全探索。

アルゴリズム自体はすぐに思いついたが全探索のところで変なバグを埋め込み、1時間近く悩んでしまい上の順位になった。予選通過は恐らく無理。

デバッグ中に {|A| = |B| = 1} になっているケースを見つけたのでclarを投げた。

string a, b;
int n;
bool solve(){
    if (n <= 6){
        set<string> S;
        S.insert(a);
        rep(k, 3){
            set<string> T;
            for (string x : S){
                rep(i, n)loop(j, i + 1, n){
                    string s = x;
                    swap(s[i], s[j]);
                    T.insert(s);
                }
            }
            swap(S, T);
        }
        return S.count(b);
    }
    vi diff, same;
    rep(i, n){
        if (a[i] != b[i]) diff.push_back(i);
        else same.push_back(i);
    }

    string na, nb;
    int d = diff.size();
    if (d >= 7) return false;

    rep(i, d){
        na.push_back(a[diff[i]]);
        nb.push_back(b[diff[i]]);
    }
    rep(i, same.size()){
        if (na.size() >= 6) break;
        na.push_back(a[same[i]]);
        nb.push_back(b[same[i]]);
    }

    set<string> S;
    S.insert(na);
    rep(k, 3){
        set<string> T;
        for (string s : S){
            rep(i, s.size())loop(j, i + 1, s.size()){
                swap(s[i], s[j]);
                T.insert(s);
            }
        }
        swap(S, T);
    }
    return S.count(nb);
}

int main(){
    while (cin >> a >> b){
        n = a.size();
        if (a.size() == 1) throw;
        cout << (solve() ? "YES" : "NO") << endl;
    }
}

Codeforces Round #263 (Div. 2)

http://codeforces.com/contest/462 日本人writer回でした。

結果は ooo-- で 1577 (-53), expert Rank: 551 でした。ここ数ヶ月間安定してしまっています。

A

グリッドにoxが書かれている。上下左右に隣り合うoのマスの数が全てのマスで偶数になっているか判定しなさい。

グリッドは小さいので普通に数えた。

int main(){
    int n;
    while (cin >> n){
        vector<string> g(n);
        rep(i, n){
            cin >> g[i];
        }

        bool res = true;
        rep(y, n)rep(x, n){
            int dx[] = { 1, 0, -1, 0 };
            int dy[] = { 0, 1, 0, -1 };
            int t = 0;
            rep(i, 4){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (0 <= nx && nx < n && 0 <= ny && ny < n){
                    if (g[ny][nx] == 'o') t++;
                }
            }
            if (t & 1) res = false;
        }

        cout << (res ? "YES" : "NO") << endl;
    }
}

B

長さ {n} の文字列 {S} が与えられる.{i} 番目の文字 {s_{i}} に割り振られるスコアは、{S} に含まれる {s_i} の個数とする。文字列から {k} 個の文字をとるとき、それらのスコアの合計を最大化せよ。

読解に時間がかかった。無駄にpairにしたけど、どの文字を選ぶかという情報は不要でその個数さえわかればよい。個数がそのまま得点になるので貪欲に大きいもの {k} 個とる。

typedef pair<char, ll> mci;
ll n, k;
int main(){
    while (cin >> n >> k){
        string s; cin >> s;
        map<char, ll> m;
        rep(i, n){
            m[s[i]]++;
        }
        vector<mci> v;
        for (char i = 'A'; i <= 'Z'; i++){
            v.push_back(make_pair(i, m[i]));
        }
        sort(all(v), [](mci const& a, mci const& b){
            if (a.second != b.second) return a.second > b.second;
            return a.first < b.first;
        });
        ll ans = 0;
        rep(i, v.size()){
            if (k == 0) break;
            ll t = min(v[i].second, k);
            ans += t * t;
            k -= t;
            // cout << k << endl;
        }
        // cout << "lsfkj";
        cout << ans << endl;
    }
}

C

はじめのスコアを0として、入力される整数のグループをTとAで交互に受け渡しする。

  • Tは受け取ったグループに含まれる整数の和をスコアに足し、それをそのままAに渡す。
  • Aは受け取ったグループを2つに分割する。分けた後のグループの要素数が1だったらそれを捨てる。1より大きいならAに渡す。

初めにTに渡される。最適な操作をし続けたとき、全ての整数を捨てるまでに得られるスコアの最大値を求めよ。

最終的にグループ内のすべての数字は、それだけを含む要素1のグループに分割される。それを併合するときにスコアが得られると考え、グループが1つだけになって併合できなくなるまでこれを続ける。和の大きなグループは先に併合して再利用したほうが得なので大きい方からグループを2つ選んで併合するという貪欲法をとる。これはハフマン符号化のアルゴリズムと全く同じなのでpriority_queueを使って全く同じように実装する。

最近たまたま二分ヒープを実装したのもあって(競技プログラミング以外で!)それを使うアルゴリズムがまず思いついた。けど上位の人はソートしてループ回すだけの方法で解いてます。

int型のオーバーフローで大量に落ちていたけど自分は提出直後に気づいて再提出したので大丈夫だった ≡( ε:)

ll n;

ll solve(vi v){
    priority_queue<ll> q;
    rep(i, v.size())q.emplace(v[i]);
    ll ans = 0;
    while (q.size()){
        if (q.size() == 1){
            ans += q.top();
            q.pop();
            break;
        }
        else{
            ll t = 0;
            t += q.top(); q.pop();
            t += q.top(); q.pop();
            ans += t;
            q.push(t);
        }
    }
    return ans;
}

int main(){
    while (cin >> n){
        vi v(n); rep(i, n)cin >> v[i];
        sort(all(v));
        cout << solve(v) << endl;
    }
}

D

木DPを書くのは初めてだったから実装が間に合わなかった…

AOJ 2426 Treasure Hunt

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426

{n} 個の点と {m} 個の長方形が与えられる。各長方形の辺上または内部にある点の数を求めよ。

解法

座標圧縮・累積和の前計算といった工夫をしないとTLEする。

template<typename T>
inline void compless(vector<T> & c){
    sort(all(c));
    c.erase(unique(all(c)),c.end());
}
template<typename T>
inline size_t idx(T i, vector<T> const& c){
    return lower_bound(all(c),i) - c.begin();
}
 
int n,m;
int xs[5000], ys[5000];
int sum[5100][5100]={};
 
int main(){
    scanf("%d%d",&n,&m);
    vector<int> x(n),y(n);
    rep(i,n){
        scanf("%d%d",xs+i,ys+i);
        x[i]=xs[i];
        y[i]=ys[i];
    }
    compless(x);
    compless(y);
    rep(i,n){
        int fx=idx(xs[i],x);
        int fy=idx(ys[i],y);
        sum[fy+1][fx+1]++;
    }
    rep(i,y.size())rep(j,x.size()){
        sum[i+1][j+1]+=sum[i+1][j]+sum[i][j+1]-sum[i][j];
    }
 
    rep(i,m){
        int lx,ly,rx,ry;
        scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
        lx = idx(lx,x);
        rx = idx(rx+1,x);
        ly = idx(ly,y);
        ry = idx(ry+1,y);
        printf("%d\n",sum[ry][rx]-sum[ry][lx]-sum[ly][rx]+sum[ly][lx]);
    }
}

AOJ 2428 Lost Number

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2428

穴あきの数式が与えられる。穴に適当な文字を入れて計算結果を最大化せよ。

解法

構文解析はエラーが起こったらメッセージ付きの例外を投げる実装にするのが一番実装もデバッグも楽だと思う。

文字の入れ方は高々 {7^{5}}通りしかないのでパーサを書いて全探索する。()の間には<operator>がちょうど1個だけ入るので事前にチェックする。

inline bool valid(int x){ return 0<=x && x<1024; }
 
char e[128];
 
inline bool ispm(char c){
    return c=='+' || c=='-';
}
inline bool ispd(char c){
    return c=='*' || c=='/';
}
 
int num(char* &p);
int fac(char* &p);
int term(char* &p);
int expr(char* &p);
 
int num(char* &p){
    int res = 0;
    if(isdigit(*p)){
        ;
    }else{
        throw "num begin";
    }
    while (isdigit(*p)){
        res<<=1;
        res+=*p-'0';
        p++;
    }
 
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "num end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int fac(char* & p){
    int res = 0;
    if(*p=='(' || isdigit(*p)){
        ;
    }else{
        throw "fac begin";
    }
 
    if(*p=='('){
        p++;
        res += expr(p);
        p++;
    }else if(isdigit(*p)){
        res += num(p);
    }
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "fac end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int term(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res = fac(p);
    }else{
        throw "term begin";
    }
    while(1){
        if(*p=='*'){
            p++;
            res *= fac(p);
        }else if(*p=='/'){
            p++;
            res /= fac(p);
        }else if(*p=='\0' || *p==')' || *p=='+' || *p=='-'){
            break;
        }else{
            throw "term end";
        }
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int expr(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res=term(p);
    }else{
        throw "exp begin";
    }
 
    while(1){
        if(*p=='+'){
            p++;
            res += term(p);
        }else if(*p=='-'){
            p++;
            res -= term(p);
        }else if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
            break;
        }else{
            throw "exp end";
        }
        if(!valid(res)) throw "overflow";
    }
 
    return res;
}
 
bool check(char* e){
    stack<int> s;
    for(int i=0;e[i];i++){
        if(e[i]=='(')s.push(i);
        else if(e[i]==')'){
            if(s.size()){
                int j=s.top();
                s.pop();
                int depth=0;
                bool ok=false;
                loop(k,j,i+1){
                    if((ispm(e[k]) || ispd(e[k])) && depth==1) ok=true;
                    else if(e[k]=='(') depth++;
                    else if(e[k]==')') depth--;
                }
                if(!ok) return false;
            }else{
                return false;
            }
        }
    }
    return s.size()==0;
}
 
int solve(){
    int ps[10];
    int c=0;
    for(int i=0;e[i];i++){
        if(e[i]=='.'){
            ps[c++]=i;
        }
    }
    int fine=1;
    rep(i,c)fine*=7;
    int ans=-1;
    rep(mask,fine){
        int k=mask;
        rep(i,c){
            int p=k%7;
            static const char cs[]="1-(*0+)";
            e[ps[i]]=cs[p];
            k/=7;
        }
        if(!check(e)) continue;
        try{
            auto it=e;
            ans=max(ans,expr(it));
            // cout << e << " : " << "ok" << endl;
        }catch(const char* c){
            // cout << e << " : " << c << endl;
        }
    }
    return ans;
}
 
int main(){
    scanf("%s",e);
    cout << solve() << endl;
}