ドイツに行ってきます。
明後日からドイツ行ってきます。
しばらく放置します。
解析的な解法
新年明けましておめでとうございます。
今日は新年早々AOJで問題を解きました。
その問題の解法について解説を読んでみる勉強になったことがあったので、メモしておこうと思います。
まず、この問題（ここから）は、解説によると全検索でも求められるそうですが、４つの硬貨を用いる問題なのでループの数が面倒になります。そこで、よく自販機なので用いる両替テクニックを実際に考えてみることにしてみます。まず、考えることはちょうど硬貨が支払えるかと言うことを考えるはずです。この時に財布で起こってることは各硬貨について枚数が足りているかを考えます。枚数が足りないときは、代金より多いお金を支払い、おつりを貰います。また、１００円のものを買うとき財布に１０円玉が２０枚あるとします。この時の支払いは１０円を２０枚支払い、１枚の１００円硬貨をおつりとしてもらうことが硬貨の枚数削減の最良の手法になります。
この考えを式に直します。
例として次のような場合を考えます。
支払額 ＝＞ ５３０
１０円 ＝＞ １枚、５０ ＝＞ １３枚、１００円 ＝＞ ７枚、５００円 ＝＞ １６枚
支払い後の残金は８８２０円になります。この代金について硬貨の枚数を一番少なくしてみます。
８８２０ ÷ ５００ ＝ １６・・・３２０
３２０ ÷ １００ ＝ ３ ・・・ ２０
２０ ÷ ５０ ＝ ０ ・・・ ２０
２０ ÷ １０ ＝ ２ ・・・ ０
この各硬貨の枚数について、元々所持していた枚数と差をとります。
１６ ー １６ ＝ ０
７ ー ３ ＝ ４
１３ ー ０ ＝ １３
１ ー ２ ＝ −１
この解は各貨幣について
解 ＞ ０ ・・・ 財布から支払った貨幣の枚数
解 ＝ ０ ・・・ 財布の中の貨幣の枚数が変化していない
解 ＜ ０ ・・・ おつりとして増えた貨幣の枚数
つまり、この問題は上の作業で得られた解の０より大きい枚数について回答します。
この考えをコードにしたものです。
#include <iostream> using namespace std; int main() { int P, price[4][2] = {{10,}, {50,}, {100,}, {500,}}; bool flag = false; while (cin >> P && P) { int total = 0; for (int i = 0; i < 4; i++) { cin >> price[i][1]; total += (price[i][0] * price[i][1]); } P -= total; P = -P; for (int i = 3; i >= 0; i--) { price[i][1] = price[i][1] - P / price[i][0]; P = P % price[i][0]; } if (flag) cout << endl; for (int i = 0; i < 4; i++) { if (price[i][1] > 0) cout << price[i][0] << " " << price[i][1] << endl; } flag = true; } return 0; }
pairの一方の値を使ったソート
AOJ 0029より
文字列とその文字列の出現回数をpairの値として使います。pairの出現回数に付いて一番大きいものを見つけたいと思います。そこでpairについて一番大きい値をループで見つけるのもありですが、今回をsortを使って一番大きいものを見つけたいと思います。
- コード
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<string, int> P;
bool pairCompare(const P& firstElof, const P& secondElof)
{
return firstElof.second > secondElof.second;
}
int main(void)
{
string s, m;
vector<P> v;
while (cin >> s) {
if (m.size() < s.size()) m = s;
bool flag = true;
for (int i = 0; i < v.size(); i++) {
if (v[i].first == s) {
flag = false;
v[i].second++;
}
}
if (flag) v.push_back(P(s,1));
}
sort(v.begin(), v.end(), pairCompare);
cout << v[0].first << " " << m << endl;
return 0;
}
Rubyはすごい？！
AOJ 0015を解いてみてRubyってすごいなと思った反面、プログラミング言語でこんなにプログラムの組み方が変わるんだなと思いました。
もともとRubyは直感的なプログラミングを求めて作られた言語だから当然と言えば当然だけど、はっきり言ってC++とRubyでコードの違いが出てしまうとmatzの手のひらの上で踊らされてる感がある。（笑）
コードです。
num = gets.to_i while num > 0 num1 = gets.to_i num2 = gets.to_i ans = num2+num1 if ans >= 10**80 then puts "overflow" else puts ans end num = num - 1 end
#include <iostream> #include <string> #include <stack> using namespace std; int changeNumber(char number) { int num = 0; for (char i = 48; i < 58; i++) { if (number == i) return num; num++; } } void puls(string number1, string number2) { stack<int> s; int tmp = 0; for (int i = 1; i <= number1.size() && i <= number2.size(); i++) { tmp = tmp + changeNumber(number1[number1.size() - i]) + changeNumber(number2[number2.size() - i]); s.push(tmp % 10); tmp /= 10; } for (int i = number2.size() + 1; i <= number1.size(); i++) { tmp = tmp + changeNumber(number1[number1.size() - i]); s.push(tmp % 10); tmp /= 10; } if (tmp > 0) s.push(tmp); if (s.size() > 80) cout << "overflow" << endl; else { while(0 < s.size()) { cout << s.top(); s.pop(); } cout << endl; } } int main(void) { string number1, number2; int count; cin >> count; for (int i = 0; i < count; i++) { cin >> number1 >> number2; if (number1.size() < number2.size()) puls(number2, number1); else puls(number1, number2); } return 0; }
Twitter Client Made of Ruby Programming Language
ツイッターをRubyでやってみました。
- 使ったもの
Ruby ( version 2.0.0 )
gem twitter ( version 5.3.0 )
- やる事
これを見ながらとりあえず進めてみる。
Twitter(Gem) - 逆引きRuby
実行するとログインの段階で失敗します。
undefined method `configure' for Twitter:Module (NoMethodError)
こんな感じにエラーメッセージがでます。どうやらtwitter gemのバージョンが更新されてメッソドが古くなったようなので、とりあえずリファレンスを見てみます。
File: README — Documentation for twitter (5.1.1)
リファレンスに従って新しいログイン方法を使います。英語だったのでよくわからなかったけど、ログインの方法は２つあるようです。とりあえず一番上のものを使ってみました。
この修正で使えるようになりました。
require 'rubygems' require 'twitter' YOUR_CONSUMER_KEY = "*****" YOUR_CONSUMER_SECRET = "*****" YOUR_ACCESS_TOKEN = "*****" YOUR_ACCESS_SECRET = "*****" client = Twitter::REST::Client.new do |config| config.consumer_key = YOUR_CONSUMER_KEY config.consumer_secret = YOUR_CONSUMER_SECRET config.access_token = YOUR_ACCESS_TOKEN config.access_token_secret = YOUR_ACCESS_SECRET end client.update("test")
