りふれろぐ

メモみたいな

ACM-ICPC2018 アジア地区横浜大会 参加記

この記事はUEC Advent Calendar 2018の11日目の記事です。

このタイミングでどうしても書きたかったところをアドベントカレンダー作成者である id:puman03 さんに色々手配していただきました。深謝いたします。

宣伝

いきなり宣伝かよって感じですね。主に学部1～2年生あたりを対象にした内容なので、ぜひ読んでみてください。

情報工学工房

カレンダー経由でこの記事を読む各位の多くは電通大生だと思いますが、電通大に「情報工学工房」という授業があるのをご存知ですか？

FrontPage - 情報工学工房2018 連絡Wiki

この科目は誰でも履修することができる通年2単位の科目で、1類の人には専門科目(選択)、それ以外の人には共通単位として扱われます。

プログラミング等の活動をしてみたいけどキッカケが欲しい人、大学や教員のサポートを受けながら制作活動がしてみたい人、たまたまやりたかったテーマがあって単位がついでに欲しい人とかには向いてると思います。逆に、特にやりたいことが明確でない人や1年間続けられる気がしない人にはあまり向いていないかもしれません。

毎年テーマが変わるので、少しでも興味がある人は4月にあるガイダンスに出席してみてはどうでしょうか。

競技プログラミング

情報工学工房のテーマの一つに、「競技プログラミング」というものがあります。

競技プログラミング(通称:競プロ)とは、与えられた問題*1に対して正しい答えを出力するプログラムを速く書く、という競技*2です。

AtCoderというサイトは頻繁に初心者向けコンテストが行われているほか、初心者向けの記事や問題集・過去問なども存在します。コンテストの過去問はいつでも解くことができます。ゲーム感覚で基本的なプログラミングスキルを学ぶことができるので、学部1年生や2年生あたりにぜひやってほしいです。

beta.atcoder.jp

ICPC

情報工学工房のテーマ「競技プログラミング」では、国際大学対抗プログラミングコンテスト(ICPC) の国内予選に参加します。

ICPCは、同じ大学の学生3人からなるチームを作り、協力して問題を解く形式のコンテストです。毎年6～7月に国内予選が行われ、上位チームはアジア地区予選に選抜されます。

AtCoderに最近手を出してる皆さんには、ぜひ来年のICPCにも参加してほしいなあと思っています。情報工学工房を経由せずとも参加できるので、その場合には3人チームを構成したのち私まで連絡いただければ手配します。

ICPC2018 アジア地区横浜大会 参加記

ここからは、2018年12月8～10日に行われた ACM-ICPC2018 アジア地区横浜大会 の参加記となります。何も考えずにだらだら書いた雑な感想文なのですごく読みづらいです。ご了承ください。

国内予選の参加記はこちら。

reflection4.hatenablog.com

メンバー

  • 私: 主に考察担当。ざっくり問題を読んで方針を考える。プログラムを書くのは遅い。
  • はと: 主にデバッグ担当。3人の中ではバグを発見するのが上手い方。
  • ばぐ: 主にコーディング担当。タイピングは速い*3がバグを埋めることが多い。

前日まで

チーム練習とかをやっておくべきだとは思ったが、結局1回もできなかった。

1日目: リハーサルとチーム紹介

昼前に大学で合流して会場に向かった。横浜は遠かった。

会場に着いてからは、コンテストの注意点等の説明を聞き、その後リハーサルを行った。
A問題とB問題は何事もなく解くことができたがC問題とD問題は解くことができなかった。

チーム紹介では、ばぐ君がこの日に電通大が100周年を迎えたことを英語で喋ってくれた。

2日目: コンテスト当日

朝5時半に起きて7時に駅で合流し、会場に向かった。とにかく眠かった。

9時半からコンテストが始まった。


ばぐ君にコーディングの準備をしてもらいつつA問題を見てもらうことにし、その間に私がB問題、はと君がC問題を読むことにした。

ばぐ君にAの実装を任せたが、本人が問題の内容や言語の挙動を勘違いしていた。正しく解ける方針を伝えたところ、苦戦しながらもなんとかAC。ここまでで33分。

B問題に取り掛かろうとしたが、すぐ思いつく単純な実装を試してもらったところ制限時間を超えてしまったため、後回しにした。

C問題は単純なシミュレーションをすれば自明に解けるが、こちらも制限時間を超えそうだった。少しした後にはと氏がいい感じの解法を思いついてくれたので、それを私が単純な計算式に置き換え、ばぐ氏に伝えて実装してもらった。1時間4分の時点でAC。

ここでB問題に戻ることにした。ばぐ氏が適当な枝刈りを提案したので、試しに実装してもらったところACした。ここまでで1時間51分。

ばぐ氏にD問題を、はと氏にG問題*4をお願いし、私はE問題を読むことにした。

まずG問題について、転倒数が関わってそうという考察が出たので、適当な方針を伝えて実装してもらったが、サンプル入力に対して正しい出力をせず、方針が正しくないことが判明した。

次にD問題に着手しようとした。ばぐ君がグラフを用いたアイデアを思いついたので、私が構造を定義して実装したが、サンプル入力が通らなかった。適当なアルゴリズムを考えたので、それに起因するものだと推測してバグ探しを始めたが、アルゴリズムではなく最初のアイデアが本質的に正しくなかったことに最後の最後まで気づかず、無駄に時間を使ってしまった。

途中でH問題を見たはと君が内容のシンプルさに気づき、試しに触ってみることになった。適当な全順序を見つければ4彩色できるのでは？と思い雑な実装を試そうとしてみる。ばぐ君にコーディングを丸投げし、適当な出力を吐くプログラムを投げてみたら当然のようにWA。次にグラフの形状の制約を利用した実装を試してみたがこれもWA。そりゃそうだ。

そうこうしてるうちに14時半になり、コンテストが終わってしまった。

結果

3問解いて60チーム中39位でした。最低限の目標としていた3問はなんとか解くことができた。
しかし、G問題を難しく考えすぎたせいで解けなかった点は悔しかった。

3日目: 企業見学

3社ほど企業見学させていただいた。まだ就活を始めていない私もそろそろなんとかしないといけないなあと感じた。

おわりに

長々と駄文を垂れ流してしまい申し訳ございませんでした。
電通大の方で少しでも競プロに興味を持ってもらえる人、ICPCに参加してくれる人が増えてくれれば幸いです。


明日は a_hollow1125 さんの「自作行列簡約化ツール」だそうです。4年前には私も同じようなことをやったなあと昔を思い出しました。

*1:1類の人は情報領域演習のプログラミングの問題をイメージするとよいです。

*2:競プロを新手のネトゲだと言う人もいますが、だいたいあってると思います。

*3:国内予選では最初の問題を日本一早く解いた張本人である。

*4:A,B,Cの次に多く解かれていたのがGだったので簡単そうだと判断した。

Java9: Set.ofとCollections.unmodifiableSetの違い

しばらくJavaを書いてなかったのだが、最近必要な場面が出てきてしまった。
いつの間にかJava9どころかJava10が出ていて、色々と新しい機能が追加されているらしい。

変更不可能な Set が必要になったので、新しい知識のない私は次のコードを書いた。

Object[] objects;
/* 略 */
Set<Object> set = Collections.unmodifiableSet(new HashSet<>(Arrays.asList(objects)));

ところが、Java9において、引数に要素を与えると変更不可能な Set を返してくれるメソッド Set.of(E...) が追加されていたらしい。これを用いるとコードは以下のようになる。

Object[] objects;
/* 略 */
Set<Object> set = Set.of(objects);

めっちゃシンプル。わかりやすい。

パフォーマンスについてはどうなのだろうか。気になったので実装を調べたり、実験を行ったりしてみた。

実装

Collections.unmodifiableSet は、引数の Set をラップし、変更を加えるメソッドを使用できないようにしたものである*1。探索等の性能は引数に与えられた Set の実装に依存する。
今回のコードで引数に与えた HashSet は、内部的に HashMap を用いている。HashMap はいわゆるハッシュテーブルであり、ハッシュ値の衝突時処理は連鎖法である。

一方で、Set.of で返されるのは java.util.ImmutableCollections$AbstractImmutableSet の子クラスである。要素数によって異なるが、Java10では要素数が3以上であれば java.util.ImmutableCollections$SetN となるらしい。
このクラスもまたハッシュテーブルのような実装を行っているらしいが、HashSet と異なる点がいくつかある。

  • Map を使用していない。言い換えれば、キーのみを格納している。
  • 衝突処理は開番地法である。
  • 実装そのものの段階で変更不可能な Set となっている

パフォーマンスに関わる部分での違いは、衝突処理であろう。ハッシュ値が衝突するようなケースに対して、探索の性能はどのような違いを見せるだろうか。

実験

衝突が少ない場合

まず、衝突があまり起きない場合のパフォーマンスを調査する。

  • 要素の型となる適当なクラスを作成する。デフォルトではハッシュ値は Object クラスにおけるものを利用するため、おそらく衝突はあまり起きないだろう。
class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode();
	}
}
  • 要素が N 個含まれる Set を、Set.of と Collections.unmodifiableSet の両方で作成する。作成の時間をそれぞれ計測する。なお、含まれる要素は同じにしてある。
  • 各 Set で、Set に含まれる要素に対し、M 回探索を行い、全体の時間を計測する。探索に用いる要素は各 Set で同じにしてある。
  • 各 Set で、Set に含まれない要素に対しても M 回探索を行い、時間を計測する。

N=100000, M=1000000 において、結果は以下のようになった。探索時間については探索1回あたりの時間としてある。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 11 ms 71 ns/回 77 ns/回
unmodifiableSet 14 ms 109 ns/回 54 ns/回

Set.of を用いたほうが探索のの効率が良さそうに見える。含まれない要素を探索した場合には、Collections.unmodifiableSet の方が時間が短くなった。

衝突が頻繁に起きる場合

MyObject クラスの hashCode の実装を、以下のように変更し、有効長を16ビットに落とす。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode() & 0xffff;
	}
}

ほかの手順は同様であるが、M の値は変更してある。

N=100000, M=100000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 5699 ms 44016 ns/回 173851 ns/回
unmodifiableSet 11 ms 122 ns/回 117 ns/回

Set.of の構築時間と得られた Set の探索時間が圧倒的に長くなってしまった。特に要素が含まれていない場合の探索時間が極端に悪化している。

衝突がほぼ常に起きる場合

ハッシュ値の有効長を8ビットまで落としてみた。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return super.hashCode() & 0xff;
	}
}

N=100000, M=1000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 16589 ms 141861 ns/回 279651 ns/回
unmodifiableSet 451 ms 7859 ns/回 9816 ns/回

ここまでくるとどちらの場合でも探索時間は非常に長くなってしまう。それでもなお Collections.unmodifiableSet の方が短い。

hashCode を定数とした場合

極端な例として、hashCode が定数を返す場合も実験する。

class MyObject extends Object {
	@Override
	public int hashCode() {
		return 0;
	}
}

N=100000, M=1000 において、結果は以下のようになった。

実装 作成 探索(含まれる場合) 探索(含まれない場合)
Set.of 16208 ms 133914 ns/回 264429 ns/回
unmodifiableSet 105433 ms 1072630 ns/回 2360586 ns/回

ここまでくると、HashSetをベースにした unmodifiableSet は線形探索のようになる(と思われる)ため、Set.of の場合よりも(10倍くらい)時間がかかるようになってしまった。

まとめ

  • Set.of を用いると簡単に変更不可能な Set を作ることができる
  • hashCode は衝突しづらくなるように実装しよう
  • ハッシュ値が衝突しづらければ Set.of で作ったほうが速いし楽


ところで、キーが順序付けできる場合には TreeSet などをベースにして、変更不可能な SortedSet や NavigableSet を作ることもできる。Collections.unmodifiableSortedSet や Collections.unmodifiableNavigableSet を参照。このあたりのパフォーマンスは調べるのが面倒になった。

*1:引数に与えた Set を直接変更してしまえば、ラップされた変更不可能なはずの Set も変更されてしまう。このようなことがないよう注意しなければならない。

ICPC2018 国内予選 参加記

忙しかったので今更になるが、どうせなら残しておきたいので書くことにした。

2018年7月6日、ACM-ICPC 国際大学対抗プログラミングコンテスト(以下ICPC)の国内予選が行われた。
ACM-ICPC 2018 Asia Yokohama Regional

結果から述べると、弊チーム WArabimochi は5完12位で、アジア地区横浜大会に選抜された。めでたい。
国内予選結果 | ACM-ICPC 2018 Asia Yokohama Regional

チーム編成

私はICPCの参加は今回で5回目となり*1、来年からは参加権を失ってしまう。最後くらいはアジア地区予選に進出したかったため、できるだけ強い(というか実力の近い)チームを作ろうとした。

メンバー(チーム紹介より)
  • 私: ねこです よろしくおねがいします
  • はと: はとです バターロールが好きです
  • ばぐ: ばぐです ばぐをうめます

予選まで

とりあえず模擬国内予選に参加し、5完した。ばぐ氏の goto 文が輝いていた。

当日開始前

とりあえずタイピングが一番早いであろうばぐ氏にAを任せて、自分はBを読んで解法を考えることになった。

開始後

3分弱でBの解法が思いついたところで、なんかばぐ氏がAを通してた。どうやらFAらしい。


交代してもらってBのコードを書いたが、なんかバグった。
適当に配列の中身を出力してみたところ、配列のサイズが足りないことが発覚したため、適当にめっちゃ大きく取ったらACした。


その後、Cの内容を教えてもらい、ちょっと考察したら、約数の中で条件を満たすものを求めればいいことに気が付いた。
ばぐ氏に適当に実装してもらってAC。


D問題、制約を見た瞬間に全探索を提案。ただし{ 2^{36} }は厳しそうだったので、適当に枝刈りをすることにした。
私が再帰関数で実装したものの、なんかサンプルの出力すら合わない。原因を探ろうと関数内部でデバッグ出力を試みたところ、そもそも再帰呼び出しができてなかった。
原因がわからず、悩んでいたところ、はと氏からの指摘で、再帰関数呼び出しで関数名を書き忘れるというミス*2が発覚した。
適当に直してAC。


私がDを実装している間に、ばぐ氏とはと氏に問題を読んでもらっていたので、解けそうなFの実装をお願いすることにした。
彼らにFを任せつつ、私は彼らが飛ばしたE問題を読んでみることにした。

少し考えたら、精度が落ちない部分をまとめて足す方法を思いついたので、難航していたFの実装に代わって私がEを書くことに。
適当に実装して、サンプルを入力したところ、なにやら例外を吐いた。

私「浮動小数点例外ってなに？」
ばぐ氏「ゼロ除算」

思い当たる箇所があったので、修正したらなんかACした。


その後ばぐ氏とはと氏はFに取り組んでいたが、残り時間では解けなさそうだと判断したらしい。


終了時間ギリギリの時に、恒例行事としてH問題にEの解答を投げ*3、WAで終了。

終了後

学内1位だったのでまあ間違いなくアジア行けるだろうとなったので、打ち上げで無限に酒を飲んでた。
アイスワインが美味しかった。

さいごに

アジア地区大会もがんばります。よろしくお願いします。

*1:4年前、つまり初めての参加でもアジア地区予選に進出していた

*2:括弧の中に引数だけ並べると、コンマ演算子と解釈されてコンパイルが通るらしい。悲しい。

*3:去年の国内予選でばぐ氏とはと氏はこれをやった

甲州街道 新宿→調布

歩き

例のアレを歩きました。

経路はこちら。甲州街道をずっと真っ直ぐ。
甲州街道は車通りが多いからか、夜でも比較的明るく、安心して歩けますね。

出発が19時11分、到着が21時51分なので、所要時間は2時間40分でした。先ほどの地図だと3時間15分とか書いてありますが、それよりも早く着きました。

ただ、今回歩いてる途中に鞄の中に入れていたいろはす(もも味)のペットボトルが破れて、色々と悲惨なことになってしまいました…
それさえなければもうちょっと速く歩けた気がします…

またそのうち同じ経路で歩くと思います。2時間30分を目標にしておこうかな。

調布から小田原へ(2日目)

歩き

こんにちは。前日に続いて小田原まで歩いたことについて書きます。

2日目は本厚木駅から小田原駅まで。
経路についてはGoogleMapを参照ください。

で、この経路なのですが、最初に想定していたものから大幅に変更しております。詳しくは以下に…

本厚木駅から小田原厚木道路側道

ここまでは計画通りに進んでいました。歩きやすい道が多かったと思います。ただ、本厚木駅から国道246号へ向かう際には片側しか歩道がなかったりして、迂回を何度かさせられました。
しばらく小田原厚木道路の側道を歩いていると、いきなり歩道が無くなってしまい、このまま歩くのは危険と判断したため、再び国道246号方向へ戻ることにしました…

国道246号

さすがに国道だけあって、比較的歩道も広く安心して歩ける道でした。特に注意すべき点もなかった気がします。

東名高速道路側道

ここが一番苦しかったです…
この側道、交差点から東名の上を通る道が出てるかと思ったら、少し進んだら次の交差点で東名の下をくぐる道が出て… といった感じで、急な上り坂と下り坂が交互に現れます。
f:id:reflection4:20151013014139j:plain
f:id:reflection4:20151013014145j:plain
平面地図だけでは分からないことも多くあるということを認識させられました。

この辺りは坂道のあたりは歩道がありますが、それ以外の場所では歩道のないところが多いです。小田急線と交わる辺りは完全に歩道が無くなり、危険だと判断したので少し迂回しました。

秦野中井ICから県道71号

側道を抜けると広い道路、神奈川県道71号線に出ます。ここから二宮町を目指してひたすら南へ。本来のルートだと途中で西の方に入っていく予定だったのですが、山道を歩きたくないと強く感じたので、そのまままっすぐ進むことにしました。
この道路は全域で歩道があり、比較的安全に歩くことができました。
二宮町に入ってしばらくすると、調布民も御用達の大型スーパー、西友があります。経路短縮のためここで右折し、次の信号で左折。あとは道なりに進みました。
この辺りは交通量も多くなく、歩きやすかった気がします。途中トンネルもあり、歩いてて楽しかったです。

東海道

海の近くまで来ると、国道1号線、いわゆる東海道に出てきます。ここからはひたすら西に向かって進めば小田原駅の近くまで辿り着けます。
国道1号、東海道と聞いて期待していたのですが、予想していたよりも道幅が狭くて少しがっかりでした。まあ高速道路とか充実してるし仕方ないのかな…
ただ、歩行者にとってはあまり困ることはなかったです。唯一注意すべきなのは片側の歩道が工事中で通れなかった箇所があったくらいですかね…
何回か橋を渡ったりして、ずっと道なりに進み、突き当ったところを右に曲がれば小田原駅。疲れました…


ということで、無事に調布から小田原まで歩くことに成功しました。
今日歩いた距離は約35キロ、出発が9:50で到着が16:44でした。ほぼ7時間歩き続けたことになりますね…
休憩時間や信号待ちを考慮せずに速度を計算してみると5km/h以上出てますね。まあいいんじゃないでしょうか。
前日と合計すると70キロ(寄り道含む)くらい歩きましたね、自分でもびっくりです。


とりあえずこんな感じですかね…
今度はどこに行こうか迷いますね。いい案があったら教えてください。以上。