問題の意味が全然わからなかったので、英文を紙に写経して、翻訳してから取り組んだ。ゆっくりでもいいからキッチリ理解して解いていきたい。英語克服すんぞー。 シミュレーション問題。 時計屋さんは一日に数個しか時計を直せない。繁盛している時は一日に…

米ドルのフォーマットを出力する問題。 入力はドル12345と、セント6で$12,345.06と出力する。 全然ストリームがワカンネェヨ。 #include <iomanip> #include <sstream> #include <string> using namespace std; class FormatAmt { public: static string amount(int dollers, int cents</string></sstream></iomanip>…

問題を理解するのにちと時間がかかった。12345があって、各数字に分割して、割り切れる数を数える。12345は5で割り切れる。4では割り切れない、3では割り切れる、2では割り切れない、1では割り切れる。なので、割り切れる数は3つ。 class DivisorDigits { pu…

シーザー暗号のデコード。エンコード(プラス側にシフト)は簡単なんだけど、デコードはマイナスが入るのでちとメンドイ。とりあえずエンコードの時と全く同じような形を作り出すことにした。 #include <string> using namespace std; #define foreach(type ,bind, ite</string>…

TopCoderの過去問を解いていくよ。 ヤッツィーの簡単バージョン。サイコロ5個振って出た目が{4, 2, 2, 5, 4}だったら、2が2個で4ポイント、4が2個で8ポイント、5が1個で5ポイント。4が2個で8ポイントが一番高い得点なので、8ポイントを出力する。 max_elemen…

Project Eulerやってたけど、70問目を超えると「全く解ける気がしない」。かといってACM/ICPCはムリっぽいし・・・と思って、TopCoderに登録してみた。200点問題ならサックリ解けそうな感じなので、しばらくTopCoderの過去問を解いていこうかと。 が。言語が…

かなり重かった。 Problem 72 - PukiWiki1/dとして、d オイラーの関数で簡単に。と思ったけど、100万までの全ての数について素因数分解したのと変わらない訳。 100万 * √100万 = 10億。 多く見積もって10億回。少なく見積もっても1億回くらい。時間計り忘れ…

ログインして問題を解かないと回答例がオープンしないのが残念だ。 Problem 5 - PukiWiki 2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり、そのような数字の中では最小の値である。では、1 から 20 までの整数全てで割り切れる数字の中で最小…

微妙。疲れてきたかも。Problem 73 - PukiWiki1/2と1/3の間にある真既約分数を求める。 真既約分数を求めるのがちとめんどかったので、全部見てしまった。 だいたい範囲を絞っておいて、 gcdしてみる。 だいたいなので、キッチリ範囲チェック。 今は反省して…

等差数列と素数の関係に関する問題。 Problem 49 - PukiWiki項差3330の等差数列1487, 4817, 8147は次の2つの変わった性質を持つ。 3つの項はそれぞれ素数である。 各桁は他の項の置換で表される。 もう一個4桁の中に同じ性質を持つものがあるらしい。 作戦と…

五角数に関する問題。 Problem 44 - PukiWiki2つの五角数の和と差を取って、五角数になるものを見つける。 五角数チェックは前に書いたのでコピッペで。2つの和と差は五角数キャッシュを持っておいて、キャッシュと比較してく事にする。 (define (problem44)…

ガンガンいくよ。 Problem 47 - PukiWiki連続する3つの数がそれぞれ3つの異なる素因数を持つものは、こんなんで、 644 = 2^2 × 7 × 23 645 = 3 × 5 × 43 646 = 2 × 17 × 19 連続する4つの数がそれぞれ4つの異なる素因数を持つものを答える。 2^2と2は異なる…

日本人50位になりました。数学なんてちんぷんかんぷんだった僕がここまで来れるとは思ってなかったっす。数学おもろいっす。後は英語・・・。 Problem 43 - PukiWikiまたまたPandigital数。こちらはちときつい。 0〜9までの順列出して全アタック。先頭のゼロ…

後で読み返してみたら、案外簡単だったり。Problem 38 - PukiWiki組合せ数が多いかと思ってたけど、そうでもなかった。1のだけの組合せは無い。と書いてあったのでほっと一安心。回答が9876...になっちゃうのでありえないか。 安心したところで範囲を考える…

ぜぃぜい。やっと解けた。Problem 32 - PukiWiki39 × 186 = 7254のように1から9が一回づつ現われる積の組合せを見つける。 積の組合せは 1桁 * 4桁 = 4桁 2桁 * 3桁 = 4桁 しかない。ということで、 1〜9の中から、1桁or2桁の順列を求める。 差集合を取って…

オイラーと同時代の数学者Christian Goldbachに関する問題。 Problem 46 - PukiWiki奇合成数25は、25 = 7 + 2 * 3^2のように、素数 + 2 * 平方数で表せる。という予想を打ち破れ。という問題。 ゴールドバッハの予想 - Wikipediaとはちょっと違うみたい。 ま…

前に作った素数判定が火を噴きそうだ。 Problem 50 - PukiWiki100万未満の素数を連続する素数の和で表したときに最長になる素数を答える問題。 まずは篩。 (define (make-sieve-of-eratothenes n) (letrec ((sieve (make-vector (quotient (+ n 1) 2) #t)) (…

はじめての非離散系？ Problem 102 - PukiWiki2次元にマッピングされた三角形が原点を含むかどうか判定する。 原点,点A,点Bのz方向の外積を取ってみて、全て同じ方向を向いてたら、含んでる。 ベクトルの話なんか忘れちゃったよ。必死でフルスクラッチ本読ん…

結構面白い。 Problem 85 - PukiWikix * yの枠があって、その中に入る長方形の組合せの数を求める。 1 * 1から順に組合せ数を求めてみると面白いルールが浮かび上がってくる。ルールは内緒。 で、そこからがちと面倒で、2,000,000に一番近い解をどうやって求…

翻訳無いけどやってみる。Problem 65 - Project Euler √2の連分数は、√2 = [1;(2)]と表せて、eの連分数表記は、e = [2; 1,2,1, 1,4,1, 1,6,1 , ... , 1,2k,1, ...]こんなんらしい。100項目の分子の数値の和を求める。 問題は長いけど、やることはシンプル。 …

なかなかうまく解けた。 Problem 62 - PukiWiki立方数の数字を入れ替えると、また立方数になっちゃう数を見つける。 41063625 (345^3)に対して、数字を入れ替えて探すと膨大な組合せが必要になってしまうので、ここは考え方を変えて、数字の占める数を保存し…

素数判定を使うことが多いProject Eulerなので、Problem 6,Problem 10の回答例を見ながら試し割りの高速化を図ります。 試し割り編 今までのアルゴリズムは、2以外の素数は奇数。というルールに基づき、3から3,5,7,9,11,13...と偶数で割ってみて√2まで割り切…

ハッカーのたのしみ読んでます。実はこの本、「解説が殆ど無い」。提示されているのは式のみ。後は自分で探るしかないのだ・・・メモメモ。 記号はCの演算子。=は等号。 & マスク。共通するビット以外をオフにする効果を持つ。 例:IPアドレス & サブネットマ…

こ・コレは・・・手に取った瞬間レジに向かってた。ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久出版社/メーカー: エスアイビーア…

連分数に関する問題。Problem 57 - PukiWiki連分数で√2を求めた時、分子と分母の桁数が違う時の数を数える。 連分数だけじゃ面白くないから、ちょっと変わった感じにしてるみたい。 分数の計算ではまった。 1回目 1 + 1/2 2回目 1 + 1/(2 + 1/2) = 1 + 2/5 3…

メモ化の威力に感動した。 Problem 76 - PukiWiki 100の和の組合せを求める。両替問題のヤバいバージョン。 ナイーブにやってみたら50で破綻した。 1だけの組合せになったら1種類と特殊化することで40秒で完了できるようになった。 同じ計算を何度もやってる…

久しぶりにキマッた。 Problem 69 - Project Euler翻訳無かったけど、オイラーの関数に関する問題。 オイラーの関数φ(n)は、nと互いに素な整数の個数を表す。例えば、φ(6) = {1,5} = 2 φ(10) = {1,3,7,9} = 4n/φ(n)とすれば、nのなかに互いに素な整数の割合…

もうちょいいこう。Problem 71 - PukiWiki100万以下の真既約分数を小さい順に並べて、3/7の左側に来る分数の分子を答える。 素直に並べたら、100万の2乗回はかかるのでムリっぽい。んじゃ、と思って3/7以下に絞ってみたけど、1000分割位で破綻。100万 * 40万…

落ち着いて範囲を考える。 Problem 63 - PukiWiki n乗してn桁になる数はいくつあるか。 ふむふむ。適当に計算してみる。 まず終端。10^1は2桁,10^2は3桁,10^3は4桁・・・となるので、10^nはn乗するとn+1桁。絶対に追いつかない。10以上は除外できる。 小さい…

回文数絡み。 Problem 55 - PukiWiki 349を反転させて足していくと349 + 943 = 1292,1292 + 2921 = 4213,4213 + 3124 = 7337回文数になるらしい。不思議だ。回文数にならないものをLychrel数と言うらしい。50回回しても回文数が見つからなければ、Lychrel数…