PCK2017 予選11 ネットワークの課金システム

自分のブログの存在を完全に忘れていた(おいおい)。問題を解きました。

Charging System for Network | Aizu Online Judge

 

問題概要

頂点数Nの木(各辺s-t はコストc[s,t]を持つ)と整数Kが与えられる。以下のクエリをQ回処理する。

  • send : 2頂点u-v間のパスのコストの総和を答える。ただしコストがKの倍数である辺は0として計算する。
  • add : 頂点uから伸びているすべての辺のコストをd増やす。

制約は 1<=N,K,Q<=10^5

解法

明らかに「Kの倍数は0とする」の部分が厄介です。

addクエリは頂点に足された値を記録しておけば(これをa[u]などと書きます)辺u-vのコストは c[u,v]+a[u]+a[v] と計算できるが、sendクエリで普通に辺を1つずつ見ていくとO(N)かかってしまってダメ。

「Kの倍数は0とする」の操作をaddに押し付けることができればsendはオイラーツアーなりなんなりで高速に答えられるようになるけど、今度はaddで頂点の周りの辺をすべて見ないといけないのでO(N)かかってしまう。

 

八方塞がりに思えるのですが、ここでHL分解の以下の性質を思い出します。

(HL分解そのものについては書かないです、ごめんなさい(僕はこの方の記事で勉強しましたHeavy-Light Decomposition - beet's soil))

  • 各頂点についてそこから出るHeavy edgeは高々2本 
  • 各パスについて、通るLight EdgeはO(logN)本

 

するとこのような折衷案が思いつきます。

  • addクエリでは、頂点に足された値を記録した後、Heavy Edgeの値を更新する。
  • sendクエリでは、Heavy Edge は更新されているのでそのまま利用して、Light edge については1つずつ計算する。

 

上記の性質により、addクエリでは2箇所、sendクエリではO(logN)箇所しか計算をしないので高速に行うことができます。求めたいものは区間和なのでセグメントツリーを用いることで、addクエリをO(logN)、sendクエリをO((logN)^2)で処理でき、全体計算量は最初の入力等も含めてO(NlogN+Q(logN)^2)となり無事解くことができました。

 

実装↓ (雑然としているのでアです)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3100945

 

 

 

ICPC2018 国内予選 参加記

ICPCお疲れ様でした。先に結果だけ書いちゃうとABCDの4完で30位でしたが学内順位の問題でアジアには行けませんでした。

以下軽い振り返りです。

メンバー

  • tempura0224 ぼく。ABとDorEを担当する予定だった。
  • zunda1st BCあたり担当。
  • chocorusk EorD,特に数学担当。

全員数学科で競技プログラミング経験は3人合わせて15ヶ月。

コンテスト

とりあえず予定通りぼくがAを開いて解く。

流石にすぐにできてBを見たらできそうだったからそのままやる。適当にやりすぎて1WA(悲しい)。

Cの進捗をzundaに聞くと微妙っぽかったので一緒に考えるとなんか解ける。適当に実装したら今度はちゃんと通る。

chocoruskがDは全探索でいけるというので全探索を書く。ぼく中心で実装したけどミスりまくって横から指摘されまくる。これ最初からぼくが実装しないほうがよかったのでは。いざ書き上がると一発で通る。

chocoruskたちにEを任せてFGを考える。これが完全に判断ミス(幾何も構文解析もろくにできないのになんで行ってしまったのか)。

トイレに行ったり教室内を走り回ったりしてるとEの解法が生えたので書いてみる。サンプルが全然合わなくて泣く。場合分けと評価の順番をミスりまくっていると教えてもらったので直す。サンプルが最後以外通って「浮動小数点例外」って怒られる。ナニコレ。何が違うのかわからないままコンテスト終了。

 

反省と感想

これの読者は大体わかると思うんですけど浮動小数点例外は0除算でした。エラーコード136とか言ってくれたらわかったのにっていうのは流石に言い訳でこれに気付けないのは本当にひどい。

弊大学は無駄にハイレベルで5完高速じゃないとダメだったらしいので完敗。

とはいえBのWAがなくてDの実装をchocoruskに任せてその間にEを詰めるとかしてれば無理じゃなかったような気もするので悔しい。まぁ0除算に気付けなかったので完全に論外なんですが。

 

ぼくは早生まれな関係で来年も出場資格があるらしいので実装力(とタイピング)を鍛えて来年こそはアジア行きたいですね。組んでくれる人見つかるといいな。

ARC094 F Normalization

　はい。ARC094のF問題(F - Normalization)の解法です。解説(aを0、bを1、cを2だと思うと和のmod3が保たれるとかいうやつ)がド天才だったのですが、もう少し思いつけるかもしれない解法でACしたので投稿します。

　といっても結局mod3を見ることにはなってしまうのでそこに至るまでのステップも書いていこうかと思います。

解法

　まず、操作後の文字列はどこかに同じ文字が連続する部分があるということはすぐに分かるのですが、それだけでは条件が足りなさそうです。また、操作の順番によってできる文字列が変わる(というか操作の順番を変えるとそもそも操作ができなくなることもある)ので左から順番に操作するorしないでDPといったことも出来なさそうです。ということで別の方向で考えてみましょう。

　数列や文字列に対して何らかの操作を施すタイプの問題では、

操作の前後で変化しないものに着目する
という方法が有効なことがあります。また、今回のように操作が3種類ある場合すべての操作に対して共通してなりたつものを見つけるとよいです。具体的に今回の問題の操作での個数の変化を見てみましょう。
  1. ab→cc　　　a：-1、b：-1、c：+2
  2. bc→aa　　　a：+2、b：-1、c：-1
  3. ca→bb　　　a：-1、b：+2、c：-1

「2増える」「1減る」という操作を同一視したいなぁという気持ちになりますね(なって。)。この時点でmod3に気づく人もいるかもしれませんが、さらにこれもよくある手法として、「個数の差(和)はわりといい性質を持ちがち」というのがあります。ということで各操作でのaの個数とb,cの個数の差の変化を見てみましょう。

  1. ab→cc　　　a：-1、b：-1、c：+2　　b-a：±0、c-a：+3
  2. bc→aa　　　a：+2、b：-1、c：-1　　b-a：-3、c-a：-3
  3. ca→bb　　　a：-1、b：+2、c：-1　　b-a：+3、c-a：±0

　「aとbの差」「aとcの差」は操作の前後で「3増える」「変わらない」「3減る」のいずれかです。もうわかりますね。操作の前後で「aとbの差」「aとcの差」を3で割った余りは変化しないということです。なるほどここで3で割った余りがでてくるのか、という感じですね。3で割った余りがカギになることに気が付いてさらに考察を進めると解説の方針になるのかなぁ。

　とはいえこれで操作後の文字列に対する重要な性質がわかりました。

  1. どこかに 連続している部分がある

  2. 「aとbの差」「aとcの差」を3でわった余りは最初の文字列と同じ。

この性質をみたす文字列は本当に全部つくれるのかという問題はあるのですが、実は|S|≠3のときはできるらしいです。(証明は帰納法でできるらしい。解説に書いてた。)ということで|S|=3のときだけ全探索することにして、他は上の条件をみたすようなものを数えるためのDPをします。

　具体的には、dp[文字数][最後の文字][(b-a)を3で割った余り][(c-a)を3で割った余り] のようなdpテーブルを2つもって、1つで「2の条件をみたすもの全部」、1つで「2の条件を満たすが連続する箇所は1つも持たないもの」を計算して差をとるのが楽な気がします。

　ということでこれでこの問題をO(27*|S|)くらいで解くことができました。最初の文字列が連続箇所を持たない場合は答えに1足すのも忘れずに。一応自分のACコードのリンクを貼っておきます。

Submission #2374335 - AtCoder Regular Contest 094

 

※追記

　少し考察すると「aとbの差」のmod3が保たれるなら「aとcの差」のmod3も自動的に保たれることがわかるため、dpテーブルは、dp[文字数][最後の文字][(b-a)を3で割った余り]と1つ項を減らして計算しても大丈夫なようです。(Submission #2374698 - AtCoder Regular Contest 094)

感想

　本番中にこの性質に気づけていながら手計算の実験部分を間違えていて解けなかったのはちょっと悔しい。|S|=3の場合だけ無理というのも罠でした。短すぎる文字列なら例外がおこりうることには思い至るべきだったなぁ。700点はさすがに嘘な気がするけどとても面白い問題だと思います。

AGC022 E Median Replace

　AGCお疲れ様でした。EのMedian Replace(E: Median Replace - AtCoder Grand Contest 022 | AtCoder)の解法です。公式の解説が天才すぎたのですけど別の方法で解けたので書きます。

　場合の数をいきなり考えるのは難しいのでとりあえず判定問題を考えます。

　まずいろいろと実験してみると最初の2文字が11だとそれ以降の並びによらず美しい文字列なことがわかります。また、左から順番に見ていったときに、1はなるべく最後まで残すべき(111→1とか110→1とかの操作は極力しない)なことや、0が2つ以上連続していたらそこはさっさと潰して0が1つだけの状態にしてしまったほうがいいということが(直感的にですが)わかります。

　以上をまとめると文字列abcde...が与えられたときにとるべき戦略は

  1. 01cde...のとき：前の01は残しておいたほうがいいのでcde…以下で1をつくれる、つまりcde...が美しい文字列ならよいです。
  2. 00cde...のとき：前の00cは潰して0にするしかないので、0de...が美しい文字列ならよいです。
  3. 11cde...のとき：cde...以下によらず美しい文字列です。
  4. 101de...のとき：前の10は残しておいたほうがいいので、1de...以下が美しい文字列ならよいです。
  5. 100de...のとき：00dの部分を潰して0にしてしまうのが最適で、残る10e...が美しい文字列ならよいです。

　これで、与えられた文字列に対して1回の操作ごとに最低でも長さが2縮まるDPを書けてO(N)で判定することができます。

　数え上げも本質的には同じで、dp[n][a][b]で「n文字の文字列でabで始まるもののうち美しい文字列の個数」とすれば上記と同じ遷移が書けます。?がでてきたときは1と見たときと0と見たときの場合の数を足せばよいです。

　2と5のパターンはそれぞれc、dが?のときは2倍しなきゃいけないみたいな罠があったりするのですがこれでO(N)で解くことができました。

　https://beta.atcoder.jp/contests/agc022/submissions/2289522

　一応コードも貼っておきましたが可読性が死んでます。

 

　ところでこれを通せたのがコンテスト終わってから15分後くらいっていう、、、。

　コンテスト中に通せなかったのは一か所1にしなきゃいけないところが?も許容しちゃってたからなんですけどコンテスト中は気づけないもんですね。Atcoder苦手すぎてつらい。

　しばらくAGCも多いのでどこかで結果が出せたらいいなぁと思います。では。