私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「トーナメントでの想定対戦数は?」(CodeIQ)を参照してください。
いよいよ夏の甲子園が始まります。
このような大会で用いられるのがトーナメント表です。
勝ち進んだことを想定し、どの投手をどの試合で使うのか検討することは珍しくありません。
今回はトーナメントにおける各チームの想定対戦数に注目します。
例えば、4チームでトーナメントを行うとき、トーナメント表の形として、以下のような形が考えられます。
このとき、各チームが決勝戦まで勝ち進んだときの対戦数は、それぞれ図の括弧内に書いた数字のようになります。
この想定対戦数の合計を考えると、左側の形は8、右側の形は9になります。
同様に、n チームでトーナメントを行うとき、この合計が最小になる形と最大になるような、トーナメント表の形を求めることにします。
標準入力から n が与えられたとき、考えられるトーナメント表の形について、想定対戦数の合計の「最小値」と「最大値」を標準出力にスペース区切りで出力してください。
なお、n は500以下の正の整数とします。
例えば、 n = 4 のとき、最小値は8、最大値は9ですので、以下のように出力します。
【入出力サンプル】
標準入力
4
標準出力
8 9
Rubyで解答しています。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #!/usr/bin/ruby def getMax(n) return (n- 1 ) + n*(n- 1 )/ 2 end def getMin(n) q = n a = 0 loop{ q = q / 2 break if q == 0 a += 1 } b = n - 2 **a c = (n- 2 *b) return c*a + 2 *b*(a+ 1 ) end # main while line = gets line.strip! next if line.empty? mx = getMax(line.to_i) mn = getMin(line.to_i) printf( "%d %d\n" , mn, mx) end |
入力値を数値にしてgetMax()、getMin()に渡し、結果を得ます。
それぞれの結果を印字します。
考え方の通りに結果を計算します。
考え方の通りに結果を計算します。
log2nを計算してもよかったのですが浮動小数点が嫌だったのでループで計算しました。対数時間なので大したことにはなりません。
直感的に最大、最小のトーナメント表の形はわかりますが、どうやって証明すればいいんでしょう?