cafelier@SRM

SRM445

SRM | 02:11 |

SRM445 の成績・ソース (要ログイン) : WA/WA/- : 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL

550開く

• 『なんかグレイコードみたいな（違うけど）方式で0～k-1までカウントしたときの辞書順最大値を求めてね』
  • 正確には、1つカウントアップする時には 0の桁を複数個選んで1に変える or 1の桁を複数個選んで0に変える ができる
  • そうやってできるもののうち、前とかぶらない範囲で辞書順最小のものがカウントアップ後の数

• 最初グレイコードじゃね？と勘違いしてビット演算一発→答えが合いません

• 手で書いてみる
• 000->001->011->010->110 のように桁があがったステップの次は、最上位桁を残して他全て 0 にできる -> 100。それが常に最小
• なのでそういうやり方で作る方法を考えればいい
  • kを2進数表記して、
    • 最上位のビットが立ってるとこはそのまま残す
    • 残りの下位桁は再帰的に、0なら全ビット反転して11...11にしたものに対応するコード、0でないなら1引いたものに対応するコード

• というのでk番目のコードを返すように書いたらまだ答えが合いません
• 辞書順最大を求めろと書いてあります

• 微妙に修正して辞書順最大を求めるようにした
• サンプル通った
• まあ問題ないでしょう。submit

275開く

• 『50点ほど格子点に点がばらまかれてます。そいつらからのマンハッタン距離をsortしたときのk番目が最小になるような点の位置（というかそのk番目最小値）を求めてね』

• ぬぬぬ全然わからん
• ぬぬぬ
• ぬぬぬ

• kが1なら答えは常に0
• kが2なら、一番距離が近い2点の真ん中
• kが3なら……
• ぬぬぬ

• すごい悩む

• あー、kがなんであれ、最適解は常にどれかの2点の真ん中にあるような気がする
  • 真ん中でなければ、k番目に近い点の方向に少し動かしてもk番目性は変えずに短くできるはず
  • （※システムテスト曰く間違いらしい…）

• というコードを書いた。全点ペアの中点を候補として試してみる全探索
• サンプル通った
• まあ大丈夫でしょう

1000開く

• 『アルファベット52文字間の換字暗号（ただしa->aやa->AやA->aのような自分に戻る変換はない）の平文と暗号文が与えられます。平文からそういう暗号文がでてくるような暗号は何通りあるか"mod大きな数"で数えてね』

• 要は、平文-暗号文に対として現れている文字は固定されるので、現れていない部分の決め方は何通りか。
• とりあえず現れていない部分をカウントするコードを…

• さて
  • 単純に探索すると、未割り当ての文字の集合に対してそれぞれのパターン数をメモ化しながら数える
  • 2^52くらいメモ化しないといけないなー無理
• でも、全部の文字を区別する必要はないな
• 平文と暗号文に同じ回数ずつ現れてる文字は互いに区別しなくていい
  • 大文字小文字で2個まで現れうるから、
  • 平文と暗号文にそれぞれ0/1/2個現れてるかどうかで9通りにグループ分けすれば、グループ内のそれぞれは対等だから52文字全通り区別して数えるより速そう

• どっちかが0個のパターンは全部まとめていいかな。6通りにグループ分けすると、たぶん(26+6)C6 くらいしか個数のパターン無いのでメモ化探索でどうにか

• 書く。
  • すごい場合分けを手作業でやった探索コード書けた
  • あとはメモ化するだけ…
  • キーが6個組のメモ化表作るのに手間取ってるあたりでタイムアップ
  • むむむあと5分あれば…

撃墜タイム

• 550撃墜された！うそっ

感想

• 書き取り練習を敢行したい (http://shinh.skr.jp/m/?date=20081221#p01)
• 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL 1LL

• 550は1を1LLに変えたら通りました。これはひどい
• しかし難易度的には550どころか400でも良かった気がする

• さらに275もシステムテストで死亡
  • ううむ。中点だけだといけないのかな。中"点"だけじゃなくて2等分線全部で距離一定だから2等分線の交点は全て考えないといけないか。そうかも。