GCJに参加しているなう その2
Round 1Aについて。
今度はA,B,Cの三問。
前回と同じく、最後だけ解けなかった。
解けた問題だけとりあえず解説。
A
パスワード入力画面で、すでに何文字か打ったが、ある時点で間違ってしまったかもしれない。
これから何文字か削除して再開するか、それとも自分を信じて続けるか、あきらめて最初から打ち直すか、と3つの方法が考えられる。
キーを打ち込む期待値がもっとも少ない場合の期待値を出せ、というもの。
ちなみに、問題ではパスワードの長さ、打ち込んでしまった文字数、打ち込んでしまった各文字で間違えた確率、が与えられ、これ以降はすべて正しいパスワードを打つ仮定となっている。
相変わらずそんなに難しくなく、それぞれの場合で期待値を計算して、最小となるような場合の期待値を出せばいい。
何文字か削除する、というのが若干面倒ではあるけれど、5文字打ち込んで3文字削除する場合は、1,2文字目が正しい場合（削除した場所から再開したらパスワードが通る）とそうでない場合（再開したらパスワードが通らないので再度打ち直し）でそれぞれの確率を元に期待値を出せばいい。
あわてて書いたので（ある文字まで正しいとする）確率表を作ってしまったが、書いた後でいらないことに気づいた。
前から順にやっていけばぜんぜん問題ない。やれやれ。
でもメモリ消費量はたかが知れてるし、計算量も何も変わらないので、そのまま通した。
B
なんかゲームの問題。
いくつかの課題があって、それはある程度以上スターを持っていないと解けないものになっている。
課題はそれぞれ二つのステージがあって、いきなり二つ目からはじめてもいい。
一つ目のステージを初めてクリアするとスターが一つもらえ、二つ目のステージを初めてクリアするとスターが二つもらえる。
一つ目のステージをクリアしてから二つ目のステージをクリアすると、一つずつスターがもらえる。（逆にやっても無駄、一つの課題では二つまでしかスターがもらえない）
それぞれの課題、ステージでクリアに必要なスターの数が決まっているとすると、すべての課題の二つ目のステージをクリアするのに必要な回数は最低何回か、という問題。
ちなみに、どうしてもできない場合は無理、と出す。
冷静に考えるとそんなに難しくなく、次の順に考えればいい。
- 二つ目のステージのうち、クリアできるものがあればクリアする。その課題の一つ目のステージをクリアしていたらスター一つ追加、試行回数一つ追加。そうでなければスター二つ追加。
- 上がなかったら一つ目のステージのうち、クリアできるものを調べて（ただし二つ目のステージをクリアしたりすでに終わった課題をのぞく）、そのどれかをクリアする。ここが一番問題だが、「現時点で一つ目のステージはクリアでき、二つ目のステージがクリアできるのに必要なスターが一番多い」ものを選ぶとよい。
- 一つ目のステージすらクリアできなかったら、どうあがいても無理。
- スターの数が課題数×2になったら試行終了。
二番目がどう考えても面倒くさいが、要するに、「ほかのステージをクリアすればひょっとすると二つ目のステージをいきなりクリアできるかもしれない」という可能性を残すのが目的。
優先的に二つ目のステージをクリアするのは、一つ目のステージを飛ばすため、というものと、どうせいつかクリアしないといけないんだからクリアできるうちにしておく、という二つの戦略に基づく。
ちなみに、largeは多量の「無理」が出て結構あせった。
結果的には正しかったようだが・・・
Cは無理だった。いじればいじるほどSampleどおりにならないという鬼みたいな感じだったが、もう途中であきらめた。
まあ、結果的には600位を切る程度の順位だったのでよしとしよう。
シャツは遠い。
