Topcoder

SRM 403 DIV2

SRM 403 DIV2申し込んじゃった。10時からやります。目標は・・・1問突破!! 問題は 続きものの3問。ラッキーナンバーは4,7で、44,47,74,77,444...と続く。 n以下のラッキーナンバーで一番大きいのはどれか。 aからbの中にラッキーナンバーはいくつあるか。 …

SRM 166 DIV2 Level One - 三角形の組合せ

ようやくまともな問題。ま、一番簡単なラインを進んでるから当然か。 工場で働いてるんだけど、毎日毎日金属のスクラップが出るので、そいつを利用して三角形のピクチャーフレームを作りたいと思ってる(センスねぇな)金属片の長さが与えられるので、三角形の…

SRM 165 DIV2 Level One - イギリスの旧硬貨

イギリスの旧硬貨に関する問題。 一番小さい単位がペンスで、12ペンスで1シリング、20ペンスで1ポンド。ペンスを変換してコインの量を最適化せよと。 ややこしいシステムだな。今は100ペンス = 1ポンドらしい。 回答は、前に出てきた時計の問題と変わらず。 …

SRM 164 DIV2 Level One - 右揃え

テキストのフォーマット問題。 全ての長さが同じになるように右揃えにしなさいと。 #include <string> #include <vector> #include <sstream> #include <iomanip> #include <algorithm> using namespace std; #define foreach(bind, item) \ for (typeof ((item).begin()) bind = (item).begin(), __ie = (</algorithm></iomanip></sstream></vector></string>…

SRM 163 DIV2 Level One - シャクトリムシのお食事

英語で泣きそうになるな。 シャクトリムシは結構面白い動きをして、シャクトリムシ - Wikipediaこんなん。 日本語で尺取虫、英語でinchwormと言う位なので、長さを計る虫。という意味は変わらないらしい。 枝に等間隔に葉っぱが付いてる。シャクトリムシも等…

SRM 162 DIV2 Level One - 最小公倍数

C++ではあんまり解きたくない問題。 4,5,6とか範囲が与えられるので、最小公倍数を求める。 #include <vector> using namespace std; class LCMRange { public: static int lcm(int first, int last) { vector<int> numbers; int acc = 1; for (int i = first; i <= last;</int></vector>…

SRM 161 DIV2 Level One

簡単。 カードを配るだけ。ただし、10枚カードがあって、3人に配る場合は3枚づつ。"1231231234"を配ると{"111", "222", "333"} 普段quotient使ってるから気付かないけど、割って掛けたら違う数が出てくるっておかしな話だ。 10 / 3 * 3 = 9 10 * 3 / 3 = 10 …

SRM 160 DIV2 Level One

C++のfindってメンドイ。数字を覚えるのに、1〜0までで"TRADINGFEW"とかテーブルを作っておいて、"LGXWEV"で709とする。という変な暗記法。暗号として使ったほうが効果的だと思う。 #include <string> #include <algorithm> using namespace std; template <class T, class U> int find_index(T se</class></algorithm></string>…

SRM 158 DIV2 Level One - タイヤのローテーション

タイヤのローテーションなんて考えたこと無いよ。 タイヤのローテーションが、1 -> 3, 2 -> 4, 3 -> 2, 4 -> 1こんな感じ。初期設定から何フェーズ目で今の設定になるかという問題。 数学っぽくいけるかと思ったけど、イマイチわからなかったので、テーブル…

SRM 156 DIV2 Level One - ディスクスペースの確保

おっと、一問やり忘れた。 ハードディスクが複数台あるので、ががっとまとめて、最低何台必要か答える。 #include <vector> using namespace std; #define foreach(bind, item) \ for (typeof ((item).begin()) bind = (item).begin(), __ie = (item).end() ;\ bind </vector>…

SRM 157 DIV2 Level One - 数当てゲーム

プログラミング始めた頃に作った気がする。 数当てゲームは、100個の数字の中からランダムに数字を選んで数を当てるゲーム。 もうちょっと簡単にして、上限が9答えが6だとすると、 1〜9までの真ん中(1 + 9)/2の5を選ぶと、上です。と出る。 5は選んだから一…

SRM 155 DIV2 Level One - キープ

こういう問題好きだな。 インカ帝国では文字を持ってなくて、数を表すのに「縄の結び目の形で数で表す」という手法(キープ)を使っていたらしい。 キープ (インカ) - Wikipedia Quipu - Wikipedia, the free encyclopedia へぇぇ。 で、問題。Xで結び目、-が…

SRM 154 DIV2 Level One

また売値と買値。今度はマージンを求める。 入力が文字列なのでちょっと面倒だけど、新しい言語を覚えるには丁度いいレベル。 #include <vector> #include <string> #include <sstream> using namespace std; #define foreach(bind, item) \ for (typeof ((item).begin()) bind = (ite</sstream></string></vector>…

SRM 153 DIV2 Level One

小学生の宿題みたいな。 買値と売値と商品数があって、一番利益が出る商品名返す。利益が無い場合は""を返す。 #include <vector> #include <string> using namespace std; class MostProfitable { public: static string bestItem(vector<int> costs, vector<int> prices, vector<int> sale</int></int></int></string></vector>…

SRM 152 DIV2 Level One - 不動点

くそぅ。問題が全然わかんねぇ。 f(x) = R * x * (1 - x)のRが与えられるのでxを0.25から始めて、不動点を求めていく。200000回不動点を求めてみて、そこから更に1000回求めてみて、最大値と最小値の差がいくつになるかを答える。と、ここまで辿りつくまでが…

SRM 151 DIV2 Level One - PrefixCode

しばらくブログラムよりも英語で悩みそうだ。 電話番号とかだと、東京が03,大阪が06みたいになってる。そういう文字集合をPrefixCodeというらしい。035という番号をどこかの地域に割り当てるなんて事はしないので、PrefixCodeの正当性をチェックしたいと。 {…

SRM 159 DIV2 Level One - 路上駐車できるとこ

ロスで路上駐車の切符切られたことあるww 交通違反って何であんなに凹むんだ!? さて、ルールに基づいて、路上駐車できるところを探していく。 私道の前は停めちゃダメ。 バス停の前と、5,10メートル先は停めちゃダメ。 脇道の前と、5メートル先、5メート…

SRM 150 DIV2 Level One - 時計屋さん

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

SRM 149 DIV2 Level One - ドルのフォーマット

米ドルのフォーマットを出力する問題。 入力はドル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>…

SRM 148 DIV2 Level One - 割り切れる?

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

SRM 147 DIV2 Level One - シーザー暗号のデコード

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

SRM 146 DIV2 Level One - ヤッツィー

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