ICPC 国内予選 2019 参加記

参加記を書き書き。 (激寒)
5年連続チーム catsatmat で参加して国内9位で予選通過しました。

• 練習

数回しか3人では練習してなかった (国内予選/アジア地区はかなり埋まっていたのでCF gymなど5時間セット中心) あとはopencupにたまに出た (opencupはcamypaper さんと出ることが多かったが)

• 当日

実習で遅刻しかけてヒヤヒヤしたがまあ自分がいなくても行けるのでは？とも思っていた。間に合ってホッとした。

開始したらcatupperが印刷にいき、shiatsumatに設定してもらいつつAを読み、自分が通した。Bを帰ってきたcatupperに投げて自分はCを読む。shiatsumatには後ろを読んでもらう。

Dで困っていたので概要を聞き、どうせDPでしょと言いながらCを詰めているとcatupperが合流して漸化式を立ててくれていた。自分がCの見積もりになぜか失敗して無限に実行が進まず途方にくれていたら気づいたのでDに代わる。途中で数回改善を思いついたのでパソコンを奪いつつやっていきCとDが同じような時間に終わった。C, D同時並行してる間にshiatsumatにE以降を読んでもらった。

Eは頑張る系だということでshiatsumatに実装を考えてもらいつつF以降を検討していく。F全然わからなくて焦っていたらcatupperがGの解法を思いつくが実装が大変と主張していた。

ここまで相当出遅れていたので順位表を見た感じでEをやり切る必要があるのではという結論に至り、しかし自分はEを丸投げしてF絶対解くマンをしていた。catupperと議論もしたが全然まともな解法が出ず、しかし気付いたら解法を思いついており実装も軽そうなのでEがバグったところでパソコンを奪い通す。

あとはE通さないとやばいかな〜といいつつGを完全に諦める。Eだいたいできていそうだったので手でケースを提案したり、if文コメントアウト二分探索 (サイアク) をしたりする。あと数分というところでEで判定パートではなく列挙パートがミスっていることに気付く (こんなの気付かないでしょ)。コンテスト終了。かろうじて10位に入っており安堵。

• 反省

今まで本番として3人で出た大会の中では1番相談が上手く行ったのではないか。自分がCをバグらせていたのが相当罪が重いがFが解けて±0くらいにはなった。Eも複数人でチェックしたらいい感じであと5分あれば通ったんじゃないかなあ。ABCDFをさっと通してEとGを分担して詰めるみたいなのが出来ればよかったが... コンテストの成績はかなり危なかったがまあこういうこともあるでしょくらいの範囲には収まっていそう(実力不足) まだアジアもあるので5年間の総括は今度にします。

全国統一プログラミング王決定戦本戦 G - Greatest Journey

コンテストではFで辺のコストをmin(C[i],C[j])だと勘違いして破滅しました(こちらも解けるらしいのですが) サンプルに書いてあるやん(絶望)と最後の方に気付いて悲しいね。Gの解説がア(上級者向け)なのでメモを残しておきます。

まず、どういう移動が最適かを考えます。

どの辺も複数回通ってもいいという制約のもと、通った辺のコストが順にa_1,a_2,...,a_Lだとします。

この中のmax=Mをとるindex(複数ある場合は1番左)をpとすると、a_{p+1}...,a_LをMに置き換えてよい(途中から往復し続ける)ことがわかります。

Mに最短で至るまでの経路は全て1回は使わないといけないが、M以前で複数回使うような辺があったとき重複分をMにやってもらった方がいいこともわかるので、iさんはV_iからある頂点まで最短で移動した後、同じ辺(しかもそこまでの経路でmax)を使い続ける形のみを考えればよいです。

次に、こんなの分割統治(重心分解)するしか、ないだろ。という気持ちになるところは多分慣れです。

重心分解では、重心を通る移動のみを考えて後は各部分木に分ければいいので、一旦重心に集めます。V_iから重心Gまでの辺の数をE_i, コストの和をC_iと置きます。

重心GからDFSして各頂点vまでの辺の数をD_v, コストの和をB_v, vの親をp_v, vの親とのコストをw_vとし、V_iからGを経由してvまで行き、vとp_vの間を0回以上往復します。(vまで行って親の方向に往復すると考える方が考えやすいです(子はたくさんあることもあるので))

このとき各クエリiについて、C_i+(L_i-E_i-D_v)*w_v+B_v = C_i+(L_i-E_i)*w_v+(B_v-D_v*w_v) のvについての最大値(vまで辿りつける、つまりL_i - E_i - D_v >= 0の条件の下で)を速く求めたいです。見やすさのためにL_i-E_i をL'_i, B_v-D_v*w_vをB'vとおき、iについての定数項(C_i)を無視すると max L'_i * w_v + B'v (ただし L_i - E_i - D_v >= 0) となり、直線y=w_v*x+B'vたちのうちx=L'_iで1番上にあるものがわかればよいです。

まだ考慮できる頂点にL_i - E_i - D_v >= 0の条件があるため好きな順番に直線を追加する必要があり大変に思えますが、上で見たようにGからvまでのパスにおいてmaxではない辺を複数回使うものは考えなくてよく、maxの辺のみを使うことを再び考えます。(考慮する頂点のうち)適当にvを取ります。x=d(D < D_v)でvが選ばれないことが言えると嬉しいです。素直にvまでの途中の深さdの点をu (D_u = d)とします。uまで潜ったコストはB_u、vでdを代入した値は(D_u - D_v) * w_v + B_vですが、w_vがパス上のmaxという仮定より(B_v-B_u) <= w_v*(D_v - D_u)であるのでvまで潜らない場合の方がコストが良いです。よってL_i - E_i - D_v >= 0の条件を無視して解いても答えは変わりません。(ここがなかなかわからなかった、まあライブラリが強ければ思考停止でいいので)

結局分割統治の各stepではw_vが小さい順に直線を追加していくことで蟻本のenvelopeの管理と同様にdequeででき、O((NlogN + MlogM)logN)でこの問題が解けました。

ACM-ICPC 2018 Asia Yokohama Regional 参加期

チーム catsatmat で参加して ABCDGK の6完12位でした。アジア地区予選には2016年も参加していて11位だったので、今回の結果は残念なものでした。感想文だけ送るのが面倒なので簡単な参加記も残しておくことにしました。参加記を書き書き。

まず、チームは catupper と satashun と shiatsumat で構成されていて、まあ3人とも橙のどこかみたいな実力してると思います。

• コンテスト前

shiatsumat が来なくて焦った。maroonとcatupperがスマブラをしていて草。US配列に前日必死で慣れた。

• コンテスト

catupperがemacs、satashunとshiatsumatがgeditを使う予定だったのでとりあえずAをcatupperに任せてあとの2人は後ろを読む。

読んでないけど実装が怠いみたいなことを言っていた気がするがA AC(0:14)。

satashunはBを、shiatsumatはCを読んでいたがまだどちらも解けていなかった。

shiatsumatがCはsatashunの方が得意そうというので見たら、マンハッタン距離で個数をカウントして、小さい方から繰り上がらせていけばいいのではということになった。配列サイズが半分しかなくて1WAののち、C AC(0:27) 。

Cが通ったことで落ち着いたのか、続いてBも(今の要素, 前の要素)の組は1回ずつしか見なくていいことに気づき実装。B AC (0:38)。初めmathっぽく考えてしまった(初項を固定してみたりとか)

Dが一瞬で解かれていたのでshiatsumatに読んでもらいつつ後ろを見ていく。自分はJとかKとかを読んだがDをもらう。Gはcatupperが出来たということでG AC(1:08)

この辺まではそこまで悪くなかったのに詰まり始める。

しばらくして satashun さんがDは出来たと主張して実装してバグらせてくれました。アイディアは割とすぐ出たのに遷移がとてもバグってしまった(2つともを処理して終わったかどうかが適当だった) catupperはK出来たというのでパソコンの奪い合いのち、D AC (2:41), K AC (3:04)

Eは苦手なので2人に投げて、パソコンが空いている時間にJをしばらく考えていたらLCAが書ければできることに気付いた。

Jはsatashunさんが担当してバグらせてくれました。Eはcatupper、Fはshiatsumatが書いてた。

残りの時間はJを実装したりEを実装したりFを実装したりという感じだったがどれも通せず。Hもshiatsumatにより解法っぽいものが出てたが色のflipが詰めきれてなかったっぽい。

• 反省

Fは2人とも嘘をついたせいで重いだけに見えてしまったのがミスだった(EとJが手詰まりに見えたからなんですが、冷静に幾何なんてやるべきではないだろ)

Eは自分は見てないけど2人の解法のいいところを取るといい感じだったっぽくて残念。

Jはほとんど合ってたが、lcaが変わる場合の処理が甘かった。終盤時間が足りなくて手元でサンプルを作る余裕がなかった。

Hみたいなの残り2人は得意っぽいので前半を早くして余裕が作れたらチャンスなんだけどなあ(2年前もskinny polygonが終わらなかった)

まあでも学内topが離れすぎていたためとりあえず手を付けた問題を全部解き切るための動きだったので、人を適宜マージしたら1問は増えた(上手く行けば+2)かなあというのがあるが、シンプルに実力不足だと思いました。中盤が多いコンテストだったので少し実力が伸びればだいぶ変わりそうなセットでした。

来年も出られれば5年連続同じチームということになるのでいい結果が残せるといいですね(赤くなろうね)

有理数の探し方

この記事は Competitive Programming (2) Advent Calendar 2018 - Adventar の 12/11 分です(の予定でした)

連分数展開・Stern–Brocot tree には様々な面白い構造があり、たまにプログラミングコンテストでも出題される割にあまり知らなかった(かつ日本語の記事もあまり見たことがない)ので、紹介していきます。
(Farey 数列 という概念も聞いたことがあるかもしれませんが、 Stern-Brocot tree に似たものです)

簡単のため、以下では基本的に非負の有理数を扱います。

• Stern–Brocot tree

唐突ですが、Stern–Brocot treeとは以下のような木を指します (from wikipedia)

まず作り方がイメージしやすい方 (この方法はこの図のイメージと少し違いますが)

初め端にと が書かれています。(0以上の有理数からなる区間を表しています)

ここから、以下の操作を 繰り返して数列を作ります。

• 数列で隣り合う全ての有理数の組 と の間に を書く。

のとき明らかに なので、この列は常に(通常の順序で)昇順となっています。(とが隣り合う時、 という性質も保存されます)

各頂点が区間を持っており、ある区間を分割して出来る2つの区間が子となった2分木のようなものをイメージすると良いです。

この図から、分母が小さい方から有理数が列挙されていく様子を感じてもらえると思います。

次に詳しくこの木の性質を見る前に、この木と深い関わりのある 連分数展開 を紹介します。

• 連分数展開

ここではsimpleな表現のみを考えます。(以下のように、各部分の分子に1しか使えないもののことです)

有理数 x が連分数展開として と表されるとき ] と表記します。

例えば、 なので、] です

この連分数の作り方は Euclid の互除法に似た操作となっています。各stepで、を表したいとして、 (ただし、) と表せます。

有理数 を連分数展開して]となったとします。(k : 非負整数, a_0 : 非負整数, a_1, .. : 正の整数)
のとき、] ]ですが、最後が1であることを許さなければ一意に表せます。
(雑ですが、 は正かつ1以下(1となるのは、hogeが無かつa_i=1の時だけ)であるため、毎回整数部分を入れていくしかないので)

まずこの表現の場合、根は[1]です。

そして、] ()]の子は、Stern–Brocot treeにおいて]と}です。

小さい方を左の子にするのですが、これはその数列の長さの偶奇によって変わって、奇数の時は末尾を+1したものの方が大きく、偶数の時はその逆です。

逆に、この頂点の親はakから1を引いたもの(akが1になったら撤去してa_{k-1}に1を足す)ことによって得られます。

(連分数展開をexplicitな展開を書く)

Stern-Brocot tree には綺麗な性質があって、

1. 二分探索木を成す
2. 全ての既約な有理数が1度ずつ現れる

ある頂点の左子孫は全て自分より小さく、右の子孫は全て自分より大きいという性質を満たします。これも深さの偶によりますが、連分数展開で今見ているところ以降を操作すると、右下の部分が変わるだけで

これまた雑ですが、全部が網羅されていそうなことの雑な説明です。

まず深さdには全て異なる2^d 個の頂点があります。

を観察すると、深さdにある頂点ではこの和がd+1となっていることがわかります。

先頭のみ0が許される & (先頭でない)末尾は1が許されない ような 和が d+1 の個数を考えます。

d=0の時は[1]のみなので良いです。それ以外の時、oがd+1個あって、末尾と、末尾の1つ手前以外に仕切りを入れると列になるのでこれは 2^d 通りです。

導入が複雑(雑)でしたがこういった性質を利用すると、有理数で近似・有理数の数当てゲーム(例えば整数であれば普通の2分探索で解ける) などができます。

(近似は結構複雑なのでそのうち追記したいですが、気になる人はwikipediaのcontinued fractionを見てください)

• 例題

XVIII Open Cup named after E.V. Pankratiev. Grand Prix of SPb
E. Decimal Form

なる整数a,bを用いてa/bを計算したものを小数点以下18桁にしたものが10^4個まで与えられるので、それぞれa,bを答えてください

Stern-Brocot treeの上で探索したいのですが、実は下る向きを変える(左の次は右、右の次は左)とすると分母がだいたい倍になるので O(log max) 回しか方向転換せず、それぞれでは doubling してまっすぐ下りることで解けます。別の解法としては、小数点以下18桁の x が与えられるは a/b が[x-10^-19, x+10^-19) に入るということで、この両端を連分数展開すると近似の問題として解くこともできます。

JOI春合宿 2008 day3 Fraction

を満たす既約分数a/bのうち小さい方からk番目を求めよ。

kが小さいので、この二分探索木に小さい方から潜るだけで良いです。(知識...) (既約なものってそんなにないのでは(トーシェント関数の累積和を評価すればよい))

• ギャグ

Pythonのfractionsにはなんと分母のmaxを指定して近似する関数 (limit_denominator)があります。なんてこった。

• 参考

Spaghetti Source - Stern-Brocot 木

Grand Prix of SPb - Codeforces

WebDiarios de Motocicleta: Rational Search

Stern–Brocot tree - Wikipedia

Continued fraction - Wikipedia

https://www.ipsj.or.jp/07editj/promenade/4503.pdf

説明は自分で考えたところが多いので誤りがあったり、他にも面白い応用(や問題)があったら教えてください。

ICPC2018国内予選 H問題

今年もチームcatsatmatで出場しました。4位で通過出来て嬉しかったです。

• H問題

前原先生の記事
木上のナップサック問題
でだいたいわかりますが、コードを載せておきます。

まず、素直な解法として、dp[v][c] := vの部分木についてコストcで得られるmaxとおくとO(nkk)ですが、このままでは高速化が難しいです。

ポイントは、各頂点vの子たちを、vの必要量の昇順に並べておくと、ある子に潜ることが出来る時その手前の子たちも全部使えて、このことを利用するとdpの配列を持ちつつdfsすることができるという点です。これだけでオーダーが良くなるのは不思議な感じですね。これに加えて各頂点に使える上限があるので面倒になっています(このパートはスライド最小値をやると線形で解けます)　よって時間計算量はO(Case * NK)です。100*100*10^5 = 10^9を8秒なので結構実装に気を使わないといけません。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; ++i)

typedef vector<int> vi;
typedef long long ll;
typedef vector<ll> vl;

const ll inf = -1e18;
const int MN = 110;
const int MK = 100010;

inline void chmax(ll &x, ll y) { if (x < y) x = y; }

int n, k;
vi g[MN];
int h[MN], s[MN], lo[MN];
vl dp[MN];
int deq[MK];

void dfs(int v, vl vec) {
    vl &res = dp[v];
    
    int l = 0, r = 0;
    
    for (int i = 0; i <= k; ++i) {
        if (vec[i] != inf) {
            ll x = vec[i] - (ll)i * s[v];
            while (l+1 <= r) {
                int id = deq[r-1];
                if (vec[id] - id * (ll)s[v] <= x) {
                    --r;
                } else {
                    break;
                }
            }
            deq[r++] = i;
        }
        if (l+1 > r) {
            res[i] = inf;
            break;
        } else {
            res[i] = vec[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
            if (deq[l] <= i - h[v]) {
                ++l;
            }
        }
    }
    
    for (int to : g[v]) {
        dfs(to, vec);

        vl &nx = dp[to];
        
        for (int i = 0; i <= k; ++i) {
            chmax(vec[i], nx[i]);
        }
        
        l = r = 0;
        for (int i = 0; i <= k - lo[to]; ++i) {
            if (nx[i] != inf) {
                ll x = nx[i] - (ll)i * s[v];
                while (l+1 <= r) {
                    int id = deq[r-1];
                    if (nx[id] - id * (ll)s[v] <= x) {
                        --r;
                    } else {
                        break;
                    }
                }
                deq[r++] = i;
            }
            if (l+1 > r) {
                nx[i] = inf;
                break;
            } else {
                ll val = nx[deq[l]] - (ll)deq[l] * s[v] + (ll)s[v] * i;
                chmax(res[i + lo[to]], val + (ll)s[v] * lo[to]);
                if (deq[l] <= i - (h[v] - lo[to])) {
                    ++l;
                }
            }
        }
    }
}

int main() {
    while (cin >> n >> k, n) {
        rep(i, n) dp[i] = vl(k + 1, inf);
        rep(i, n) g[i].clear();
        rep(i, n) cin >> h[i];
        rep(i, n) cin >> s[i];
        for (int i = 1; i < n; ++i) {
            int p; cin >> p; --p;
            g[p].push_back(i);
        }
        for (int i = 1; i < n; ++i) {
            cin >> lo[i];
        }
        rep(i, n) {
            sort(g[i].begin(), g[i].end(), [&](int a, int b) {
                return lo[a] < lo[b];
            });
        }
        vector<ll> vec(k + 1, inf);
        vec[0] = 0;
        dfs(0, vec);
        cout << *max_element(dp[0].begin(), dp[0].end()) << endl;
    }
    return 0;
}

2016-2017 National Taiwan University World Final Team Selection Contest

結構前のコンテストですが、G問題がシンプルだけどどこか新鮮で面白かったので紹介します
Dashboard - 2016-2017 National Taiwan University World Final Team Selection Contest - Codeforces

概要
N個(値段:p_i)の空でない部分集合であってK番目に値段の和が小さいものを求めよ(復元なし)
2 ≤ N ≤ 2 × 10^5
1 ≤ K ≤ min(10^6, 2^N - 1)
1 ≤ p_i ≤ 10^8

解法
まずpを小さい順にソートします。もちろん2^N通り全列挙は出来ないのと、Kはあまり大きくないので、小さい順に列挙することを考えます。
ここで、ある集合の1番右のものの次を続けて使うorある集合の1番右をやめてその右隣を使うという遷移をすることにすると、価値が単調に増加するように遷移出来て嬉しいことがわかります。(イメージしにくいですが)
よって、priority_queue等で管理しつつ遷移していくことでO(KlogK)で解くことが出来ました。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const int MN = 200010;

int N, K;
int p[MN];

int main() {
	scanf("%d %d", &N, &K);
	rep(i, N) scanf("%d", &p[i]);
	sort(p, p + N);

	using Data = pair<ll, int>;
	priority_queue<Data, vector<Data>, greater<Data>> que;

	que.push(mp(0LL, -1));

	ll la = -1;
	++K;

	while (K--) {
		Data t = que.top(); que.pop();

		ll val = t.fi;
		int pos = t.se;

		la = val;

		if (pos == N-1) continue;

		//add next
		que.push(mp(t.fi + p[pos + 1], pos + 1));

		//replace
		if (pos != -1) {
			que.push(mp(t.fi + p[pos + 1] - p[pos], pos + 1));
		}
	}

	cout << la << endl;

	return 0;
}

ACM-ICPC 2016 Asia Tsukuba Regional 参加記

チームcatsatmatで出場してABCDEFGの7完11位でした。真面目にUSキーボードの練習をしたので今度はJISがわからなくなって困っています。しかし環境に慣れていなかったのはアレかなあ　自分はgeditで頑張りました

まずコンテストパートについて

自分はパソコン操作が苦手なのでAはとりあえずさっさと書ける人(catupper)が通した

Bをshiatsumatが読んでやるだけというので書いてもらっている間に, 自分がCを読んでcatupperに話したら一瞬で区間と言われすごい(小並感)となった B少し面倒ということで実装が軽そうなCを先に通すことにした　FAだった

そしてBの続きをやってもらって無事AC

Cをやっている間にshiatsumatたちがDを読んでにぶたんではと言っていたが普通に嘘なことに気付いた　あぶなかった
普通にO(N^2logN)で出来ることはすぐにわかったが, 26倍とかをつけるとTLEが不安だと思った(ここでとりあえず投げたらみたいな声が出たので投げたが普通に手元でテストするべきだった...(その後結局手元で最大ケースを作って試したので))
vectorをsetに突っ込むのをやめて適当なhashにしたがTLE
ここで両方setに突っ込んでから答えを求めるのが自明に無駄で片方しか突っ込まないことにしたら2倍速くなってACした
この辺でかなりもたついてしまった...

Dをやっている間に問題を読み進めてもらう
Eは後回しで良くないという感じになりその後のFはshiatsumatが解法を思いつき, Gはcatupperが読んでいて問題を説明して貰うと自分が思考停止segment treeと言ってしまい面倒な方針になってしまった(実際にはsegtreeがすぐ書ければよかったが, 座圧しにくくて必要なところだけ作るsegtreeになったため(JOIのapples的な))ライブラリを写さずsegtreeパートにバグを埋めるのに気付くのに時間がかかって残念

FGを書いたりデバッグされたりしていてHはかなり大変そうに見えたので大人しく自分がEを書くことに
というかFはあんまり通されなかったのにすごい(小並感)
FとGで共にWAを出して並列にデバッグしたため同じくらいにACとなった

H以降を考えてもらう間にEを自分が頑張って書く
普通に全探索して文字列を生成して, 生成した文字列が正しいかチェックする関数に投げまくる方針だった
構文解析にあまり慣れていないのと, 正しいとは限らない文字列をパースするのがややこしくて結構混乱してしまった
return がところどころ抜けていたり, C++に疎いので例外を投げるのではなくてINFを返す実装にしたらところどころINFだったらINFを返すみたいなのを忘れてしまったりしてデバッグが大変だった
デバッグしていたら出来たので提出したらTLEが返ってきて!?!?!?となった
パースする関数が無限ループしてるのかと思って真面目にチェックしたが結局全列挙パートを速くしたら通ってなんやねんとなった
ここでめっちゃ時間かかったの戦犯ですね...

最後の方はcatupperがHを慌てて書いている間にIを自分とshiatsumatが考えていた
やばそうな方針を誰かが提示しては計算してどれくらいになりそうかチェックするやつをやっていたが,
それまで出ていた方針と, なんか対角線とそれに近い点を取ってくるやつを合わせれば上手くいきそうなことが終了間際にわかった
Iは好き

終了

感想 :
メンバーの実力が近くてGまではまあ誰がどれをやっても解き切れそうな感じだったのは良かったと思う
Iを通せなかったのは反省
HJKは現状厳しい感じだったので各自もう少し実力が必要
やっぱり慣れない環境で問題を解くと時間が凄いかかって大変ですね
surreal numberってなんやねん(呆然)

コンテストパート以外
１日目、着くといきなり受付が英語でここは日本か？？？となった
日常生活で疲れが溜まっていたため交流パートは頑張れなかった
ホテルがこの前泊まったところだった、QOLが高かった(睡眠も良く取れた)
イベントとしてよく出来ていてすごい(小並感)
コンテスト後の懇親会的なものは、ブースがたくさんあって何か思っていたのと違った
クイズを解いたり、色々なものを貰えて嬉しかった(realforceのキーボード, 水樹奈々の謎DVD, その他たくさん)
楽しかったので来年も盛り上がってほしい
C某d某F某s某i某a某の宣伝が多く感じた(たのしみ)

海外の地区には行かないので(行く意味もあまりないけど)
来年もがんばるぞい(東大は地区予選に行くのすら大変なため)

良いコンテストありがとうございました