AtCoder Regular Contest #011に参加してみた

Java Contest ARC

久々のプロコン！

A - 鉛筆リサイクルの新技術

そのまま実装すればOK。10分くらい。
ソースコード

B - ルイス・キャロルの記憶術

Bにはめずらしくこれも基本的に実装するだけ。終わった時点で30分くらい経過。
ソースコード

C - ダブレット

ある単語first、lastとN個の単語リストが与えられる。1文字ずつfirstから1文字ずつ変えて単語リストの文字を経由してlastにたどり着くまでの過程を調べる問題。

前に似てる問題がDPで使われているのを見たことがあるのでDPかと思いきや単語数が1000。とても状態数を保持できない。
一応BFSで行けるのかなあと思って実装。経路1→7→5をStringで"1 7 5"で保存するという駄目そうな実装で、WA + TLE。全然だめでした。

終了後に他の人のコードを参考に再実装。重要な点は2つで、
1. 一度調べた単語を2度と調べる必要は無い（あとでまた調べるのは冗長）。
2. 経路の覚え方は前から覚えておくのは大変だが、後ろから覚えれば簡単。

データ構造をやけに豊富に使いました。集合はHashSet、キューはLinkedList、スタックはStackです。
ソースコード。


2問解けたのでまあまあ満足な回でした。でも3問目は頑張れば出来る問題だったなあ。惜しいことをした。順位は99位(2問)。次回も100位以内を目指します。