Bubble Cup8 Finals B. Bribes

問題

概要

$N$頂点,$N-1$本の辺からなるグラフが与えられる.
辺は無向または有向である.
辺の向きを無視したときグラフは連結.
有向辺は逆走することが可能で,その際コスト1がかかる.
ある辺を1度逆走する度にその辺のコストは倍になる.
はじめ頂点1にいて,Kヶ所の頂点をある順序で訪れたときの最小コストを求めよ

制約

  • $1 \le N \le 10^{5}$
  • $1 \le K \le 10^{6}$

解法

グラフが木であることから,ある2点をつなぐパスは1通りしかない.よって移動の仕方は一意に定まる.
すると,それぞれの辺について逆走する回数が求められればよい.
pからqへと移動するときにpからlcaまで辺を登り,lcaからqまで辺を下る.
これをimos法+木dfsでまとめると,ある辺を登る回数と,下る回数が分かる.
通った辺について,繰り返し二乗法を使うことでコストを高速に求められる.
計算量O(Nlog(N)+K).

コード

テンプレート部,ライブラリ部は省略する.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
public class Solver
{
public void Solve()
{

var n = sc.Integer();
var G = Enumerate(n, x => new List<KeyValuePair<int, int>>());
for (int i = 0; i < n - 1; i++)
{
var a = sc.Integer() - 1;
var b = sc.Integer() - 1;
var c = sc.Integer();
G[a].Add(new KeyValuePair<int, int>(b, c));
G[b].Add(new KeyValuePair<int, int>(a, -c));
}

//LCAとかの構築
var par = Enumerate(32, x => Enumerate(n, y => -1));
var depth = new int[n];
Action<int, int, int> dfs = null;
dfs = (prev, cur, dep) =>
{
depth[cur] = dep;
par[0][cur] = prev;
foreach (var to in G[cur])
{

var next = to.Key;
if (next == prev) continue;

dfs(cur, next, dep + 1);
}
};
dfs(-1, 0, 0);
for (int i = 0; i < 31; i++)
for (int j = 0; j < n; j++)
{
if (par[i][j] == -1) par[i][j] = -1;
else par[i + 1][j] = par[i][par[i][j]];
}


Func<int, int, int> getLCA = (u, v) =>
{
if (depth[u] > depth[v]) { var tmp = u; u = v; v = tmp; }
for (int k = 0; k < 32; k++)
if ((((depth[v] - depth[u]) >> k) & 1) == 1)
v = par[k][v];
if (u == v)
return u;
for (int i = 31; i >= 0; i--)
if (par[i][u] != par[i][v])
{
u = par[i][u];
v = par[i][v];
}
return par[0][u];
};

//ここからクエリ処理
var m = sc.Integer();
var vs = new List<int>() { 0 };
foreach (var x in sc.Integer(m))
vs.Add(x - 1);

var up = new int[n];
var down = new int[n];
for (int i = 0; i < m; i++)
{
var p = vs[i];
var q = vs[i + 1];
if (p == q) continue;
var lca = getLCA(p, q);
up[p]++;
down[q]++;
up[lca]--;
down[lca]--;
}
Func<int, int, KeyValuePair<int, int>> dfs2 = null;
ModInteger ans = 0;
dfs2 = (prev, cur) =>
{
var u = 0;
var d = 0;
foreach (var to in G[cur])
{
var next = to.Key;
if (next == prev) continue;
var res = dfs2(cur, next);
u += res.Key;
d += res.Value;
if (to.Value == 1)
ans += ModInteger.Pow(2, res.Key) - 1;
if (to.Value == -1)
ans += ModInteger.Pow(2, res.Value) - 1;
}
up[cur] += u;
down[cur] += d;
return new KeyValuePair<int, int>(up[cur], down[cur]);
};
dfs2(-1, 0);
IO.Printer.Out.WriteLine(ans);
}
static T[] Enumerate<T>(int n, Func<int, T> f) { var a = new T[n]; for (int i = 0; i < n; ++i) a[i] = f(i); return a; }
}

まとめ

はじめHLとかで解こうとしてしまったけど,木dfsでシンプルに解ける.根方向にimos法をするのは新しい知見だった.

BubbleCup writeup

sugim48さん,kmcode1さんとcamypaperでunkokmpaperというチームで参加しました.9問中6問解いて21位とかなり好成績だったと思います.

解いた問題:B,C,D,F,G,H

時系列的な日記(間違いとかが含まれている可能性がゼロではない)

開始直後,とりあえず問題を分担して読むことに

  • kmcodeさん: A, D, G
  • camypaper: B, E, H
  • sugimさん: C, F, I

開始直後

開始後数分でDを解く人が現れ始める.kmcodeさんに考えてもらう.
Bを考えるものの,HL+Fenwickとかだと1秒だと間に合わないなぁと思う.
sugimさんがCを読んでFへ.

F

kmcodeさんがDをWA.考えることに.その間にsugimさんにFを通してもらう.(1完)
Hが簡単そうなもののちょっとすぐには思いつかなかった.

D,H

sugimさんがそのままDをやることに,kmcodeさんにHをお願いする.
sugimさんが爆速でDを通す(2完).
続けてkmcodeさんがHを通す(3完).

B

Bをeuler-tour+BITで解こうと思い,PCをもらう.1から実装するのがめんどいことに気づいて冷える.
kmcodeさんにBの実装を任せようと思っていたところで,sugimさんがdfs+imos法でできるということで任せる.
僕はちらほら解いている人間がいるGを読むことに.
Bを1WA後sugimさんが通す(4完).

G

3人でGを読む.拡張ダイクストラ系っぽいけど,解法が思いつかず冷える.
leading_zeroを無視したとき,文字列の長さ最小であって辞書順最小のものを求めたいというところまでまとまる.
ゴールから長さ0の辺だけをたどっていけるところを始点としてダイクストラみたいなのはどうかと提案する.
sugimさんからよさそうという答えが帰ってきたので実装をお任せする.
その間にAとCを僕とkmcodeさんで分担することに.

Aを読んで冷える.kmcodeさんとCについて話す.
メモリの制約が4MBでヤバい(確信).bitDPとかはできなさそう.$N<=20$だし半分全列挙とかかなぁとか考える.
考察をしている間にsugimさんがGを通す.完全にプロ.(5完).

C

sugimさんにAを見てもらう.
とりあえずkmcodeさんがCに乱択解を投げる.続いて僕が焼き鈍し解を投げる.しばらく唸ったりHを見ているうちにkmcodeさんがCを解く.ヤバい(確信).(6完)

残り

sugimさんがAができたというのでお任せする.
僕とkmcodeさんでHを考えることに.議論を続ける.
kmcodeさんができたが実装に時間がかかりそうだという.
sugimさんがWAを出して,僕がランダムケースと愚直解を作り終えて,落ちるケースが分かったところで終了.21位.

まとめ

sugimさんとkmcodeさんはプロ.
僕は割と座っているだけだった感があってつらい(◞‸◟).

僕は割と実装とデバッグが遅いところがあるので,問題の概要とか考察とかをまとめて投げるのは戦略としては良かったのかもしれない?

解き直したコードは別の記事で上げることにする.

Windowsセットアップまとめ

最近何度もやってる(つらい)のでいい加減にまとめることにする

chocolateyのインストール

1
@powershell -NoProfile -ExecutionPolicy Bypass -Command "iex ((new-object net.webclient).DownloadString('https://chocolatey.org/install.ps1'))" && SET PATH=%PATH%;%ALLUSERSPROFILE%\chocolatey\bin

入れるパッケージたち

FireFox

chocolateyから入れる必要性があるのか謎
choco install firefox

ConEmu

ターミナルエミュレータ.いろいろ便利.
choco install conemu

Nyagos

コマンドラインシェル.コマンドプロンプトより便利.
choco install nyagos

Git

gitは必要.
choco install git

Atom

エディタ,sublimeでもいい説がある.
choco install atom

NodeJs

hexoを使うのに必要.
choco install nodejs.install

jdk8

javaをコンパイルしたくなることもあるので
choco install jdk8

java

java runtimeが必要なのを忘れていた
choco install javaruntime

VS2015Community

VSはサイコー(オプションが選びたい場合は手でやった方がいいかもしれない)
choco install visualstudio2015community

Skype

稀に使わなくもないから入れる
choco install skype

Clover

タブ機能があるエクスプローラは便利
choco upgrade clover

MinGw

GNUツールは必要だった
choco install mingw

その他個別に入れるやつ

  • mono
  • Go
  • Rapid Environment Editor

良問,面白かった問題リスト

今まで解いた問題で面白かった問題をまとめておくことにした.タグっぽいのはネタバレしない程度のタグのつもり.

おすすめ度は☆の数で表すことにする
☆1: 割と面白い
☆2: 面白い
☆3: とても面白い
☆4: おすすめしたいほど面白い

AOJ

  • 夕食: ☆2 考察 最大化

AtCoder

Codeforces

HackerEarth

そのうち

HackerRank

そのうち

yukicoder

topcoder

そのうち

テスト

テストする

Mathjax用のプラグインが動くと信じたいのでテスト
$O(N)$
$a=b+c$

ソースコード

1
2
3
4
5
//C#6.0が使えるジャッジ増えないかなぁ
using static System.Console;
public class prog{
static void Main()=>WriteLine("hello");
}

リンクを貼る

無駄に水平線


ブログをはじめる

ちゃんと記録を残せる場所を作ろうと思ったというだけです.

hexoというのを試してみているけど,難しそうでつらみがある.

あとでテーマとかをいじりたい.