TopCoder SRM 512 DIV2
Rating: 892(灰) → 926(緑)
緑復帰。といってもそもそも灰になったSRM 508についてノンタッチなのだが。
本格的なTopCoder復帰回。というかもう少し熱心にTCもPOJもやらないと今年の情報オリンピックが本気で危ないと思うのだがどうだろうか。
でもPOJ難しくて解けねえんだよなあ…TopCoderの過去問でもガンガン解くようにするかなあ。
256: MarbleDecoration
#include <iostream> #include <sstream> #include <string> #include <vector> #include <algorithm> using namespace std; class MarbleDecoration { public: int maxLength(int R, int G, int B) { vector<int> v(3); v[0] = R, v[1] = G, v[2] = B; sort(v.begin(), v.end()); int res = min(v[2], v[1]) * 2; res += ((v[2] - v[1]) > 0 ? 1 : 0); return res; } };
3色の球があったとしてそのうち2色で、交互に色がくるような一番長い首飾りを作れ、という物。
一番多い2色を選び、そのうちの小さいほう * 2 + (もし大きいほうと小さいほうに差がある ? 1 : 0)で計算できる。
512: MysteriousRestaurant
N日間しか空いておらず、1日1食しかできないレストランで毎日食事をし、与えられた金額以内でできるだけ多くの間食事をし続ける。しかも、同じ曜日には以降必ず同じ物を注文しなければいけない。毎日のそれぞれのメニューの値段が与えられる。
n日間、(金額無制限で)食べるのだとしたら、一番安価な選び方を求めるのは貪欲法によって容易である。
この問題においてn < 50であるので、これを繰り返す事によって解ける。
というメモが自分のメモ用紙に書いてあり、実際コンペ後に他人にも説明できたのだが、添字を考えたりするのが面倒になってコーディングを投げた。もう少しはやく思いついていれば実装する気ぐらいは起きたかもしれない。
1024:
512であきらめたので読まず。