2018-04-19

APRIL18B VAIMIN : April Challenge 2018 Division 2 - Vaibhav and Ministers

DP MOD てこずった組合せ CodeChef

問題リンク
https://www.codechef.com/APRIL18B/problems/VAIMIN

概要

組合せをO(1) で求められるように前計算をし、
障害点を考慮しながらゴールまでたどり着く経路の総数を求めます。
for 文DPで書き、 O( (p + q) log MOD + M^2 )

考察

経路について

reputation がcを下回らないように、(p, q) に移動したい、
ということを図にして表すと、「カタラン数」で出てくるような
経路の数え上げ問題になっていることが分かります。

サンプル1 の場合、
f:id:arukuka:20180418233959p:plain

c は無駄の要素なので、与えられる p, q
から cを引いておきます。
その場合のコーナーケースとして、
c だけ good deals している間にVaibhav が提示している
点が通過点にないかチェックする必要があります。

経路は(0, 0) から (p', q) where p' := p - c
までを計算しますが途中M個の障害点を考慮してなければなりません。
包除原理を考える必要がありますが、ある点から次のある点までの
経路数が常に同じであるため、再利用できます。
これで、スタート位置からゴールまでにの経路数の
「奇数個点を通過してゴールについた経路数」 - 「偶数個点を通過してゴールについた経路数」
を計算すれば答えになります（スタートは偶数:0個とする）。
点はあらかじめ何回行動したか（g + b）でソートしてあげます。
同じ座標上に2点存在する場合もありますがそれを経由しようとすると
組合せは0になるため、特に考える必要はありません。

ある点Xから（右側の）ある点Y に移動する総数は

f:id:arukuka:20180418235907p:plain

このように、負のreptationを許す経路数から
「反射」の考えでその余分な分を引くことで求められます。
（自分も完璧に理解できていませんが、詳しくは下記書籍を読んでください。
自分はこれのおかげでなんとかACまで持って来れました。

note7.hyuki.net

以上を踏まえて実装すると

Solution: 18236218 | CodeChef

となります。

2017-06-17

AOJ 2511 : 沈みゆく島

AOJ 競技プログラミング最小全域木 Union-Find 座標圧縮

Sinking islands | Aizu Online Judge

一番最初のサンプルケースを見ると、
沈む時刻が最後の方から最小全域木を構成していくと良さそう
（座圧して、時刻が同じものはグルーピングしておく）。

一番最初に沈むところまで終えて、
Union-Findが全部同じ親を持つかチェックして
ダメだったら0を出せばいいのかな。

しかしこれでは4番目のサンプルケースが合わない（金額が高くついてしまった）。
何故だ…。ふと普通に最小全域木にしたらコストはどうなるのだろうと思って
やってみたらサンプルと一致する。ホンマか。

図解してみる。

f:id:arukuka:20170617082237p:plain

えでもこれじゃあ時刻25で2の島が沈んだときに
島7-9にリンク張らないとまずいのでは？
と思ったけど、

この場合は，新たに橋を架けることで，まだ沈んでいない島々の間で移動経路が確保できるようにする．
どのように橋を架けても移動経路が確保できなくなった場合は，それ以上の橋の建設は行わない．

これは「全域木が構成できないと分かったらそれ以上リンクを張らない」ということだった。

そこで全域木を構成できない一番早い時刻を記録しておき、
そこまではあらかじめ一緒くたにして最小全域木を構成し、
そこから前に遡りながら島を追加し、最小全域木を構成することにした。

この操作は一般化できるので、

なお，現時点で既に移動経路を確保するように橋を架ける事が出来ない場合は，橋の建設は一切行わない．

これについて気にする必要はなくなる。

AC。

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

関数calが「全域木を構成できない一番早い時刻」のindexを返し、

      for (int i = 0; i < s; ++i) {
        List<Integer> comer = t.get(i);
        list.addAll(comer);
        added.addAll(comer);
      }

これが「あらかじめ一緒くたにして」いる操作になる
（降順に座圧してます）。
あとは後ろから最小全域木を構成している。

座標圧縮はソートで十分だとは思うけど、
こちらのほうが実装が楽に感じた。

あと少しで諦めて解説を見るところだった…。
しかしサンプルに助けられてしまったなあ。

2017-06-16

YQL で html を読み込む方法が変わった(html table is no longer supported.)

algon-320.hatenablog.com

id:algon-320 さんのウィジェットを使わせていただいて、
rating を取得していたのだけれど、ある日AtCoderのratingが
取得できなくなっていた。

返ってきたjsonを見てみると
html table is no longer supported. See https://policies.yahoo.com/us/en/yahoo/terms/product-atos/yql/index.htm for YQL Terms of Use
と出ていた。

その日ずっとドキュメントを見ていたが解決できず…。

今日もう一度調べてみたらStack Overflowが引っ掛かった。

stackoverflow.com

htmlstringというのを使うようになったらしい。

出力も色々変わったようなので新しい仕様に合わせて
rating取得部分を修正。

  function getAtCoderRating() {
    var userpage = 'https://atcoder.jp/user/' + handles['atcoder'];
    var yql = "select * from htmlstring where url='" + userpage + "' and xpath='//*[@id=\\'main-div\\']/div/div/div[2]/dl/dd[2]/span'&format=json&env=store://datatables.org/alltableswithkeys&callback=";
    var url = 'https://query.yahooapis.com/v1/public/yql?q=' + encodeURI(yql);
    $.ajax({
      type: 'GET',
      url: url,
      dataType: 'json',
      timeout: 10000,
      cache: false,
      success: function(json) {
        if(json['query']['results'] != null) {
          ratings['atcoder'] = Number($("span:eq(0)", "<div>" + JSON.stringify(json['query']['results']['result']) + "</div>").text());
          setHtml('atcoder');
        }
        else {
          setHtmlWithoutColor('atcoder');
        }
      },
      error: function() {
        setHtmlWithoutColor('atcoder');
      }
    });
  }

ちょっとjavascript慣れてなくてスマートな感じではないですが…。

これで色付けできるようになりました。

こういうの、ドキュメントのどこを調べると分かるのだろう…。
今回は「後でStack Overflowに出るでしょ」と思ったので放置したけど、
そうはいかない場面に出くわしたときに対処できるようになりたい。

2017-06-16

JOI 2012-2013 予選問題4 : 暑い日々 (Hot days)

JOI DP 競技プログラミング

JOI 2012-2013 予選問題４

D: 暑い日々 (Hot days) - 第１２回日本情報オリンピック予選（オンライン） | AtCoder

id:keidaroo さんのblogに触発されてどんなもんじゃろと解いてみました。
JOIの問題は解いたことがないので…。

keidaroo.hatenablog.com

解いてみる

今何日目かと前日何を着ていたかが分かれば
その中で最大化しても問題ないことが分かる
（前日より前に何を着ていたかは関係しないため）。
状態dn、遷移nのO(d n^2)DPを組む。

Submission #1356723 - 第１２回日本情報オリンピック予選（オンライン） | AtCoder

最初同じ服を連続して着てはいけないと誤読して
サンプル不一致になる。

なお、日については今と前にしか着目する必要はないので、
dpテーブルの次元は1つ減らせます（int dp[n], next[n]でいい）。

id:keidaroo さんのblogを読んで

解法が違う…。どうなっているんだ。

maxi[i] := 最高気温がiのときに着れる一番派手な服の派手さ
mini[i] := 最高気温がiのときに着れる一番派手でない服の派手さ
これで一日ごとに「最大」を取るか「最小」を取るかで遷移させていく
（再帰関数のmaiが0のとき最大を取って、1のとき最小を取っている）。
O(d)。

なるほどすごい…。
でもイマイチこれで最適解が求まる理由がよく分からない…。
中間の値を持っておいたほうが得するということはないのだろうか。

f:id:arukuka:20170616183212p:plain

・・・ウーン確かにどう動かしても、
差の絶対値なので☆のところを取ったほうが良いということはなさそう。

解説

JOI 2012-2013 予選問題４解説
 id:keidaroo さんの解き方が発展課題の方で、
私の方が愚直に解いたものになる。

解いてみて

今でこそ何とか解けるものの、
JOI予選のときに解けたものではないです
（私は高専2年のときPCK2011予選で0完、JOI2011-12予選未参加です）。

素直に、すごいなあと思うばかりです。

ポエムはできる限り避けたいですが

※はじめに言っておきますが、皆さんにとってはこの問題は楽勝だというのは知っているので、決してイキリとかそういう風に思わないでください。誰だって自分が解けなかった問題が解けるようになると嬉しいのです。（たとえどんなに簡単な問題であろうと）
暑い日々AC - keidaroo’s diary

こういう言葉を出させるコミュニティって非常に残念ですね。

同じ問題解いているお前はどうなんだという話もありますが（まあごもっとも）
競プロを始めたばかりの頃を回想したくて解いたので攻撃的な意味合いはないです。
不快に思ったら申し訳ないです。

2017-06-16

AOJ 2510 : 双子の読書感想文

AOJ 競技プログラミング DP 解説見た

Twin book report | Aizu Online Judge

DPだと思うけど大変そう。
最初rを2つ分けたときの大きいほうの最小値を求め、
余った時間に感想文を詰め込もうとしたが
無限にWAを重ねた。
半日頑張ってダメだったので諦めて解説を見る。

2013/Practice/模擬国内予選/講評 - ACM-ICPC Japanese Alumni Group

~~少し誤字~~

一番読むのに時間がかかる本をLとする

~~正しくは「一番読むのに時間がかかる本を $r_L$ とする」~~

誤字じゃなかった…。rって問題文に出てくるrのことか…。
日本語を勉強しましょうね…。

本当に？　と思ったけどなるほどなあ…。
考察が足りなかった。

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

ウーン悔しい。

2017-06-16

AOJ 2333 : 僕の友達は小さい

AOJ 競技プログラミング DP

My friends are small | Aizu Online Judge

DPだろうなということは目星がつく。
ただ

僕は、入れられる友達がまだ残っている限り、入れるのを止めない。決して止めない。

この条件を満たすようにするにはどうするか
を考える必要がある。

ここで、リュックに詰めなかった一番小さい友達を状態に持って置けば
最後に組み合わせを足すところで判定できそうということが分かる。
これを「wを昇順にソート」しておくことで、
「一番最初にskipしたのはいつか」に状態が変わり、扱うのが楽になる
（しなくても解けることには解ける）。

あとはDPを書けば良い。
O(n^2 W)だが、Time Limt:8 secなのでまず大丈夫だろう（最大ケースで2, 3秒くらい？）。

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

最初DPテーブルを
dp[何番目までの友達まで考慮したか(n + 1)][最初にskipしたのはいつか(n + 1)][容量(W + 1)]
としていてRE（メモリエラー）をもらってしまった。
一番最初の次元は今と次しか考慮しなくていいので、
削ることができる。

ただ書くのが面倒なので、メモリが危ないときだけにしたい。
普段からこちらを書いておく練習も必要そうだが…。

それにしても、始めたばかりの頃はDPは分からなかったし、
「1,000,000,007 で割った余りを出力せよ」なんて言われたら
まず解けないと思っていたのが思い出される。
進歩は遅いけど、成長はしているんだなあ。
少しうれしい。

2017-06-14

AOJ 1196 : 橋の撤去

競技プログラミング AOJ 木

橋の撤去 | Aizu Online Judge

ICPC諸島には島の数 n に対して n-1 個の橋があり，どの島から島へも，橋を何回か渡れば到達することができるようになっている．

つまり木になっている。

それが分かればあとはやるだけとなる。
すべての頂点（島）を根と見なして探索し、
・移動コストが一番大きな遷移（根まで戻りたくないので）、
・端っこ（橋を渡る必要がないので）
を考える。
すべての辺（橋）のコスト（長さ）を考えうる最大回数3でかけて足し、
「大きな遷移」を引き、「端っこ」につながる辺のコスト x2で引けばよい。

例えばSample Inputの2番目のケースを島1を根して考えると、

f:id:arukuka:20170614180905p:plain

最大の遷移（端っこは含めないことに注意）30と端っこの辺のコスト x2 = 12
を全体の合計 x3 = 196から引くと、
196 - 30 - 12 = 156
となる。なおこれは最小ではなく、島5か8を根にして考えたものが最小となる。

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