【AIZU ONLINE JUGDE】「ザ・スクエアーズ/The Squares」を学習する


AIZU ONLINE JUGDEというサイトで、諸先輩方のコードを拝見させてもらいながら勉強するエントリ。

今回の問題は「ザ・スクエアーズ/The Squares」というもの。

模範解答

以下、sawfishさんのコードより(前回と一緒だ! なんて人なんだ)。コメントアウトは、コボリが勝手に付け足しています。

学習

おおまかな流れ

  1. フィールドと避難者を設定する。向きを示す文字列の配列と、向きによる「次に進む方向」の配列をつくっておく
  2. まず、避難者それぞれについて、進行方向の確定をさせる。とりあえず「今向いている方向が進めるかどうか」から考え、それが無理なら問題文の通りに次案を検討していく
  3. 全員の進行方向が確定したら移動フェーズに入る。優先度(prio)を使いながら、同じ場所に避難者が着かないように移動させる。このとき、移動前の場所を床(避難者のいない場所)にしておくことを忘れずに
  4. それぞれの避難者について、非常口に立っていたら迷路から取り除く。
  5. まだ避難者が残っていれば、残った避難者だけで上記の処理を繰り返し行う。180秒(180カウント)したら強制的に終了。

優先度の処理の仕方

今回は、複数の避難者が同じ場所に移動する場合の対処に唸らされた。簡略すれば、それは「予約システム」のようなものだ。

方向付けが確定したとき、次に進むであろう場所に自分の向きを数値として入れておく。そうすると、2人目以降の数値が入るとき、どちらの数値(予約)を優先すべきか決められるわけだ。

最初は「まとめて処理すればいいのに」と思っていたが、ここの処理を理解して、方向付けと移動を分けて処理する大切さを理解した。

ArreyDeque

これまでArrayListとHashMapしかコレクションフレームワーク(コレクション=オブジェクトの集合を操作するために用意されたJava標準のAPI。今知った・笑)を使っていなかったが、ArrayDequeというのもあるようだ。

ArrayDequeは、両端キューとも呼ばれ、先頭末尾の双方から要素を出し入れできるキューの実装です。ArrayDequeを利用することで、キュー(FIFO:First In First Out)やスタック(LIFO:Last In First Out)といったデータ構造を表現できます。
ArrayDeque | Javaコード入門

アナロジーとして、ロケットペンシルのようなものか。真ん中の処理はできないが、1個ずつ取り出しつつ、目的の番が来たらそれを処理して、もう一度戻したり(あるいは捨てたり)できるイメージ。
メソッドは、offer()で末尾に登録し、poll()で先頭を取得and削除する。

今回の例では、これで避難者の脱出処理を上手に行うことができる。たとえば、5人いる中の2人目が脱出した場合、次の処理からは4人で行える。これはメモリの観点からも良いのかもしれない。

ちなみに、TreeMapという、勝手にソートしてくれるHashMapもあることを知った。便利そう。


コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA