AOJ 2511 : 沈みゆく島

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);
      }

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

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


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

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に出るでしょ」と思ったので放置したけど、
そうはいかない場面に出くわしたときに対処できるようになりたい。

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

JOI 2012-2013 予選 問題4

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

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

keidaroo.hatenablog.com

解いてみる

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

Submission #1356723 - 第12回日本情報オリンピック 予選(オンライン) | 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 予選 問題4 解説
id:keidaroo さんの解き方が発展課題の方で、
私の方が愚直に解いたものになる。

解いてみて

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

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

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

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

暑い日々AC - keidaroo’s diary

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

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

AOJ 2510 : 双子の読書感想文

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

ウーン悔しい。

AOJ 2333 : 僕の友達は小さい

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 で割った余りを出力せよ」なんて言われたら
まず解けないと思っていたのが思い出される。
進歩は遅いけど、成長はしているんだなあ。
少しうれしい。

AOJ 1196 : 橋の撤去

橋の撤去 | 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

AOJ 1145 : 全宇宙生命ゲノムデータベース

The Genome Database of All Space Life | Aizu Online Judge

構文解析の問題。
一つ困るのが繰り返しの処理。

繰り返したときの文字列の長さを持っておいて、
それよりiが小さければ中の長さでmodを取って遷移し、
そうでないときはiから文字列の長さを引いて
次の文字列を見ていく。

f:id:arukuka:20170614051922p:plain
サンプルの3番目のケース。
例えばi < 28ならi' = i % 14(一つ下の階層の長さ)とする。
サンプルでは28 <= iなのでi'=i-28をし、
i' < 10(Cの繰り返し)なのでi'' = i' % 1(Cの長さ)とする。

最大ケースについて、
sとして100文字与えられ、繰り返しの最大は1000ということなので、
最大 999^(100/5) ~= 10^60 くらいになる。
BigInteger を使うという手もあるかもしれないが、
スマートではない。

i に注目すると最大でも 10^6 までしか与えられないことが分かる。
i より大きい数でmodを取っても結果は i なので繰り返した文字列の長さが
10^9を超えたら「超えましたフラグ(sourceではoverに該当)」を
立てておいて、その間は無視すれば良い。
なぜ10^9にしたかというと、iの最大10^6 x 繰り返しの最大 10^3 なので
それぐらいにしておけば十分だと思ったため。

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

書き方が悪かったのか、処理がだいぶ面倒だった。
どうすればきれいになるか……。