オンサイトで未確認

ukuku09の活動記録。

ごどく部活動記録【海外遠征編】ACM-ICPC 2016 バンコク大会 参加記

初海外!初海外ですよ!!(ひきこもり並感

 

ということで、ごどく部の遠征も兼ねて、ICPCバンコク大会に参加してきました。

 

バンコクの黒板w」

「なんかそれすごく惜しい感じがする」

「はい。」

www.acm-icpc.eng.chula.ac.th

 

 

 

前置き

前回のごどく部活動記録にて、「競技プログラミング部から自主除名した」とか書きましたが、実はCODE FESTIVAL予選落ちしてからも、競技プログラミング部から除名することなく、ちゃんとバンコク大会に向けて練習をしていました。だから今回の海外遠征はごどく部としてではなく、競技プログラミング部として行ったわけです。

 

しかし!しかしですよ!!ごどく部設立以来、初めて部員が海外行き!!これはもう、ごどく部としても活動しないわけにはいかないじゃないですか!!

(そんなことはなくて、正直チームに迷惑なのでやるべきではない)

 

そういうわけで、今回もごどく部として参加記をまとめたいと思います。

 

0日目: 移動フェーズ

14時間くらいかけて会津からバンコクまで行きました。

 あと隣でごちうさ読んでる人がいた。酔ってた。

 

1日目: Opening Ceremony & Pre-Contest

レジってから開会式。前日の睡眠時間が2時間だったので、眠い以外の感情を失っていました。(眠いって感情?)

 

その後昼食を食べ、いざPre-Contest。

11月11日=ポッキーの日だったので、Pre-Contestはポッキー問題セット。……ただしポッキーはそこまで関係がない。

  • A - レンタル料Pで新しくショップを作る/すべてのショップのレンタル料をK上げる/最もレンタル料の低いショップを潰す の3種類のクエリを処理し、最終的に残ったショップのレンタル料の総和を求める
  • B - 1からNの区間からなる円環上で2人の人が追いかけっこをした時、2人が最初に同じマスに止まるまでにかかる時間を求める
  • C - バブルソートの交換回数
  • D - P個のポッキーを詰めるのに必要な箱の数を最小化

Cはバブルソートの交換回数やるだけだったのに、実装できなくて辛かったです。蟻本はちゃんと読まないとダメですよ?(戒め)

 

Pre-Contest後はホスト校のJDと一緒にハニトー食べたりしました。高校から日本語をやってるそうで日本語が流暢だった。……僕も6年以上英語をやっているはずなんだがなぁ。

 

2日目: In-Contest

僕はD,F,J,Lを読みました。あとIの実装をして嘘解法でACしました。

以下問題概要(あってるとは言ってない)↓

  • A - 知らない
  • B - 科目数と最高点が与えられるので、点数の組み合わせのありうるすべてのパターンにおける、点数と平均点の一致数を求める
  • C - 3次元空間の原点から出るビームを格子点上で検出できるので、検出数の最大を求める
  • D - 内部に格子点を含まない三角形ABCの2点A,Bが与えられるので、Cになりうる点をKか所列挙する
  • E - 重みつき木の2点がクエリで与えられるので、そのパス上の重みの中央値を求める
  • F - 辞書から文字列を消すゲームをする。辞書に新たに文字列を追加した時の勝者を求める
  • G - 範囲LからRの間の2進数で、'1'が連続しないbit列かつKで割り切れる数を数え上げる
  • H - 体力を回復させるが毒性のあるポーション(魔剤)を飲みすぎて死なないようにした時の、倒せるモンスターの数の最大数を求める
  • I - 根つき木を回転させて根を変えた時の、ある節における子孫の数を求める
  • J - N冊の本をX日間で印刷する時の最小コストを求める。ただし印刷は並列でできるものとトポロジカル順序があるものがある
  • K - 期待値が云々
  • L - 尋問で得たM個の位置関係から、Nか所の反乱軍の基地の位置を特定する

正確に知りたい人は最近パワーアップしたGoogle 翻訳にでも問題文を投げよう。

 

で、

肝心の(?)ごどく活動ですが、

  • Bを読もうとして挫折。チームメイトに投げる
  • Cで格子点を座標上の点と誤読。入出力からして誤読しているのは自明だったのでチームメイトに投げる
  • L(1回目)、英単語がわからなすぎて読めない
  • L(2回目)、Outputを読み飛ばし。座標上の点どうしが重なったらダメだと考える
  • IでLCA(嘘解法)を思いついて実装するも、実装が解法と食い違ってて無限にWAを生やす

……もうこれ救いようがないよね。本番でこれだもんね。

 

結果は3完25位。解説フェーズがなくて辛かった。

 

Lは一回捨てようとしたのですが、どうやら一番簡単な問題だったようなので、英和辞典を開いて再読。問題概要を伝えると解法プログラムにコンパイルしてくれるプロが通してくれました。

人々がIをあまりにも高速に解くので、クソ簡単なのかと思ったけど、解いてみたら普通に難しく感じたので、実力のなさを感じました。てか想定解は一体何なの?オイラーツアー?

 

3日目: 帰宅フェーズ

また14時間くらいかけてバンコクから帰宅。会津と東京は離れすぎなので、座標圧縮して欲しいです。

 

感想

き◯いろモザイクの劇場公開初日に行けなかったので残念でした。

「目標6完w」とか「誤読しないw」とか言ってたけど、全然解けなくて勉強不足&実力不足を感じました。一応座ってるだけの人にはならなかったのは良かったですが、蟻本くらい網羅しとけって感じ。

あと実装中に「ここはこうじゃない?」と言われると、思考停止で考えていた実装から変えてしまうのは、良くないなぁと思いました。そういうのは競プロに対して自信がないからやってしまうんだと思うので、もっと問題を解いて自信をつけたいです。

 

www.acm-icpc.eng.chula.ac.th