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だとすると,
解法: †難しいのは, xが素数でない場合であろう.
さらに, 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 と順に出力. (+は見やすくするために追加) |
