hogecoder

つたじろう(Tsuta_J) 競技プログラミングの記録

Google Code Jam Round 1B 2017 C: Pony Express

想定解法と違う方法で解いたので一応メモ。

問題概要

街が  N  (2 \le N \le 100) つあり、街  i j を結ぶ道路の長さは  D_{ij} (km) (-1 \le D_{ij} \le 10^{9}, ただし  -1 の時は道路がないことを表す) である。

それぞれの街には馬がおり、街  i にいる馬は時速  s_{i} (km/h)  (1 \le s_{i} \le 10^{3}) で移動することができ、最大で  e_{i} (km)  (1 \le e_{i} \le 10^{9}) 移動できる。街と街の移動には馬を利用する (必要ならば途中の街で馬を乗り継ぐこともできる)。このとき、以下のクエリを  Q (1 \le Q \le 100) 処理せよ。

  •  U から  V に向けて、上記の制約を満たした乗り継ぎをしながら馬に乗って行くことを考えたとき、かかる時間の最小値を求めよ。

解説

拡張ダイクストラで求めることができます。

rec[i][j][k] := 街 i を出発時点で、今乗っている馬 j が距離 k を走った時にかかる累計時間の最小値 となるような配列を作ります。この配列を真面目に取ろうとしても  10^{2} \times 10^{2} \times 10^{9} のサイズの配列を取らなければならないので無理ですが、実際はそのほとんどが使われることが無いため、使うところだけ利用できるように map を利用して作ることにします。

 x から  y に行く際には、馬の走れる距離が十分にあると仮定すると以下の  2 つの遷移が考えられます。

  •  y に着いた後も、今乗っている馬に乗り続ける
  •  y に着いたら、街  y にいる馬に乗り換える

別の馬に乗り換えた場合、走行距離の情報がリセットされることに注意して遷移すれば良いです。制約を満たさない動き (たとえば、馬の走行距離の限界を超えるなど) をしないようにすることも重要です。

ソースコード

struct Elem {
    int city, horse, dist;
    double cost;
    Elem(int a, int b, int c, double d) : city(a), horse(b), dist(c), cost(d) {}
};

bool operator<(const Elem &a, const Elem &b) {
    return a.cost > b.cost;
}

int e[110], s[110];
int mat[110][110];
signed main() {
    int t; cin >> t;
    repq(cs,1,t) {
        int N, Q; cin >> N >> Q;
        rep(i,0,N) cin >> e[i] >> s[i];
        rep(i,0,N) rep(j,0,N) cin >> mat[i][j];
        printf("Case #%lld:", cs);
        rep(i,0,Q) {
            // city, horse, dist
            map<int, map<int, map<int, double> > > rec;
            int u, v; cin >> u >> v;
            double ans = DBL_MAX;
            u--; v--;
            priority_queue<Elem> q;
            q.push(Elem(u, u, 0, 0.0));
            while(!q.empty()) {
                Elem pick = q.top(); q.pop();
                int from = pick.city, d = pick.dist, usg = pick.horse;
                if(from == v) {
                    ans = min(ans, pick.cost);
                    break;
                }
                rep(to,0,N) {
                    if(mat[from][to] == -1) continue;
                    if(d + mat[from][to] > e[usg]) continue;
                    int nd = d + mat[from][to];
                    double c = (double)mat[from][to] / s[usg];
                    if(!rec[to][usg].count(nd) || rec[to][usg][nd] > rec[from][usg][d] + c) {
                        rec[to][usg][nd] = rec[from][usg][d] + c;
                        q.push(Elem(to, usg, nd, rec[to][usg][nd]));
                    }
                    if(!rec[to][to].count(0) || rec[to][to][0] > rec[from][usg][d] + c) {
                        rec[to][to][0] = rec[from][usg][d] + c;
                        q.push(Elem(to, to, 0.0, rec[to][to][0]));
                    }
                }
            }
            printf(" %.12lf", ans);
        }
        cout << endl;
    }
    return 0;
}

実はワーシャルフロイドを 2 回やる想定解法をまだ読んでいない・・・ (読もう)

TopCoder SRM 712 Div1 Easy: LR

オーバーフローで死ぬつらい問題。

問題概要

原文 → TopCoder Statistics - Problem Statement

環状になっているサイズ  n の数列  s, t がある (0-indexed)。 i 番目の要素に対して左隣は要素  i-1 であり、右隣は要素  i+1 である。 (ただし、 (n-1) 番目の要素の右隣は要素  0 である。)

数列に対して、以下の 2 種類の操作が可能である。

  • L: すべての要素に対して、その左隣の要素の値だけ加算する。
  • R: すべての要素に対して、その右隣の要素の値だけ加算する。

 s に対してこの 2 種類の操作を合計 100 回まで行って、数列  s を数列  t にすることができれば、その操作手順を出力せよ。できないならば、No solution を出力せよ。

解説

操作を見ればわかるように、各要素に対して加算の操作しかできないため s[i] > t[i] となるような要素が一つでもあればその時点で不可能です。また、最初から  s t が一致していれば操作する必要がありません。このチェックは最初にすべきでしょう。

今回の場合、総和を比較することによって操作回数を知ることができます。数列  s の総和を  S として、簡単に説明します。

どちらの操作においても、操作後には現時点での数列の総和ぶん増えます。これは各要素で隣にあるものを足しているので、各要素が 1 度ずつ加算されているということからわかりますね。ですので、操作をするごとに数列の総和は  S \rightarrow 2S \rightarrow 4S \rightarrow 8S \dots のように増えていくことになります。( t の総和  -  s の総和) に対してこの性質を利用して計算していけば、操作回数が特定できます。

また、L と R の並び順は関係ない こともわかります。これは L -> R と R -> L の結果が等しいことを利用すれば示せます。したがって、LL…L RR…R のような操作手順に帰着できるため、L と R の個数さえ分かれば良いことになります。

答えを導く方法の一つとして DP があります。 dp[i][j][k] := R を i 回、L を j 回行った時の k 番目の要素の値 となるような配列を作ります。この遷移は R を行うか L を行うかしかないので、その 2 つを書けば良いです。

ソースコード

ll dp[110][110][60];
class LR {
    public:
    string construct(vector<long long> s, vector<long long> t) {
        int n = (int)s.size();
        rep(i,0,n) if(s[i] > t[i]) return "No solution";
        if(s == t) return "";

        ll ssum = accumulate(s.begin(), s.end(), (ll)0);
        ll tsum = accumulate(t.begin(), t.end(), (ll)0);
        if(ssum == 0 || (tsum - ssum) % ssum) return "No solution";
        ll diff = (tsum - ssum) / ssum;
        ll turn = 1, d = 1;
        while(1) {
            if(diff - d < 0) return "No solution";
            if(diff - d == 0) break;
            diff -= d;
            d *= 2; turn++;
        }

        memset(dp, 0, sizeof(dp));
        rep(i,0,n) dp[0][0][i] = s[i];
        repq(x,1,turn) repq(i,0,x) {
            int j = x - i;
            bool ok = true;
            rep(k,0,n) {
                ll v = -1, w = -1;
                if(j != 0) v = dp[i][j-1][k] + dp[i][j-1][(k-1+n)%n];
                if(i != 0) w = dp[i-1][j][k] + dp[i-1][j][(k+1)  %n];
                dp[i][j][k] = max(v, w);
                if(dp[i][j][k] != t[k]) ok = false;
            }
            if(ok) return string(i, 'R') + string(j, 'L');
        }
        
        return "No solution";
    }
};

これ通せなかったのつらいなあ (本番は回数の決め打ちをしていなかったのでほげ)

遅延評価セグメント木をソラで書きたいあなたに

この記事は前記事: 「セグメント木をソラで書きたいあなたに」の続編です。セグ木をソラで実装するのはまだ厳しい・・・という方はまずはこちらの記事を読んでみてください。

tsutaj.hatenablog.com

この記事は「セグメント木はソラで書けるけど、遅延評価セグ木は書けない・・・」という人を対象にしています。

遅延評価って何?

まず遅延評価について軽く説明しておきます。

遅延評価というのは、値の伝播を遅らせるテクニックです。これは区間に対して更新を行うときに必要になる時が多いです。例えば、値の更新を普通のセグメント木でやろうとしたとき、範囲の長さを  L とするとこの範囲の長さだけクエリを呼ばなければならないため  O(L \log N) かかってしまいますが、遅延評価をすることでこれを  O(\log N) で実現できます。

どうしたらうまくいくのか、簡単に解説します。

配列 a = {1, 3, 2, 6, 5, 4, 7, 9} を普通のセグメント木(区間和) で表すと、以下のようになります。

f:id:tsutaj:20170330223205p:plain

区間和に対応したセグメント木なので、親は子の 2 値の合計を持っている、といった作りになりますね。

このセグメント木に対して、 \left[1, 5\right] 内の要素それぞれに 3 加算することを考えます。すると、通常ではこんなにも多くのノードを更新しなければなりません。

f:id:tsutaj:20170330223607p:plain

これでは効率が悪いですね。そこで、遅延評価用の配列を別に用意し、1 つのノードにつき 2 つの値を持つようにします。説明のため、普通のセグメント木にもあるような、値を覚える配列を「値配列」と、遅延評価用の配列を「遅延配列」と呼ぶことにします(造語)。遅延配列では何を持つのかというと、 自ノードの区間に一様に加えられた値 を持つことになります。

遅延配列をもつセグメント木は、このようなイメージになります。

f:id:tsutaj:20170330223212p:plain

例えば  \left[1, 5\right] に加算クエリが与えられた時、この区間 \left[1, 4\right]  \left[5, 5\right] にわけて考えます。この 2 つの区間に対応するノードについて、遅延配列を更新 します。(なぜなら、この 2 つの区間について一様に加算されているからです。)

f:id:tsutaj:20170330223214p:plain

遅延配列に値が入っているノードについては、いつか遅延配列の情報を値配列の方に伝播させなければいけません。これはどのタイミングで行えば良いかというと、「クエリでそのノードにアクセスしたとき」に更新すれば良いです。

f:id:tsutaj:20170330223217p:plain

遅延配列に値が入っているとき、値配列に入っている値は本来の値ではありません。遅延配列の値を加味してあげることで、初めて本来の値になります。ですので、そこにアクセスした時はまず「遅延配列の中身を反映させてから」処理を行う必要があるのです。

まとめると、

  • 遅延配列は、区間に一様に与えられた値を記憶している
  • 遅延配列に中身が入っているノードにアクセスした時、自分と自分の子に対して値の伝播が起こる
  • 親ノードは、値配列が確定した状態の子ノードを参照することで更新される

このような実装をすることで、必要なときだけ値の伝播が起こるため計算量がぐっと減ります。これで、遅延評価付きのセグメント木も書けるようになります!

実際に書いてみよう

それでは「区間加算・区間和クエリ」を扱えるような遅延評価付きのセグメント木を書いてみましょう。

初期化

初期化については、普通のセグメント木とほぼ同じです

というのも、最初に用意するときは、遅延配列に何も入っているはずがないですよね。実装は普通のセグメント木に遅延配列の宣言が増えただけです。

実際に書くとこのようになります。

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1);
        lazy.resize(2*n-1, 0);

        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = node[i*2+1] + node[i*2+2];
    }
};

遅延評価

ノードに対して評価を行う関数を作りましょう。そのためには

  • 自分のノードは何番目なのか?
  • 自分のノードが指す範囲はどうなっているのか?

を知る必要があるため、 3 つの引数を取ります。

遅延配列に中身が入っている場合、評価を行う必要があります。この関数で何をすべきなのかというと、

  • 自ノードの値配列に値を伝播させる
  • 子ノードの遅延配列に値を伝播させる
  • 自分のノードの遅延配列を空にする

これができればよいです。最下段のノードの処理に気をつけながら書くと、次のようになります。

// k 番目のノードについて遅延評価を行う
void eval(int k, int l, int r) {

    // 遅延配列が空でない場合、自ノード及び子ノードへの
    // 値の伝播が起こる
    if(lazy[k] != 0) {
        node[k] += lazy[k];

        // 最下段かどうかのチェックをしよう
        // 子ノードは親ノードの 1/2 の範囲であるため、
        // 伝播させるときは半分にする
        if(r - l > 1) {
            lazy[2*k+1] += lazy[k] / 2;
            lazy[2*k+2] += lazy[k] / 2;
        }

        // 伝播が終わったので、自ノードの遅延配列を空にする
        lazy[k] = 0;
    }
}

区間加算

区間に対しての更新なので、前記事でいうところの 最上段から下がっていく イメージで見ていきます。

基本的には前回の値の取得クエリとやることは同じです。しかし、遅延評価の関数を適切に呼び出す必要があります。

要求区間が対象区間を完全に被覆している場合、区間に対して一様に値が与えられていると言えます。ですので遅延配列に値を入れた後、評価関数を呼び出します。

そうでない場合、子ノードの値配列をしっかり更新してから、子ノードの値をもらって更新することをします。これは再帰関数にすることで簡潔に書くことができます。

実際に書くとこのようになります。

void add(int a, int b, ll x, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;

    // k 番目のノードに対して遅延評価を行う
    eval(k, l, r);

    // 範囲外なら何もしない
    if(b <= l || r <= a) return;
    
    // 完全に被覆しているならば、遅延配列に値を入れた後に評価
    if(a <= l && r <= b) {
        lazy[k] += (r - l) * x;
        eval(k, l, r);
    }

    // そうでないならば、子ノードの値を再帰的に計算して、
    // 計算済みの値をもらってくる
    else {
        add(a, b, x, 2*k+1, l, (l+r)/2);
        add(a, b, x, 2*k+2, (l+r)/2, r);
        node[k] = node[2*k+1] + node[2*k+2];
    }
}

区間和の取得

これも前回の区間和クエリと書き方はほぼ同じです。違いはやはり遅延評価を呼ぶかどうかで、今回の場合は関数の最初に遅延評価を入れるだけでよいです。

実際に書くとこのような感じになります。

ll getsum(int a, int b, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;

    // 関数が呼び出されたらまず評価!
    eval(k, l, r);

    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return node[k];
    ll vl = getsum(a, b, 2*k+1, l, (l+r)/2);
    ll vr = getsum(a, b, 2*k+2, (l+r)/2, r);
    return vl + vr;
}

コード例

遅延評価セグメント木を習得することで様々なクエリを処理できるようになります。今回は AOJ の DSL で登場するクエリ処理のコード例を載せておきます。

※「区間更新」を扱うときは、遅延配列のフラグが立っているかどうかの bool 配列を別に用意しなければならないため、注意が必要です。

区間最大クエリにしたりなどは比較的簡単にできます。また、工夫すれば区間最小値の個数を答えるクエリなども作れますので、ぜひやってみてください。

楽しいセグ木ライフをお送りください。それではー。

セグメント木をソラで書きたいあなたに

セグ木にいろいろ生やす問題がてんで解けない私なので、セグ木に慣れようと思い立ちました。そのためにはまずセグ木をもっと知らねばならないと思ったので、ソラで書けないか色々やっていました。

やってくうちにコツを掴んでソラで書けるようになってきたので、忘れないためにも記事を書くことにしました。ということで、何も見ずにセグ木を書くために押さえておきたいポイントを紹介していきます。

注意

この記事は、「セグ木がどんな形をしているかはわかるけど、実装はできない・・・」という方向けで、遅延評価が不要な、区間最小の基本的なセグメント木のみ扱っています。

そもそもセグ木って何という人は他記事を参考にしてください。
おすすめは iwiwi さんのスライド → プログラミングコンテストのためのデータ構造

また、すでにセグ木が書けるプロの方が見ても面白くないかもしれません。

記事では区間最小についてのみ扱っていますが、区間和もほぼ同じコードで実現できます (コード例は後述)。

まずは形を見よう

ノードの数

セグメント木は皆さんご存知のとおり、図で書くとこんな形をしています。

f:id:tsutaj:20170329204251p:plain

元のデータ数以上になる最小の 2 冪の数を  N とします。すると、ノードは全部で  2N - 1あります。なぜこうなるかは、各段にあるノードの数を 2 進で書いて足していくと簡単にわかります。

すなわち、

  • 最下段にはノードが  N 個ある
  • それより上の段のノードは全部で  N-1 個ある

ということになります。この性質は後に大事になるので、しっかり把握しておきましょう。

ノードの関係

セグメント木上で操作をするには、ノードの関係を明らかにする必要があります。ここでは木と同様に、自分のノードの直下にあるノードを「子」、自分のノードの真上にあるノードを「親」と呼ぶことにします。

木に例えるとこれは完全二分木になります。つまり、葉でない限り自分の子は必ず  2 個あるということです。

f:id:tsutaj:20170329204255p:plain

自分のノードの番号を  k をおくと、親や子にアクセスするには以下のようにします。

  • 親にアクセスするには、  \lfloor \frac{k-1}{2} \rfloor 番目にアクセスする
  • 子にアクセスするには、  2k+1 番目・  2k+2 番目にアクセスする

これを各所で使うことになります。

更新・取得クエリ

一般的なセグメント木では、値を更新するクエリと、値を取得するクエリの 2 種類を行うことになります。かなりざっくりとしていますが、各クエリに関してはこのようなイメージを持つと良いです。

  • 値の更新クエリは、最下段から上がっていくようにする
  • 値の取得クエリは、最上段から下がっていくようにする

雑ですが、このようなイメージを持って実装を重ねることで詰まることなく書けるようになると思います。

実際に書いてみよう

初期化

元となる配列があって、それをセグメント木で表してみることをやってみましょう。

まずは、セグメント木のサイズ (ノード数)を決定します。そのためには最下段のサイズを求める必要がありますが、これは先述のとおり、元のサイズ以上になる最小の 2 冪 です。この値を  N としたとき、セグメント木のサイズは  2N-1 です。

次に実際に値を入れていくのですが、最下段から値を入れていき、それ以降は下の段から順番に自分の子を参照することで値を入れていきます。上のノードの値を決めるには下のノードを参照しなければならないことを考えると、最下段から入れるのは自然な流れですね。

最下段のノードのインデックスはどうなるのか?と思うかもしれませんが、これには最下段より上の段のノードは全部で  N-1 個ある ことを利用します。前に  N-1 個の要素があるので、インデックスは元のインデックスに  N-1 を足せばよいですね。

これらをまとめると、次のような実装になります。

struct SegmentTree {
private:
    int n;
    vector<int> node;

public:
    // 元配列 v をセグメント木で表現する
    SegmentTree(vector<int> v) {
        // 最下段のノード数は元配列のサイズ以上になる最小の 2 冪 -> これを n とおく
        // セグメント木全体で必要なノード数は 2n-1 個である
        int sz = v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, INF);

        // 最下段に値を入れたあとに、下の段から順番に値を入れる
        // 値を入れるには、自分の子の 2 値を参照すれば良い
        for(int i=0; i<sz; i++) node[i+n-1] = v[i];
        for(int i=n-2; i>=0; i--) node[i] = min(node[2*i+1], node[2*i+2]);
    }
};

値の更新

 x 番目の要素を  val に更新する」ことを考えます。

これを行うには、 x 番目の要素が含まれる区間全てを更新する必要があります。上のノードを更新するには下のノードを見なければならないため、下のノードから更新していかなければいけないことがわかります。

最下段から上がっていく イメージで書いていきます。つまり、まずは最下段を更新し、あとはその親を更新することを繰り返せばよいです。

実際に書くとこんな感じになります。

void update(int x, int val) {
    // 最下段のノードにアクセスする
    x += (n - 1);

    // 最下段のノードを更新したら、あとは親に上って更新していく
    node[x] = val;
    while(x > 0) {
        x = (x - 1) / 2;
        node[x] = min(node[2*x+1], node[2*x+2]);
    }
}

値の取得

区間  [a, b) にある要素の最小値を答える」ことを考えます。

説明のため、クエリで与えられた区間 (実際に計算したい区間) を「要求区間」、各ノードがカバーしている区間を「対象区間」と定義します (造語)。

これを扱うには、以下の 3 つの情報が必要になります。

  • 要求区間はどのような区間か?
  • いま自分がいるノードは何番目か?
  • 自分がいるノードはどのような区間か? (対象区間はどのようになっているか?)

要求区間と対象区間の関係によって場合分けをします。

要求区間と対象区間が交わらない場合

この場合は、これ以上操作をすすめても意味がありませんので、答えに影響しない値を適当に返しておきます。

要求区間が対象区間を完全に被覆している場合

この場合、対象区間は要求区間の計算に必要です。そのため、現状の答えと比較して、更新が必要ならば更新をしていきます。

要求区間が対象区間の一部を被覆している場合

この場合、対象区間の子にあたる区間に移動して、完全に被覆するまで操作を行わなければなりません。

子に移動するので、「現在見ているノード」と「対象区間の情報」が変わります。子のノードのインデックスの取得は先述のとおりで、対象区間に関しては、子のノードが現在見ているノードを半分に分割したものであることを利用すると得られます。

最上段から下がっていくイメージでこれをまとめると、このようなコードになります。(ここが一番難しいと思いますので、わからなければ Twitter などで私に質問してください)

// 要求区間 [a, b) 中の要素の最小値を答える
// k := 自分がいるノードのインデックス
// 対象区間は [l, r) にあたる

int getmin(int a, int b, int k=0, int l=0, int r=-1) {
    // 最初に呼び出されたときの対象区間は [0, n)
    if(r < 0) r = n;

    // 要求区間と対象区間が交わらない -> 適当に返す
    if(r <= a || b <= l) return INF;

    // 要求区間が対象区間を完全に被覆 -> 対象区間を答えの計算に使う
    if(a <= l && r <= b) return node[k];

    // 要求区間が対象区間の一部を被覆 -> 子について探索を行う
    // 左側の子を vl ・ 右側の子を vr としている
    // 新しい対象区間は、現在の対象区間を半分に割ったもの
    int vl = getmin(a, b, 2*k+1, l, (l+r)/2);
    int vr = getmin(a, b, 2*k+2, (l+r)/2, r);
    return min(vl, vr);
}

コード例

AOJ にコードを上げていますので、参考までに。

以上です。遅延評価付きのセグ木についても後日記事でまとめます (たぶん)。

RUPC2017 Day3 北大セットのまとめ

この記事は立命合宿の 3 日目に行われた北大セットのまとめ的記事です。勝手にまとめてしまいました。

※ 随時更新します

問題

実際にコンテストで使われたバージョン

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

正式掲載

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

解説

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

テスターやった人並みの一言

解法詳細はスライドを見てください。

  • A は (奇数個ある種類数) / 2。誤読しやすいのは正直申し訳ないし誤読する人が出るだろうなあという予想はしていたけど、問題をちゃんと読むという注意力を問うた部分もある (たとえ誤読していてもサンプル 3 で気づくと思ったんですけどね・・・)
  • B は 「x 点上げるときに 8 位以上になれるか?」で二分探索できる (全探索でも可)。同率の扱いや、得点を上げた時の順位変動に注意。
  • C はパスグラフとしてみるとよくて、端を特定したあとは端と任意の頂点について質問攻め。順列のサイズが 1 のときに注意。
  • D はパラメータが増えたダイクストラで、距離をキーにして priority_queue を使えばよい。N を通過したか否かのフラグを持つと楽に書ける。速度をキーにしてもそこそこうまくいくけど 1 ケースだけ落ちます (後述)
  • E は区間を set に突っ込むときの set のサイズがそのまま答えになる (更新は頑張らなければいけない)
  • F は根つき木の同型性判定を応用して、木の中心を根として同型性判定を行う
  • G は パターン順列の run の数に応じて解法を変えていく。run の数 が 4 以上なら確実に No
    • run の数 = 1 なら LIS
    • run の数 = 2 なら 山 → 谷 のパターンに合うように点を貪欲にとる
    • run の数 = 3 なら 山 → 谷 → 山 のパターンに合うように貪欲に

コード例 (tsutajiro 解)

A 問題 | B 問題 | C 問題 | D 問題 | E 問題 | F 問題 | G 問題

ちょっとした裏話

  • 作問班唯一の学部生・・・ (若人がいない)
  • 情報系学生の底辺なので作問するまで Git の使い方が分からなかった (爆笑)
  • B は最初二分探索が想定解であったため、チーム数が  10^{5} まで、得点上限が  10^{9} まで、といった感じだったが、 B にしては難しすぎるため全探索可能な範囲に落ちた
  • D で始めの自分の解では距離比較でなく速度比較でダイクストラをやっていて、それで一旦全ケース通ってた
    • → のちに Darsein さんがチャレンジケースを生成して見事に落とされる
    • → 理由は最悪計算量がベルマンフォードと同じになり間に合わないため (しかし通常のベルマンフォードよりは速い模様)
    • → tsukasa_diary さんが SPFA を実装したところ爆速で通る (が、最悪ケースを作るのが難しいためこれは許容する流れに)
  • 先輩方はみんなプロ (それはそう) (精進します)

以上です。

立命館大学プログラミング合宿2017 参加記

立命館大学プログラミング合宿2017 に参加してきました。競技プログラミングの合宿に参加したのは初めてです。 帰りの電車ヒマなので参加記をつらつらと書いていこうと思います。

-1 日目 (作問班参加・準備編)

北大では立命合宿で作問を担当しているので、作問班をサークル内で作らなければなりません。大変そうだけど競プロできる先輩たちといろいろ議論しながら作っていったらためになるだろうなあと思って作問班に参加することに。

立命合宿の日程が北大の卒業式と被ってしまい、先輩方が合宿に出られなくなって当日現地に行くのが私だけになってしまったので、必然的に解説を全部やらないといけない感じになりました。これは全部解いてからいかないとまともに解説できなくてヤバいのでは!?と思ったので全問題のテスターをやることにしました (しかし、F の TLE に悩まされて結局 F 以外のテスターになりました)

作問に必要なツールの使い方は今回で一通り勉強できましたし、何に注意すべきかも分かったので勉強になりました。次に作問する機会があったら活かしたいですね。

0 日目 (移動編)

北の果てから移動するので前日から移動。宿は京都でとってました。烏丸おしゃれすぎてマジヤバい (語彙)

1 日目 (立命 & 阪大セット)

いよいよ合宿スタート!

kenkoooo さん、 kawabys さんとチーム ktky で出ました。

  • 最初 A 問題の担当だったのですが難しく考えすぎてハマる (戦犯)
  • B はあんまり読んでない (kawabys さんが AC)
  • C を見たら各頂点の深さみてよしなに足し合わせたらいけるなあとなってので書いて AC。
  • D は最初アルファベットを頂点にして右隣のアルファベットに辺を張るグラフみたいなのを考えていたけど嘘 (戦犯)
  • E は気づいたら kenkoooo さんが AC していた (すごい)
  • F は kawabys さんと kenkoooo さんが考察していたけどつらかったらしい (自分は他の問題やってて参加できなかった)
  • K を見たら DP なのかなあと思って書いていたけど、教科の最高点が複数人いた場合に詰むことが判明しておしまい (戦犯)

結果、4 完 20 位。全体的に戦犯でした。

懇親会ではいろんな人と話せて面白かったです。競プロサークルの事情はどこも同じようで、最初は大量に入ってくるけどその分幽霊部員もたくさん出るよねーみたいな話をしていました。九大の方々が今後の新歓について真面目に議論していてアツかったです。

2 日目 (会津大セット)

yurahuna さん、 odan さんとチーム toy18 で参加しました。

  • A 問題はやばかったらしい (yurahuna さんが AC)
  • B 問題は lower_boundupper_bound 使えばいいだけだったので書いて AC。
  • C 問題は odan さんから方針の相談をされたので、定数項を素因数分解して入る数字の候補を減らしていこうということを言った (でも実際範囲狭かったのでこれをやらなくても全探索で OK) odan さんは構文解析のプロなのですぐ実装してくれて AC。
  • D 問題は DP を考えていて、最初  10^{8} 回くらいの計算になりそうな感じの DP が出来上がって計算量的に不安だったけど書く → ひたすらバグるので 2 人に相談 → DP の方針を変えようということになり、想定解法と同じ DP にたどり着く → 添え字がややこしすぎる → yurahuna さんとひたすらデバッグをする → AC!!!!

この問題だけでコンテスト時間の半分を消費したといっても過言ではないかもしれません。正直チームメンバーがプロなので通った感じで、自分ひとりだったら完全にあきらめてましたね。本当に感謝です。

  • E 問題は平均最大化するだけといって yurahuna さんが早々に AC (ほんまプロ)

結果、 5 完 8 位。最終的に D が通ったのが大きかったですね。

懇親会はなんと RCO さんの援助があり費用が無料に。競プロ er に理解のある RCO さんに感謝です。自分の卓は北大・会津大・名古屋大・九大と津々浦々から来ている感がすごくて楽しかったです。チンチロやったら 3 つとも 2 の目が出たのはビビった (運を使い果たした)

3 日目 (北大セット)

いよいよ北大セットお披露目のときです。実は結構バタバタしていて、AOJ に初めて問題をアップしたのが前日の夜 10 時くらいで、最終稿が載ったのが当日の午前 9 時前後でした。原因としては私が AOJ 側にコンタクトを取る方法を知らなかったことと、準備の段取りを先輩方に聞くのが足りなかったことですね。次回は反省を生かして 3 日前くらいには上げられるようにしたいです。

コンテスト運営を 1 人でやるのは不可能だからと、ジャッジチーム側に tubo28 さんがまわってくださいました。実際 1 人 (しかも作問側未経験) では運営不可能だったので、本当に助けられました。

バタバタしながらもコンテストがスタート。私は総評とスライドの手直し、それから風船運びをしながら過ごしていました。

問題のこといろいろに関しては、長くなったので別記事を見てください。

プロがたくさんいる中で解説をしなければいけなかったので相当緊張しましたが、何とか終わったので良かったです。次に解説するときまでには自信もって解説できるくらいの力をつけたいですね。

まとめ

オンサイトはいいぞ。初参加でしたがとても楽しかったです。やっぱりチーム戦はいいですね。

あと帰りに買った漫画がよかった。以上です。

ICPC 国内予選 2016 D: ダルマ落とし

昨年歯が立たなかっただけに解けてうれしい。

問題概要

原文を参照してください → Daruma Otoshi | Aizu Online Judge

解説

take[i][j] := 区間 [i, j] のブロックを全て取ることができるか となる bool 型の配列を用意します。まずはこの take 配列に対して、真偽値を正しく入れていきます。

条件より、区間の長さが  2 であるときの判定は容易です。問題はその後でしょう。

次の  2 つの事項を確認することによって、より長い区間についても判定できるようになります。

  • 区間  \left[ i, j \right] のブロックを全て取ることができ、かつ  i-1 番目と  j+1 番目のブロックの重さの差が  1 以下であれば、区間  \left[ i-1, j+1 \right] のブロックを全て取ることができる
  • 区間  \left[ i, k \right] 区間  \left[ k+1, j \right] について、両区間に対して全て取ることができるならば、区間  \left[ i, j \right] のブロックを全て取ることができる

したがって、以下のようにすれば take 配列を正しく構築できます。

  • 区間の長さが短い順に以下を行う
  • 長さが  2 であれば、重さの差が  1 以下であるかを判定して配列を更新する
  • それ以外の長さであれば、より短い区間の結果を使って配列を更新する

この配列を元に答えを出すのですが、これに答えるには以下の補題を解かなければなりません。

 \left[ 1, N \right] の中に、長さが  N 以下の区間がたくさんある。その中から、区間どうしが同じ頂点を被覆しないようにいくつかの区間を選ぶときの、被覆できる頂点数の最大値を求めよ。

これは DP で解くことができます。

dp[i][j] := 区間 [i, j] において被覆できる頂点数の最大値 となるような配列 dp を用意します。

この配列の初期化は各区間を見ることによって行います。例えば 長さ  M区間  \left[ a, b \right] があったとします。 \left[ a, b \right] において被覆できる頂点数の最大値は当然  M なので、dp[a][b] = M が成り立ちます。これを全区間に対して行うことで初期化します。

あとは dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]) と更新してあげることで正答が得られます (発想としては前述の「より長い区間に対しても判定できる」の箇条書きの  2 つめと一緒です)、 O(N^{3}) パワーを信じましょう。答えになるのは dp[0][N-1] です。

ソースコード

bool take[310][310];
int dp[310][310];

signed main() {
    int n;
    while(cin >> n, n) {
        int w[310];
        rep(i,0,n) cin >> w[i];
        memset(take, false, sizeof(take));
        memset(dp, 0, sizeof(dp));

        rep(i,0,n) {
            rep(j,0,n-i) {
                int len = i+1;
                int s = j, t = j+i;
                rep(k,s,t) {
                    if(take[s][k] && take[k+1][t]) take[s][t] = true;
                }
                if(len == 2) {
                    if(abs(w[s] - w[t]) < 2) {
                        take[s][t] = true;
                    }
                }
                if(take[s][t]) {
                    int x = s-1, y = t+1;
                    while(1) {
                        if(x < 0 || x >= n || y < 0 || y >= n) break;
                        if(abs(w[x] - w[y]) >= 2) break;
                        take[x][y] = true;
                        x--; y++;
                    }
                }
            }
        }

        rep(i,0,n) rep(j,i+1,n) {
            if(take[i][j]) dp[i][j] = j-i+1;
        }

        rep(i,0,n) rep(j,i,n) rep(k,i,j) {
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
        }
        cout << dp[0][n-1] << endl;
    }
    return 0;
}

当時は「DP を  2 回やる」みたいなことを呟いている人がたくさんいるのを見て、こんなんできるわけ無いだろうと思っていたけど、今見ると DP を  2 回やる気持ちが確かに分かる。