190.1

個人的には結構好きなタイプのセットかも。

250

部分的に隠された文字列が与えられるので、候補の中から該当するものが一つに絞れる場合にはそれを答えよという問題。ただし、同じ文字が複数ある場合に、一部だけ隠されているということはない。

26文字のうち表示されている文字とされていない文字に分類して、表示されているものならば候補と一致して、そうでなければ隠されている、というフィルタをかければおしまい。

600

a*b=cという式が与えらる。それぞれの数字は6桁になるようになっており、任意の文字を書き換えて数式が成り立つように修正する。このとき修正する最小の文字数を答えよという問題。

可能なaとbを全部列挙して、積とcとの違いをカウントすれば、最小のものは求まる。ただし単純にやると時間が間に合わないので、適当に最適化しないといけない。積とcとの差をメモする。aとbの先頭の文字の修正はcの先頭の文字の修正と同値であるので修正しない。元の文字と同じになるような修正はちゃんとスキップする。というような最適化をやったら通った。

実際には下の方から桁を決定していくのが正しいやり方らしいけれど、他人のソースを読んでも何をやっているのか分からない...。

1000

平方数で割りきれない数のうちn番目のものを答えよという問題。

ある数がn番目であるかどうかをバイナリサーチすればおしまい。ある数が何番目なのかは自分より前に平方数で割り切れるものがいくつあるかをカウントすれば良い。平方数はいずれも互いに素になるように選択する。

平方数Aで割り切れるものはn/A個あり、平方数Bで割り切れるものはn/B個あるが、AとBで割り切れるものがn/A/B個あるので、その分のカウントを減らす。というのを全部の可能な平方数集合に対して行う。ちなみに最小の互いに素な平方数7個の積が範囲からはみ出すので、平方数集合は大きさ6まで考えるだけで良い。なので、カウントが0になるものを打ち切るように6重ループを回せば良く、時間的にはすぐ終わる。