mayoko’s diary

プロコンとかいろいろ。

何も知らないのに ISUCON 2017 に参加した

チーム「座るだけのコンテストってな~んだ?」で OKeiGo さん, しょラーさんと一緒に ISUCON 2017 に参加しました。

僕がやったのは, チーム名を考えることと, それを実際に実行することだけです。

前日まで

Vagrant で ISUCON の環境を再現できるものがあり, それでホーンとか言ってた
github.com

これ使ってなんか勉強しようとネット資料とか見てたけどみんな難しい言葉使っていてわかりませんと言う感じ

サーバーの概念に多少詳しくなったけど肝心の実装は何もわからない

  • 冷静に考えてお前コード読むことしか能ないんだからもうちょっと app.py とか読んでおけばよかったのにと始まってから思った
  • というかしょラーさんと OKeiGo 君だったら僕いらないだろとチーム組んだ時から思ってた

当日

一番いろいろ勉強できた気がする
他の二人が頑張ってセットアップしてる間にへーとかホーとか言ってた

  • ていうか二人が詳しそうなのでなんか思いついても言いづらいなぁみたいな気持ちはあった
  • ssh でどう接続すれば良いのかもよくわからなかったし, web サービス自体どうやって閲覧するのかもよくわからなかった
    • 理解するのに 30 分くらいかかった

後ほかの二人が slack で話してるのを見てヘーとか言ってた

  • python でやってたんですけど, os.environment.get() ってやると環境変数が取れるらしい
    • それでヘーと思って echo $ISUBATA_DB_HOST とかやってみたけど特に何も起きなくて解せなかった

app.py を読んどけと言われたので読む

  • flask とか言うのが web アプリケーションのフレームワークになってることを初めて知った
  • おそらく ISUCON ではそんなに大事な部分ではなさそうですが, login とか logout ってこうやって実装するんだーみたいのも初めて知った
    • flask.render_template(filename) で filename を渡すとか(GET でよく使う)
    • POST の時には flask.request.form['hoge'] で hoge を受け取るとかしてるっぽいですね
    • flask.session がよくわかってない
      • 複数の人がいるのに flask.session.pop() とかで除外するみたいな感じで良いんだろうか

後まぁ flask でやるときはデコレーションで「ここにアクセスしたときはこういう操作すれば良いよ」というのを書けば良いってのもここで知りました

  • 世の中の人いろいろ考えるなぁっていう

話を聞いていると今回は GET /icons/* を高速化するのが大事っぽかったんですが, しょラーさんの提案していた解法が僕にはよくわからなかった(なんか nginx 使って何かするらしい)

その後僕が見てたのは mysql 周り(見てただけ)

  • まだ見てないメッセージ数を求めるやつは, 各チャンネルごとに合計のメッセージ数を覚えておき, 各ユーザーが各チャンネルのメッセージをいくつ読んだか覚えておけば(メッセージを消すことが出来ないので)求まるよねという話をした
  • GET /fetch のところで, プログラムが sql クエリを何回も呼び出すやつやってて頭悪いな~と思ってたら しょラーさんが解決してた
    • sql でもらった結果を配列として持っておいて, 配列で for 文を回せば OK
      • python 詳しくないので書き方がわからなかった
  • 世の中には slow query というボトルネッククエリを調べられる便利機能があるらしい
    • 使い方イマイチわかってない

その他気になったこ

  • password に salt つけてハッシュ化するってやつ, たまに見るけどそれ意味ある?と思っているのでやる必要性が気になる

感想

世の人々はこんな複雑な web 系プログラミングに詳しくてすごいなーと思いました。

ICPC 国内予選 2017 に参加しました

4 位でめでたい!

開始前

Sleep, 114514, lsplpl, catsatmat の次で 5 位くらい入ればワンチャンあるのでは?とかそれ無理でもドワンゴ賞と NTT 賞が美味しそうとかいう話をする
結構時間余裕を持って会場入りしたので暇
戦略としては僕が基本的にコーダーをやる感じに

本番

問題文は印刷してもらってその間に僕は A と B を解く
A ははい
B はめんどいけどなんとか
A と B 解いてる間に C と D 見てもらってて, C はなんか解けて D は難しいらしいので C は解いてもらって D の相談
「ユーて n*m 小さいし場合分けして行けない?」と聞いて最初えーって言ったけど行けるやんと気づいて C 問題 AC の直後書き始める -> AC
D 解いてる間に E の解法が大体出来ていて, 「書いて」と言われたので書く
バグバグ
バグバグしてる間に F わかったらしいので書いてもらう -> AC(天才か?)
E もなんかバグ取れて AC
予選通過ワンチャンあるんじゃね?という空気になり始める(たしか 4 位くらい)
G もなんか考えられていて, 「右手法っぽくやればいいんじゃない?」という話だったのでじゃあ実装するか〜ということに
バグバグ
実装の思いがこっちに伝わってなかったっぽいのでいろいろ言いながら実装完成させる->AC
G を AC するだいぶ前に catsatmat とかが 7 完してたっぽいので今更かな〜と思ったけど順位表見たら 4 位!
そのまま終わって終了

終了後


みんなお祝いしてくれてとてもうれしい
チームメートのこのツイートなんか心に来る

CODE FESTIVAL 2016 に参加しました

タイトル通りです。思ったことをつらつら書いていきます。

1 日目

家から追い出されたのでちょっと早めに家を出ると案の定早く着きすぎた。


暇だったのでちょっと周りをブラブラしましたが面白いものは電通しかありませんでした。

会場に着いて暇だったので雪の宿を yazaten さんと btk さんにあげたりクソなぞなぞコンテストを作ったりしていました。12/11 に行う予定です。よろしくお願いします。

メインメニューのコンテスト。1600 点でパーカーがもらえるらしいというのと配点からまずは ABCDe を解くことを目標にしました。

  • A 問題: はい。
  • B 問題: 最初 N 点「以上」だと思って超簡単な貪欲じゃんと思ったら WA して「は?」と言ったけど適当に二分探索して通した。
  • C 問題: 「多分連結っていうので良くね?」と思って提出したら AC して良かった。AtCoder の配点はよくわかりませんがいつもの 400 に比べると簡単だった。
  • D 問題: これはちょっと迷った。しばらく考えた後,
    • M で割ったあまりで考える
    • M で割ったあまりについて, 奇数個余っているようなものについて注意する
    • M で割ったあまりが i <-> M-i となるようなものをペアにしてごにょる
  • みたいな方針でできることに気づいて, 適当にやったらサンプルあったので提出したら AC した。これはバグらせるかと思ったのでラッキーだった(ここで詰まって終了した人もいたらしいけど, 辛そう)。
  • E 問題: 適当に dfs 枝刈りしたら部分点はとれた。満点をしばらく考えていたけどわからなかったので 次の問題を見る。
  • H 問題: 次の部分点なのでちょっと見たが難しそうだったのであまり真面目に取り組まなかった。
  • F 問題: 一瞬である程度の方針が立ったので簡単な気もする。最初に思いついた方針は少し間違えてたけどまぁ修正できる範囲で, 普通に AC。これはうれしかった。

後は E の満点, H の部分点を考えててた(特に E ばっかり考えてた)けどわからず終了。去年は面白い問題に取り組む前に終了してた感じだったけど今年はそこそこ楽しめたので良かったです。無事パーカーももらえたしハッピー。

後はごはん食べたりペアコーディング見たりエキシビジョンマッチみたりしました。

  • AC 画像について, ガーリッシュナンバーに変更したのは良くないという意見を受けました。
  • エキシビジョンはちょっと考えたけどわからず…海外勢が 0 完太陽だったのは面白いですね。

最後リレーでよろしくお願いしますするときに英語離せないの辛いなーってなりました。tozangezan さん普通に話せててすごいなぁと思いました。

2 日目

トーナメントは B 問題が簡単そうだったので 400/600 を狙ってたんですがバグって終了。0 完太陽でした。
A 問題の最小全域木作ってあらかじめ i から j への最大コストとか覚えておくののテクニックとかアルゴリズム的正当性がすごい頭良いなぁと思いました。

トーナメントは割と難しい問題だった気がするので 45 分 2 セットでも良かったような気がします。あんまり消化しきれてない感じが。

あと Round2 の A も 1 行でかけると聞いて考えてたんですがこれも面白かったですね。後で chokudai さんに賢い考え方を教えてもらいました。ところでいまだにいろはちゃんと chokudai さんの違いが分かってない。誰がやってるんだ。

その後のトークは kyuuri さんの LT とりんごさんのクイズが面白かったです。snuke さんがクソなぞなぞに言及してたのはなんとなくうれしかったです。

最後にリレーがありました。本選でまぁまぁいい順位だったせいで I 問題を割り当てられました。が, 普通に難しくてわからなかったので海外勢に教えてもらいました。すごい。ここでも英語できないの辛かったですね…

ところで I 問題は書くべきことを記憶するのが非常に面倒なロシアゲーだったのでメモを持っていくのを許可してほしい感じがありました。頭の中で解法を思い起こしながらコード書いてたら「マダー?」みたいなこと言われてすまぬ…となりました。

後から考えると

  • クソなぞなぞ談義したかった
  • ハル研プロコンの話もうちょっとしたかった
  • コンテンツ別のやつもうちょっと楽しみたかった

とかいろいろやればよかったと思うことありますが楽しかったです。運営の方々本当にありがとうございました。

ハル研プロコン2016に参加しました

ハル研プロコンに参加しました。
www.hallab.co.jp

個人的にはとても楽しかったのですが, 上位の人によるとあまり工夫のしどころがなかったようです。

とりあえず自分のやったことを書いていきたいと思います。

貪欲パート
  • 一番近くの小惑星に近づく, 最も小惑星が消える方向にレーザーを打つ, で 76240
  • レーザーで遠くにいる小惑星が消えてくれるほうが嬉しいのでそうする, で 71813

この後「ちょっと待てばレーザーでたくさん消せるならちょっと待つ」というのを入れましたが, これはうまくいきませんでした。
これについて考察すると, 例えば残り 3 個の小惑星があり, 1 つは非常に遠くにあって残りの 2 つはすぐ近くにあるとします。今打つと遠くにある一つのみを消すことになるのですが, ちょっと待ってから打つと近くにある小惑星が 2 つ消せるとしましょう。
そうすると, 元の方法では「遠くを消してからちょっと移動して 2 つ消える」だったのに対し, もう一つの方法では「2 つ同時にレーザー打ってから遠くにある小惑星に近づいてまたレーザーを打つ」となるので, 明らかに損をします。

  • 近づく小惑星に関して, 端っこに近いやつほど近づきやすくする, で 68199
  • レーザーも端っこ消しやすくすれば良くなるのでは, を勘違いして真ん中にあるほど消しやすくしたところ改善, で 67686

これについて考察すると, 今回の自分のアルゴリズムではなにかの小惑星に向かう動きしか考慮していないので, 宇宙船自体はずっと端っこにいたほうが有利っぽいことを考えるとレーザーは真ん中をたくさん消すほうが良さげだったということですかね。

探索パート
  • 行先であり得そうなものを 2 通り拾ってくるようにする, で 62469
    • ここでマグカップを確信しました。
  • レーザーについてもあり得そうなものを 2 通り拾ってくる, で 61632
  • 枝刈りを入れることでたくさん探索して 60117
    • 枝刈りは, (今のターン) + (まだかかりそうなターン数) > (今までの最短ターン) だったら消す感じです。
  • 時間で粘るようにする, で 59761

後は気合の高速化で探索範囲を広げました。ここまではめっちゃ楽しかったんですがこっからはあんまり楽しくなかったです。
最終的には 59136 ターンで finish しました。最後に確認したときは 4 位僅差で 3 位だったと思いますがどうなることやら。

上位陣の話を聞いたところ,

  • 方針はビームサーチ
  • 小惑星の壊れた数でサーチのターンを進めていき, 評価関数は経過ターンのみ
  • 遷移は基本的に 8 方向で, 40 ターン以内にぶつかって破壊できるときは小惑星に向かって近づく

だったそうです。確かにこれだと高速化ゲーで楽しくなさそうですが, ビームサーチは「ターンでゲームを進めると評価関数つくりにくいなぁ」と思ってた自分にとっては「小惑星の壊れた数」でサーチを進めるのは頭の良さを感じました。なるほど。

できれば 3 位に入っててほしいです…

Codeforces Round #365 (Div. 2) C. Chris and Road

問題

codeforces.com

n 頂点の凸多角形が x 軸方向の負の方向に単位時間 v で移動する。この凸多角形の内部に入らないように, y 軸を y = w まで移動したい。
y 軸の移動速度が最大で u の時, 最短で何秒で y = w まで移動できるか。

解法

凸多角形の左側を歩くときと右側を歩くときで場合分けします。右側を歩くのは必ず成功するので, これでちゃんと答えが求められます。

左側を歩く場合, x 軸が最小になる点から y 軸が最大になる点(時計の 9 時方向から 12 時方向ってイメージ)で凸多角形に衝突しなければ良いです。

右側を歩く場合, y 軸が最小になる点から x 軸が最大になる点(時計の 6 時方向から 3 時方向)で凸多角形の内部に入らないようにすれば良いです。

const int MAXN = 100100;
pii P[MAXN];
int N, W, V, U;
typedef double Real;
int prv(int i) {
    return (i+N-1)%N;
}
int nxt(int i) {
    return (i+1)%N;
}

int main() {
    cin >> N >> W >> V >> U;
    for (int i = 0; i < N; i++)
        cin >> P[i].first >> P[i].second;
    int imin = min_element(P, P+N) - P;
    int imax = max_element(P, P+N) - P;
    Real ans = 1e18;
    // 多角形の左側を通る場合
    {
        int i = imin;
        bool ng = false;
        for (int j = 0; j < N; j++) {
            Real t = (Real)P[i].second / U;
            Real x = P[i].first - V*t;
            if (x < 0) {
                ng = true;
                break;
            }
            int ni = prv(i);
            if (P[ni].second <= P[i].second) break;
            i = ni;
        }
        if (!ng) ans = min(ans, (Real)W/U);
    }
    // 多角形の右側を通る場合
    {
        while (1) {
            int ni = prv(imax);
            if (P[ni].second >= P[imax].second) break;
            imax = ni;
        }
        Real tmp = 0;
        int y = 0;
        int i = imax;
        for (int j = 0; j < N; j++) {
            // 普通に歩いてかかる時間
            Real need = (Real)(P[i].second - y) / U;
            if ((Real)P[i].first - V*(tmp+need) <= 0) tmp += need;
            else tmp = (Real)P[i].first / V;
            y = P[i].second;
            int ni = nxt(i);
            if (P[ni].first <= P[i].first) break;
            i = ni;
        }
        tmp += (Real)(W-y)/U;
        ans = min(ans, tmp);
    }
    printf("%.10lf\n", ans);
    return 0;
}

Codeforces Round #365 (Div. 2) D. Mishka and Interesting sum

問題

codeforces.com

数列 A に対して, 以下のクエリに答えよ。

  • 区間 [l, r] に偶数個ある整数の xor を取る
解法

偶数じゃなくて奇数だったら簡単です。というのも, xor は 2 回同じ数をかけられれば自動的に 0 になるので [l, r] の区間の xor を累積和で適当にやれば良いだけだからです。

ですが, これは偶数の場合を聞いているので, 答えるべきものとしては [l, r] の累積xor から, [l, r] に存在する数の xor の和を取ったもの, になります。

累積和は簡単なので, 区間 [l, r] におけるユニークな数の xor 和を考えます。

クエリを R の順番に並べます。で, ある数がすでに表れていた場合には前回現れたところはすべて無効化するような感じにします。具体的には

last[num] = (num が最後に出てくる index) というようにすると, i 番目に num が出てきた場合, A[last[num]] ^= num とやることによって解決します。こういう風にすれば bit なりセグメント木なりで区間 xor の問題に落とせます。

// 0-based Binary Indexed Tree
template<typename T> struct BIT {
    int max;
    vector<T> bit;
    BIT(int max) : max(max) {bit.resize(max+1);}
    // [0, i)
    T sum(int i) {
        T s = 0;
        while (i > 0) {
            (s ^= bit[i]);
            i ^= i&-i;
        }
        return s;
    }
    // 0-basedな座標iに値xを追加する
    void add(int i, T x) {
        ++i;
        while (i <= max) {
            (bit[i] ^= x);
            i += i&-i;
        }
    }
    // [a, b)
    T sum(int a, int b) {
        return sum(b)^sum(a);
    }
};

const int MAXN = 1001000;
int A[MAXN], S[MAXN], L[MAXN], R[MAXN];
int ans[MAXN];
vector<int> G[MAXN];

int main() {
    int N, M;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
        scanf("%d", A+i);
    for (int i = 1; i <= N; i++)
        S[i] = S[i-1]^A[i-1];
    cin >> M;
    for (int i = 0; i < M; i++) {
        scanf("%d %d", L+i, R+i);
        L[i]--;
        ans[i] = S[R[i]]^S[L[i]];
        G[R[i]].push_back(i);
    }
    BIT<int> bit(MAXN);
    map<int, int> last;
    for (int i = 0; i < N; i++) {
        bit.add(i, A[i]);
        if (last.find(A[i]) != last.end()) {
            bit.add(last[A[i]], A[i]);
        }
        for (int j : G[i+1]) {
            ans[j] ^= bit.sum(L[j], i+1);
        }
        last[A[i]] = i;
    }
    for (int i = 0; i < M; i++)
        printf("%d\n", ans[i]);
    return 0;
}

Codeforces Round #372 (Div. 1) B. Complete The Graph

いやなんか時間とってゆっくり競プロやりたいんですけど…

問題

codeforces.com

コスト付きの無向グラフが与えられる。いくつかの辺のコストは好きに選べるので, s から t への最短経路の大きさを L にしたい。このようなことが可能であれば, そのうちの 1 つを答えよ。

解法

まず自明に解がない場合を省きます。というのは, いじれるすべての辺のコストを INF にしても最短経路が L 未満の場合と, いじれるすべての辺のコストを 1 にしても最短経路が L より大きい場合です。

逆に, これ以外の場合は, 解が存在することが示せます。これは

  • いじれるすべての辺のコストを 1 にすると最短経路は L 未満, 全て INF にすると L より大きい
  • いじれる辺のいずれかのコストを 1 増やすと最短経路は 1 増えるかそのまま

から言えます。

で, どう具体的にアルゴリズムに落とすかというと,

  • いじれる辺のすべてのコストを 1 にセット
  • 以下を繰り返す
    • dijkstra して t までの距離を求める。L なら終了
    • そうでない場合, s から t までの最短経路にいじれる辺があるはず。その辺のコストを L-d[t]+1 にする。

というようにやれば, いじる辺は M 本しかないので O(M^2 log N) になります(これでギリギリ通った)。さらに, 最初にすべてのコストを 1 にしたときの最短経路上の辺のみを使うようにすると O(NMlog N) になって高速になります。

struct edge {
    int v;
    ll w;
    int id;
    edge() {}
    edge(int v, ll w, int id) : v(v), w(w), id(id) {};
};

vector<edge> G[1010];

vector<ll> dijkstra(int n, int s, int t) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        if (u == t) return d;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

void no() {
    cout << "NO" << endl;
    exit(0);
}

const int MAXM = 10101;
int U[MAXM], V[MAXM], W[MAXM];
bool use[MAXM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M, L, s, t;
    cin >> N >> M >> L >> s >> t;
    const ll INF = 1e9;
    for (int i = 0; i < M; i++)
        cin >> U[i] >> V[i] >> W[i];
    for (int i = 0; i < M; i++) if (W[i]) {
        G[U[i]].emplace_back(V[i], W[i], i);
        G[V[i]].emplace_back(U[i], W[i], i);
    }
    auto d = dijkstra(N, s, t);
    if (d[t] < L) no();
    if (d[t] == L) {
        cout << "YES" << endl;
        for (int i = 0; i < M; i++) {
            ll w = (W[i]==0) ? INF : W[i];
            cout << U[i] << " " << V[i] << " " << w << endl;
        }
        return 0;
    }
    for (int i = 0; i < M; i++) if (!W[i]) {
        G[U[i]].emplace_back(V[i], 1, i);
        G[V[i]].emplace_back(U[i], 1, i);
    }
    d = dijkstra(N, s, t);
    if (d[t] > L) no();
    {
        int now = t;
        while (now != s) {
            for (edge e : G[now]) {
                if (d[e.v] + e.w == d[now]) {
                    use[e.id] = true;
                    now = e.v;
                    break;
                }
            }
        }
    }
    while (1) {
        for (int i = 0; i < N; i++)
            G[i].clear();
        for (int i = 0; i < M; i++) {
            ll w = INF;
            if (W[i] == 0 && use[i]) w = 1;
            if (W[i]) w = W[i];
            G[U[i]].emplace_back(V[i], w, i);
            G[V[i]].emplace_back(U[i], w, i);
        }
        auto d = dijkstra(N, s, t);
        if (d[t] == L) break;
        int now = t;
        while (now != s) {
            int id = -1;
            for (edge e : G[now]) {
                if (d[e.v]+e.w == d[now]) {
                    id = e.id;
                    now = e.v;
                    break;
                }
            }
            if (W[id] == 0) {
                W[id] = L-d[t]+1;
                break;
            }
        }
    }
    cout << "YES" << endl;
    for (int i = 0; i < M; i++) {
        ll w = INF;
        if (W[i] == 0 && use[i]) w = 1;
        if (W[i]) w = W[i];
        cout << U[i] << " " << V[i] << " " << w << endl;
    }
    return 0;
}