2007年12月

久々にやった．寝ぼけていた．500点問題の状態の取り方がおかしかった…

250点問題：単語の列をアンダースコア区切りできれいに指定幅に並べろと．端数分のアンダースコアを次の単語が小文字で始まるときに挿入するだけ．余り過ぎないように注意．

500点問題：部屋の回転つき迷路．状態空間を，現在位置と各行・各列の反転状態とにとれば，最大でも80万状態くらいしかない．後は普通に最短路を探索すりゃ終わる．でも状態のとり方を間違えて各行各列でなく全部を反転してた…．終了ちょっと前に間違いに気づいたけど直す時間なかった．

1000点問題：解の存在に必要な条件は最小公倍数だろうけど…　そこから先が面倒そう．よくわかりません．

問題読み間違えて 500点落とした．1000点は間に合わなかった．

250点：右方向にしか動けないナイトをチェス盤上でもっとも長く動かせと．ただし，四手以上動かす場合には四方向の動きを少なくとも一回ずつすべて使用すること．四手未満ならどんな組み合わせでもいい．盤面の高さが３以上で横幅が７以上なら　横幅－２　回動けてこれが最大．盤面が条件を満たさないなら面倒なのでDP．

500点：問題を読み間違えたけど作成するデッキ数の二分探索でおわる．指定数のデッキが作れるかどうかは，各カードに対してデッキ数に満たない分だけジョーカーを追加して，ジョーカーの使用枚数がデッキ数以下かどうかをチェックすればわかる．ショーカーの数がデッキ数以下ならジョーカーが重ならないので作成可能．

1000点：辺の小さいほうから順に，ひし形の短径の最大値と最小値を計算していくだけ．