1090 In the army now

問題:

数の列が与えられる. その列は昇順に並んでいるものを期待する. もし, 前に大きな値が存在した場合は, その個数だけjumpするとする. 問題は, 列の長さが10000と大きいこと.

基本解法:

単純なソートを行うことでカウントすることができるのだけれども, O(n^2)のアルゴリズムではTime Limit Exceedになってしまう.

解法:

そこで, より高速なアルゴリズムを使って, カウントすれば良い.

(松崎の解法) マージソートを使って計算を行った. ソースは後で乗せようかと.

1091 Tmutarakan exams

問題:

N以下の数から, K個を選んでその最大公約数が1でないものを求めたい. このような組み合わせの個数を求める問題.

基本解法:

ある数xの倍数の中から選べば最大公約数は1とはならない. サンプルに含まれる, N=10, K=3だとすると,

  1. x=2の場合: 2,4,6,8,10 より, 5C3 = 10
  2. x=3の場合: 3,6,9 より, 3C3 = 1 合計で, 11となる.

解法:

難しいのは, xが素数でない場合であろう.

  1. x=4=2*2の場合: その組み合わせはすでにx=2の場合に数えられている.
  2. x=6=2*3の場合: その組み合わせはx=2とx=3の場合で数えられている. したがって, x=6の場合はの数を引かなければならない.

さらに, x=30=2*3*5の場合: 引きすぎなので, これは足す.

これをうまくまとめれば, とても簡単な問題になります.

1095 Nikifor-3

問題:

1,2,3,4が必ず含まれるような10進数が与えられたときに, その順列のなかで, 7で割れるようなものがあればそれを求める問題.

基本解法:

なぜ 1,2,3,4? --> この順列の10進数に対して, 7で割るとすべての余りが出現.

解法:

1,2,3,4についてはそれぞれ一つを抜きだし, 別に(最後に)考える. 0については, 前にあるとまずいので, 最後に全部くっつける.

それ以外の並べかたは? --> 実は適当でOK. 例えば, 5,3が残っているのなら, まず, 53 % 7 = 4. 1から4の順列を後につけるので,

 全体の余り = ( 4 * 10000 % 7 ) + ( 1 から 4 の順列 % 7 )
            = 2 + ( 1 から 4 の順列 % 7 )

となる. 上の第二項は好きに選べるのだから, 5にしてしまえば7の倍数になる. 5になるような順列は 1324. よって,

  5,3 + 1,3,2,4

と順に出力. (+は見やすくするために追加)


Last-modified: 2009-11-06 (金) 13:25:51 (3426d)