9999-12-31

移行?

tubo28.me というドメインを買ってさくらVPSとひも付けています。今後はそっちの方をよく更新すると思います。

2019-01-28

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019 - AtCoder

1 年ぶりに rated に参加したの書いてみる。

結果は下の通りだった。遅かったので決勝進出はできないけどギリギリ 500 位には入ったので自腹で遊びにいく権利はゲットした。

f:id:tubo28:20190128012620p:plain

なんとレート変動 ±0。

f:id:tubo28:20190128014657j:plain

A Subscribers

A にしては自頭要素多くない？

int main() {
    int n;
    int x, y;
    while (cin >> n >> x >> y) {
        int ma = min(x, y);
        int mi = max(0, x + y - n);
        cout << ma << ' ' << mi << endl;
    }
}

B Touitsu

i 番目の文字ごとに一番多いものに揃える。

int main() {
    int n;
    string a, b, c;
    while (cin >> n >> a >> b >> c) {
        int ans = 0;
        rep(i, n) {
            int cnt[256] = {};
            cnt[a[i]]++;
            cnt[b[i]]++;
            cnt[c[i]]++;
            int ma = *max_element(cnt, cnt + 256);
            ans += 3 - ma;
        }
        cout << ans << endl;
    }
}

C Different Strokes

D より難しかった。先手は

残っている料理の中で A+B が最大
複数ある場合は A が最大

の料理を選ぶのが最適。後手も同様にする。

 
// score, a, b, id
using Tup = tuple<int, int, int, int>;
 
signed main() {
    int n;
    while (cin >> n) {
        priority_queue<Tup> ab[2];
        rep(i, n) {
            int a, b;
            cin >> a >> b;
            ab[0].emplace(a + b, a, b, i);
            ab[1].emplace(a + b, b, a, i);
        }
 
        vector<int> used(n, false);
        int score[2] = {};
        rep(i, n) {
            auto &que = ab[i&1];
            while (true) {
                int id = get<3>(que.top());
                if (used[id]) que.pop(); else break;
            }
 
            int ab, a, b, id;
            tie(ab, a, b, id) = que.top();
            que.pop();
            used[id] = true;
            score[i&1] += a;
            // dump(id);
            // dump(a);
            // dump(b);
        }
 
        cout << score[0] - score[1] << endl;
    }
}

ボドゲとか弱い人なのでこの問題を解くのに 40 分くらいかかった。

D Restore the Tree

この問題は言い換えると、各頂点について自身を終点とする辺が複数ある場合に、どれを元の根付き木の辺として使うか (どの始点が本当の親か) 選べという問題になる。

追加される辺は親から子孫の方向だけなので入力のグラフは DAG になる。DAG はトポソできる。親と繋がっている辺はトポソしたときに一番後ろになるはずなのでそうする。

vector<vector<int>> g, rg;
int E;
 
vector<int> vis, arr, par, ord;

void tsort(int v) {
    vis[v] = true;
    for (auto &c : g[v]) {
        if (!vis[c]) tsort(c);
    }
    arr.push_back(v);
}
 
int main() {
    int n, m;
    while (cin >> n >> m) {
        E = n + m - 1;
        g.assign(n, {});
        rg.assign(n, {});
        rep(i, E) {
            int a, b;
            cin >> a >> b;
            --a; --b;
            g[a].push_back(b);
            rg[b].push_back(a);
        }
 
        vis.assign(n, false);
        par.assign(n, -1);
        arr.clear();
        rep(i, n) if (!vis[i]) tsort(i);
        reverse(all(arr));
 
        ord.resize(n);
        rep(i, n) ord[arr[i]] = i;
        rep(v, n) {
            int par = -1;
            for (auto &src : rg[v]) {
                if (par == -1 || ord[par] < ord[src]) {
                    par = src;
                }
            }
            cout << par + 1 << '\n';
        }
        // puts("aaa");
    }
}

E 以降

元気があったら復習します。

2017-10-03

ICPC アジア地区予選での環境構築

2019/01/08 追記: JetBrains がスポンサーになったおかげで (?) 環境が劇的に改善し、JB 製 IDE や Atom, Sublime が使えるようになりました。 VM が配布されているので試してみて不都合なければこの記事の内容は不要です。

Computing Environment for the Contest | ACM-ICPC 2018 Asia Yokohama Regional

あと数ヶ月で ICPC アジア地区予選つくば大会が開かれます．例年通りならば，アジア地区予選では運営が用意したパソコンを使わなければいけないので，競技開始後に選手は必要に応じて設定ファイルを書き，そのパソコンに入っているエディタでコードを書かなければいけません．Visual Studio とか，濃厚にカスタマイズされた Vim はダメなので注意してください．(Eclipse などのフリーの IDE が使えることはあります．)

そのため，素の Gedit を使うとかでもない限り準備が必要で，各チームで打ち合わせておく必要があります． Twitter 上でそのへんどうしようかなーという話を見かけたので，私が行っていた設定を紹介してみます．2015 Asia Taipei regional, 2016 Asia Tsukuba regional で使ったもので，両方共，当時最新の Ubuntu LTS でした (今年の環境もそのうち公開されるでしょう)．

エディタ (Emacs)

ICPC ではパソコンが 1 台しか使えないので，チームメイトのエディタを揃えたほうが有利です．World Final 2017 の放送を眺めると分かりますが，チームによって様々です．私は Emacs を使っていたので，Emacs の設定方法のみ紹介します．

~/.emacs

Emacs の良い点は，数行の設定を書けば，自動インデントやコンパイルエラーのハイライト，gdb との連携などの最低限の機能と，軽さ，シンプルさが両立できる点です．

ホームディレクトリに .emacs というファイルを作成し，次のように記述してください．もちろんチームの Emacs ユーザーに聞いて追記・削除してください (いないなら使うべきではない)．

(global-set-key "\C-z" 'undo)            ;; C-z で Undo
(global-set-key "\C-s" 'isearch-forward) ;; C-s で検索
(global-set-key "\C-r" 'query-replace)   ;; C-r で置換
(global-set-key "\C-j" 'dabbrev-expand)  ;; C-j で補完
(global-set-key "\C-h" 'keyboard-quit)   ;; C-h (ヘルプ) の誤爆は頻発するので keyboard-quit か delete-backward-char に当てる
(global-linum-mode t)                    ;; 行番号を表示
(setq inhibit-startup-message t)         ;; 起動時のメッセージを無効化
(show-paren-mode t)                      ;; 対応する括弧の表示
(add-hook 'c++-mode-hook 'flymake-mode)  ;; C++ のコードを開いたときに flymake を有効にする

Emacs の設定を書く場所は他にも複数あり，~/.emacs.d/init.el 等がそうです．Emacs を初めて起動した際に ~/.emacs が無ければ ~/.emacs.d/init.el が自動で作成されます．~/.emacs が優先されるのでそのままでもいいのですが，混乱防止のため消してしまっても良いですし，そちらに書いてもいいです．

~/Desktop/Makefile

コンパイルエラーのハイライトは Emacs 組み込みの flymake という拡張機能で実現できます．使えるようにすると，コンパイルエラーを解析して行番号などの情報を取得し，エディタ上に表示してくれます．ICPC の環境では，インターネット上のパッケージが使えないので，Makefile を使った設定が最もシンプルでおすすめです．

コードと同じ場所 (後述の理由で Desktop がおすすめ) に Makefile という名前のファイルを作り，次のように記述します．インデントは必ずタブにしてください．(はてなブログに貼ると勝手にスペースになってしまう…)

check-syntax:
    g++ -Wall -Wextra -fsyntax-only -std=c++11 $(CHK_SOURCES)

g++ に与える引数のうち，-fsyntax-only と $(CHK_SOURCES) は必須です．-Wall, -Wextra は，未使用の変数があるとかの警告を最大限に出すようにする設定です．うるさいと思ったら適当に消すなどしてください．-std=c++11 は，C++ 11 を有効にする設定で 03 で良いなら消してください．

以上の設定をすると，GCC が検出できた変なところに下線が付き，マウスカーソルか，エディタ上のカーソルを持って行くと説明がポップアップで表示されます．Clang の方が賢いので使えるなら g++ を clang++ に変えた方が良いです (本番ではたぶん使えない？)．

f:id:tubo28:20171003200106p:plain

Bash

Bash が使えます．~/.bashrc に次のように書いていました．

bind 'set completion-ignore-case on'        # 大文字小文字を無視して tab 補完
ulimit -s 1048576                           # スタックメモリ 1GB でオーバーフロー防止
alias g="g++ -Wall -Wextra -std=c++11 -g"   # 積極的に警告・C++11・デバッグ情報を埋め込み
alias a="./a.out"
alias l="ls"
alias k="ls"
alias e="emacs -nw"                         # Emacs をターミナル内で起動

キーボード

本番前の話です．公式の発表がないので分かりませんが，いつも使っている物は使えないかもしれないので，英字配列の練習が必要かもしれません．私のときはなんかブヨブヨする英語のキーボードでした (持ち込み可にしてほしいなあ)．

その他

前日の練習セッションでどれだけ WA を出してもいいので，新しい C++ は使えるか，スタックは深いか，実行速度はどのくらいかなどを見ておく．
Ctrl+Super+Left, Ctrl+Super+Right とか Unity の使い方を覚えておく．
チームで少なくとも 1 人は Python や Ruby (irb) の使い方を覚えておく．電卓として使えますし，乱数ケースがサッと作れるので便利です．
下の画像は Codeforces ですが，Firefox でファイルを提出するとき，ボタンにドラッグアンドドロップしても選択したことになります．だから Desktop で作業すると楽です．

f:id:tubo28:20171003193957p:plain

まとめ

以上です．準備もコンテスト時間に含まれるのであまり高度なことはできませんが，チームで相談して，最低限の手順リストのようなものは用意しておいた方が良いと思います．他にこういうのもいいよーというのがあれば教えてください．

選手の皆さんの検討を祈ります．

2014-08-31

TopCoder SRM #629 Div2

SRM DP 貪欲

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かな…？と思って考えてたけど解けませんでした。

2014-08-28

Code Formula 2014 予選B

AtCoder 全探索 Code Formula

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

2014-08-27

Codeforces Round #263 (Div. 2)

Codeforces ハフマン符号化貪欲

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

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

A

グリッドにoかxが書かれている。上下左右に隣り合う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を書くのは初めてだったから実装が間に合わなかった…

2014-08-17

AOJ 2426 Treasure Hunt

累積和座標圧縮 AOJ

問題

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