【AIZU ONLINE JUGDE】「バトンリレーゲーム/Baton Relay Game」を学習する


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

今回の問題は「バトンリレーゲーム/Baton Relay Game」というもの。

模範解答

以下、hs484さんのコードより。コメントアウトは、コボリが勝手に付け足しています。

学習

問題を見て、迷ったのは次の点。脱落したあと、その脱落者を含まないように次の数をカウントできるかどうか。自分だったら、

  • 「脱落したかどうか」の配列をつくって、カウントをすべきかどうか毎度処理する
  • 1回の操作ごとに配列を作り直す(脱落者を配列に入れないようにする)

の2つが浮かんだが、ベストには思えない。

おおまかな流れ

  1. 生徒のノードをつくる。生徒は、「自分の前後の生徒が何番か?」ということと「脱落していないか?」という情報をもつ
  2. 宣言された数に応じて、バトンを持つ生徒(cur)を動かしていく。
  3. 上の操作が完了したら、バトンを持つ生徒を脱落させ、その前後の生徒を関連づけさせる。
  4. 上記を繰り返し、最後に結果を出力

処理の負荷の大きさは自分の考えた方法と似ていた。「宣言された数だけ繰り返し処理をしないようにできれば」と思ったが、今回はこれがベストか。

ただ、ノードを作ってグラフとして処理する方法は考えられなかった。たしかに点と線で考えられる問題なのだから、グラフで考えるべきだよなあ。そうすれば、上のように前後の関連づけも簡単にできる。

for文の様々な書き方の種類

Javaを学んでいくと、「こんな書き方もできるんだ!」と感じることが増えるが、なかでもfor文はいろんなパターンがある。今回はイテレータを利用したfor文を使っていた。while文で処理してもいいだろう。

下の2つは参考サイト。
Javaで使えるfor文の種類いろいろ at HouseTect, JavaScriptな情報をあなたに
イテレータと拡張 for文 | じっくり学ぶ Java講座


コメントを残す

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

CAPTCHA