天下一プログラマー

天下一プログラマーコンテストが開催されている。どれどれ、ちょっと参加してみようかな。って、応募資格は学生さんのみ。残念。
予選第一回の問題が http://lab.klab.org/young/2009/07/%E5%A4%A9%E4%B8%8B%E4%B8%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9E2009-web%E4%BA%88%E9%81%B8%E7%AC%AC1%E5%9B%9E%E6%A6%82%E6%B3%81/ に掲載されていたので、外野ながら挑戦してみた。言語は Ruby を選択。

第1問

1. グレゴリオ暦では1年の平均日数は365.2425日というのを用いて、2001年から3000年までの日数を求める。
2. 日曜日は2001年1月1日から数えて7日目なので、1 で求めた日数そのままを7で割る。

year = (3000 - 2001) + 1
day  = (year * 365.2425).to_i
puts day / 7

第2問

どうやって4文字の文字列を抽出するかが問題で、その他は特に問題ないと思う。ここでは、String#[first..last] で実装した。

str = "87104101110321051103211610410132991111171141151013211110232104117109971103210111810111011611544321051163298101991111091011153211010199101115115971141213210211111432111110101321121011111121081013211611132100105115115111108118101321161041013211211110810511610599971083298971101001153211910410599104321049711810132991111101101019911610110032116104101109321191051161043297110111116104101114443297110100321161113297115115117109101329710911111010332116104101321121111191011141153211110232116104101321019711411610444321161041013211510111297114971161013297110100321011131179710832115116971161051111103211611132119104105991043211610410132108971191153278971161171141013297110100327897116117114101115327111110032101110116105116108101321161041011094432973210010199101110116321141011151121019911632116111321161041013211111210511010511111011532111102321099711010710511010032114101113117105114101115321161049711632116104101121321151041111171081003210010199108971141013211610410132999711711510111532119104105991043210510911210110832116104101109321161113211610410132115101112971149711610511111046"

i = 0
x = 0
while i + 3 < str.size
    num = str[i..(i + 3)].to_i
    if num % 3 == 0
        x += 1
    end
    i += 1
end
puts x

第3問

この問題は解けなかった。いや、一応下に書いたコードで解けてるとは思うんだけど、計算量がものすごいので使い物にならない。問題を解く場合には、定石みたいなものがあると思うんだけど、わからなかったってことは勉強不足ってこと。うむ。

man   = 10000
money = [10000, 5000, 2000, 1000, 500, 100, 50, 10, 5, 1] # お金
max   = money.map { |m| man / m + 1 }                     # 最大何枚使用できるか
c = 0
# 10,000円
max[0].times { |y1|
    sum1 = y1 * money[0]
    if sum1 == man
        c += 1
        break
    end
    # 5,000円
    max[1].times { |y2|
        sum2 = sum1 + y2 * money[1]
        if sum2 == man
            c += 1
            break
        end 
       # 2,000円
        max[2].times { |y3|
            sum3 = sum2 + y3 * money[2]
            if sum3 == man
                c += 1
                break
            end 
           # 1,000円
            max[3].times { |y4|
                sum4 = sum3 + y4 * money[3]
                if sum4 == man
                    c += 1
                    break
                end 
               # 500円
                max[4].times { |y5|
                    sum5 = sum4 + y5 * money[4]
                    if sum5 == man
                        c += 1
                        break
                    end 
                    # 100円
                    max[5].times { |y6|
                        sum6 = sum5 + y6 * money[5]
                        if sum6 == man
                            c += 1
                            break
                        end 
                        # 50円
                        max[6].times { |y7|
                            sum7 = sum6 + y7 * money[6]
                            if sum7 == man
                                c += 1
                                break
                            end 
                            # 10円
                            max[7].times { |y8|
                                sum8 = sum7 + y8 * money[7]
                                if sum8 == man
                                    c += 1
                                    break
                                end 
                                # 5円
                                max[8].times { |y9|
                                   sum9 = sum8 + y9 * money[8]
                                   if sum9 == man
                                        c += 1
                                        break
                                    end 
                                    # 1円
                                    max[9].times { |y10|
                                       if sum9 + y10 * money[9] == man
                                            c += 1
                                            break
                                        end 
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
}
puts c