445.1

やめた方がいいんじゃないの？

275

N個の場所からのマンハッタン距離を考えるとき、K番目に近いものの最小値を求めよ、という問題。

座標が整数なので1/2刻みで全部調べればいいらしい。証明しないで使う気にはなれない...。

マンハッタン距離なので、各二点間の中心点とそれに45度の直線上の点を選ぶと、ある二点からの距離が等しいことになる。で、K番目のヤツを最小にするには、K番目のヤツを動かすと同じ長さのヤツでK-1番目以前のヤツの長さあが長くなってしまう。つまり、K番目のヤツを最小にするのはそれと等しい距離のヤツがどこかにいるはず。(ただしK=1の場合は違う。)先に述べたように、ある二点からの距離が等しいヤツはその二点の中心点とそれに45度をなす直線状にいるはず。で、実際に考慮すべき同じ距離にいる点が2個なら中心点だけで良くて、そうじゃない場合はP個の点のすべてから等距離になる点。45度傾いているという条件を使えば、直線の交点なので、可能な点は1/2刻みの点に必ず乗る。だから1/2刻みで全部調べればいい、ということか...。

550

Nビットの数を0から始めて、同じ数が出てこないように任意個の0もしくは1を反転させるという処理を行う。この処理に次の数が最小になるようにするという制約を加えたとき、最初のK回の処理で出てくる最大の値を答えよ、という問題。

2^K回目でようやくKビット目が立って云々...。みたいなのを想像した程度。何もやっていない。

1000

アルファベットの置換を用いた暗号を考える。元の文と暗号化の結果が与えられるので、可能な暗号パターンをすべて答えよ、という問題。大文字小文字は別で、自分と同じ文字(ケースは無視)になるような置換は使わないとする。

52ビットの元の文で使ったかどうかと、52ビットの暗号文で使ったかどうかを持っておいて、マッチングを追加していってその時何通り可能かを計算する。メモの効率を高めるために、状態の同一化をうまくやる。ある文字から別の文字へのマッチングは、同じ大文字小文字の使用状況の文字へのマッチングと同等とみなせるので、そこをうまく使う。つまり52ビットの中で、26ビットずれたところとの関係は保存しないといけないけれど、それ以外は自由にスワップして構わない。実装あるのみ...。

実際には52ビットで持って並びかえて、なんてしないで、これと同じ状態のがいくつあって、こういうマッチングは何パターンあって、結果どういう状態になって、みたいなのにうまく圧縮してやらないとダメみたい。