SRM 502 Div 1 - Problem 250 TheLotteryBothDivs
問題
SRM 502 Div 1 - Problem 250 TheLotteryBothDivs
TopCoder Statistics - Problem Statement
使用言語
C++
方針
・setを用意する．
・setの各要素について，要素の各下位str.length()字が新たな文字列strに一致する場合は,その要素を廃棄．str追加．
・新たな文字列strについて，strの下位itr.length()字がsetのある要素itrに一致する場合はstrは廃棄．
問題点
・ほとんどのケースで通るが112番目のケースでWA，コーナーケースか？（201808022025現在）
所感
・実装するだけだと思っていたが．．．
コード
#define lgt length() set<string> st; void add (string str) { bool flag = true; for (string itr: st) { if (itr.lgt >= str.lgt) { if (itr.substr(itr.lgt-str.lgt, str.lgt) == str) st.erase(itr); } else { if (str.substr(str.lgt-itr.lgt, itr.lgt) == itr) flag = false; } } if (flag) st.insert(str); } class TheLotteryBothDivs { public: double find(vector<string> goodSuffixes) { int size = goodSuffixes.size(); double ans = 0.0; for (size_t i = 0; i < size; i++) add(goodSuffixes[i]); for (string itr: st) { cout<<itr<<endl; ans += pow(0.1, itr.lgt); } return ans; } };
TopCoder Member SRM 501 div1 easy - FoxPlayingGame
問題
TopCoder Member SRM 501 div1 easy - FoxPlayingGame
TopCoder Statistics - Problem Statement
使用言語
Java
要約
scoreに対して任意の順序でnA回
方針
・全探索
→O(2ˆn)なので×
・場合分け
→面倒臭い
・最大値を求める
→乗算の効果を最大にするために，常にまとまって掛け算される
→そのまとまりに何回(paramB/1000)をかけるかでループ
所感
・明日Javaの試験なので今日はJavaです
・勘が大切な問題
・キャスト！
コード
public double theMax(int nA, int nB, int paramA, int paramB) { double sumA = nA * (paramA / 1000.0); double pb = paramB / 1000.0; double ans = -10e9 + 0.0; for (int i = 0; i < nB + 1; i++) ans = Math.max(ans, sumA * Math.pow(pb, i)); return ans; }
AtCoder Beginner Contest 103 D - Islands War
問題
AtCoder Beginner Contest 103 D - Islands War
D - Islands War
使用言語
C++
方針
・取り除く必要のある橋の本数の最小値を求める．島は直線上に並んでいる．
→狭い区間で争いが起きていたら，その外側は必ず行き来できなくなるので気にしなくて良い
→mapで東側の最も近い敵の場所を管理
・取り除く必要のある橋の本数の最小値を求める==壊さない橋の本数を最大化する
→橋を前から順に見ていき，本当に橋を壊す必要があるところまでは壊さない．
ex)
1-2-3-4-5
1 4で争う時，前から見ていくと3のところで橋を壊せば良い
1-2-3|4-5
2-5で争う(ことのみを考える)時，前から見ていくと5のところで橋を壊せば良い
1-2-3-4|5
これらを組み合わせる
まず島1について，最も東側だとして3と4の間の橋を壊せば良い
1-2-3-4-5
島2について，島1の理由で3と4の間の橋を壊されるので，5のことは気にしなくても良い
1-2-3-4-5
島3について，争ってはいないがこれ以上橋をかけたまま東の島を見るわけにはいかないので橋を破壊(ans++)
これ以上，破壊する必要のある橋は今の所ない（r=INF）（もし島3と争っている島があったとしたら，その島の手前の橋を壊すべき橋とする）
ex2)
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4-5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8-9
1-2-3-4|5-6-7-8|9
所感
・union find木っぽさあるが削るし，有り難く直線なので違う
・好きな問題ではある
・コンテスト中に解き終わりたかった
コード
int N, M; map<int, int> mp; int main() { cin>>N>>M; REP(i,M) { int a, b; cin>>a>>b; if (mp[a] > b || mp[a] == 0) mp[a] = b; } int l, r = INF, ans = 0; FOR(l,1,N+1) { if (mp[l] != 0) { r = min(mp[l], r); } if (l>=r) { ans++; r = mp[l] == 0 ? INF : mp[l]; } } cout<<ans<<endl; return 0; }
AtCoder Beginner Contest 103 C - Modulo Summation
問題
AtCoder Beginner Contest 103 C - Modulo Summation
C - Modulo Summation
使用言語
C++
方針
・各mについて見るの時間かかりそう＆＆mの大きさは大きい方が良さそう．．．（数によってはlong longでも足りない？）
・そもそも最大値になるということは，m mod aがa-1になる時
→a[I]-1を足すだけ
所感
・abcのcにしては簡単だった
・貪欲したい欲を抑える
コード
int N; vector<int> a; int main() { cin>>N; REP(i,N) { int tmp; cin>>tmp; a.push_back(tmp); } int f = -N, size = a.size(); REP(i, size) f += a[i]; cout<<f<<endl; return 0; }
SRM 500 Div 2 - Problem 250 SRMCards
問題
SRM 500 Div 2 - Problem 250 SRMCards
TopCoder Statistics - Problem Statement
使用言語
C++
所感
・やるだけ
コード
int maxTurns(vector<int> cards) { int ans = 0; sort(cards.begin(), cards.end()); int count = cards.size(); for (size_t i = 0; i < count; i++) { ans++; if (cards[i] + 1 == cards[i+1]) i++; } return ans; }
SRM 500 Div 1 - Problem 250 MafiaGame
問題
SRM 500 Div 1 - Problem 250 MafiaGame
TopCoder Statistics - Problem Statement
使用言語
C++
方針
・最も投票された人にのみ注目
・N人の人が残る候補者にどう投票するかでループ
所感
・問題文理解できなかったり，スペルわからなくなったり，英弱の極みという感じだった．
・複雑に考えちゃいけない問題
コード
vector<int> vote(555, 0); class MafiaGame { public: double probabilityToLose(int N, vector<int> decisions) { int size = decisions.size(); for (size_t i = 0; i < size; i++) { vote[decisions[i]]++; } //最も投票された回数 int maxvote = *max_element(vote.begin(), vote.end()); //最も投票された人の人数 int maxnum = count(vote.begin(), vote.end(), maxvote); //最も投票された人でも1票ということは，全員1票で無限ループ if (maxvote == 1 && N != 1) return 0.0; //単独で最多投票獲得数ならばその人が敗者決定 if (maxnum == 1) return 1.0; //ここで候補を絞る //N票しか存在しないので，候補者がmaxnum以上になることはない //確実に入れる人の数は同じなので，全員ランダムとみなして問題ない //一人になったら終了 int candidate = maxnum; while (candidate != 1) { //次の投票数が最多の人の人数を計算 candidate = N % candidate; //(mod 0)==投票数が最多の人の人数が変化しない==無限ループ if (candidate == 0) return 0.0; } //maxnum人の中誰が候補者になっておかしくなかった． return 1.0 / maxnum; } };
主に要約など参考：
Top Coder Single Round Match 500 Div1 - 練習帳 - TopCoder部
ABC097-C(12問目)
問題
AtCoder Beginner Contest 097 C - K-th Substring
C: K-th Substring - AtCoder Beginner Contest 097 | AtCoder
使用言語
C++
方針
・k文字以下の文字列作りまくる
→木にぶち込む
→k番目出力
所感
・setディスられてたの見たけど，重複可なの逆に便利
コード
int main() { string s; int K; set<string> S; cin>>s>>K; int size = s.length(); for (int i = 0; i < size; i++) { string tmp; for (int j = 0; j < 5 && j + i < size; j++) { //多分ここ5じゃなくてkでもいける tmp = s.substr(i, j+1); S.insert(tmp); //cout<<tmp<<S.size()<<endl; } } set<string>::iterator itr = S.begin(); for (int i = 0; i < K - 1; i++) itr++; cout<<(*itr)<<endl; return 0; }
