ICPC 国内予選 2017 参加記

できるだけポエティックにならないように気を付けます…
(が自分視点で展開しており十分ポエム)。
思うところは色々ありますが今までの日々は味のあるものだったので
日記として残しておきたいと思いました。
書いたあと見直しましたが酷いです。自戒。

概要

チームSoleilとして Ut.kさんとこいしさんと一緒に
ICPC国内予選2017に参加しました。

結果は391チーム中37位で予選通過になったと思います。

新学期頃から今までのことについて振り返ります。

前前前菜

新学期・チーム編成

学校のコンピュータクラブというサークルに所属しています。
一部中の一部が競プロを楽しんでいます。

今年は競プロをやりたい! という新入生が多くて
まずはICPCで頑張りましょうか! という話になりました。

チームは3チーム出る予定でしたが
休めない実験が被った方がいたりで2チームで出ることに。

自分は

  • 2チームのうちどちらか一方が予選を通過できるように
  • 組みたいなと思った選手と自分がチームを組めるように
  • ***(アレすぎて書けない)

を満たすようにチームを組みました。

今思えばこの頃から精神がおかしかったのですが
練習の邪魔だと当時感じた選手をslackのチャンネルからkickしたりしました…。
ここに懺悔します
(彼は当日弊学のチームを応援してくださっており
大変人ができた方だなと思いました)。

練習

ABC早解きの朝練(平日毎日)を過去2年間やっていたのですが
大変不評だったので廃止することに。

火曜日と木曜日にAOJ-ICPCから問題を選んで解いてしました(ABCDを選ぶ)。
あとはyukicoderに出たりAtCoderに出たり。
自分にとって今までにないほどわいわいできており楽しかったです。
また、JAGの模擬国内予選以外にも2回チーム練習として模擬戦を実施しました。

なお、たぬたろう さんにコーチをお願いして
木曜日・模擬戦の問題の選定と模擬戦・本番の会場整備等をお願いしました。
おかげ様で選手が練習に専念できました。ありがとうございます!

5月末~本番

私事で恐縮ですが自分は持前のうつ病が悪化して実家休養することに相成りました。
模擬戦、模擬国内予選~予選当日だけ学校に戻りました。
実家からも問題を解いていましたがダウンしていたときは何もできず。

他の選手もレポートや研究が忙しかったりで参加率が減少していきました。

模擬国内予選の日、チームメンバーが揃ったので
観戦サイト用に集合写真を撮ったのですが
今年は掲載する場所がなくて残念だったです…。

当日ちょい前の自分

7月に入ってから毎日嗚咽との闘いでしたが
国内予選前日、散歩中にげーげーしてしまったので
薬局で対ストレス用胃腸薬(漢方)を買いました。
あとはカフェインの錠剤(トメルミン)を買ったりユンケルを買ったりして
当日に備えました。

あとは…神社にお参りしてました…。

当日

前前菜

夢でボロ負けする夢を見て飛び起きたあと、
再び寝てボロ勝ち(なんと10位! ありえね~)する夢を見て
げんなりしました。まだICPC終わってないんかい…。

前菜

こいしさんと連絡が取れたのでお昼ご飯はゲン担ぎにかつ丼を食べました。

その後ライブラリを印刷したり共有のお菓子・飲み物を買って会場入り。
諸事情により選手のほとんどはリハーサルを満足にこなせなかった。

リハーサル終了から本番開始までは各位好きなように過ごしていたと思います。
世間話をしたり、デレステのMVを見たり、休んでいたり。
自分は緊張でそれどころではなかったのですが、そういう人々を見て和みました。

諸注意として提出ミスに気を付けること、TLEがないことについてアナウンスしました。
実行時間がかかるプログラムに応援コールがしたいねと談笑し
Pらでペンライトを持ってこなかったことを後悔しました。
が、これは電子的な準備になってしまうのだろうか…。

本番

5分前でもサイトにアクセスできて
「(開始直前はアクセスできないようになってなかったっけ)」
「(去年はどうだったっけ)」
「(まさかこどふぉる…?)」
と思っていましたが本当に開始直前ロードが長くなり
SSレアの気配を感じてコンテスト開始。

戦略というほどでもないですが
各問題は複数人で見て解けそうな人が名乗り出て
実装する、という方針を取っています。
固定すると苦手な問題でアになったりすると思ったので…。

A問題はこいしさんが瞬間的に解法を生やして実装・AC。
B問題は難しそうに見えましたがUt.kさんが「解けます」と
一言放って華麗にAC。C問題はびっくりするほどやるだけでしたが
外側と内側のmin, maxを取るのをバグらせそう…と心配していたら
こいしさんが自信マンマンに「簡単」と言ってくれたので
お任せしました(投げっぱなしでドン引きされたような気がしますが…)。

D問題、2^500になっちゃうよなー間に合わないよなー。
このn \times m \leq 500という制約はどう活かせるのだろう、
と考えていましたがこいし君と実は状態数少ないのではないか、
という話をしたことから、直感と独断でDの純粋な幅優先解法を書きました。

サンプルは(もちろん)合ったので入力ケースをダウンロードして実行。
1秒経っても終了せず「だよねー笑」と顔を見合わせた瞬間に終了。
えっ提出するよ…? → Correct Answer(これ赤字なのでWAに見える)
んほお。

2ケース目をダウンロードして実行。
3秒経っても終了せず、あれーやっぱりダメか1ケース目弱すぎたのかな
と考えていたら終わる。
えっ提出するよ…? → Conglaturations!
チームメイト一同「はあ?!」

Eは全列挙して試しても間に合うと考えたので実装。
時間がかかり過ぎたので自明な枝刈をして
実行。
1行入力ごとに1秒程度かかって全体で192ケースほど…。
このとき終了15分前だったのでプログラムを信じて応援コールをしていました
\ハーイハーイハイハイハイハイ!/
ペンライト欲しかった…。

結果むなしくもWA。
終わった後に気づきましたが自明な枝刈をしようとして
自明なバグを埋め込んでました…。スミマセン…。

コンテスト終了。

終了後

予選通過できたようでうれしかったですが
D問題を考察せずに解けてしまったのが非常に不快でした。
終わってみれば確かに状態数は少ないのが分かったのですが…。

個人的に応援していたチームは成績が揮わなかったようで、
D問題に対するヘイトを勝手に湧かしています。
やるせない…。

今回チームメイトのおかげで良い結果を残せました。ありがとう!
チームメイトとはアジア地区を楽しめるように精進していきたいと思います。

コーチにはささやかなお礼として好きだと伺っていた
ぼのぼののぬいぐるみをプレゼントしました。

最後に、チーム戦は楽しいですね…。

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