SRM 516 Div 1 - Problem 250 NetworkXOneTimePad
お久しぶりです．
問題
SRM 516 Div 1 - Problem 250 NetworkXOneTimePad
TopCoder Statistics - Problem Statement
使用言語
C++
問題概要
N個のビット列のplaintextsがある．各plaintextsにXORすると全てのciphertextsになるkeyが存在する．その数を求める．
方針
・全てのN個のビット列についてplaintextsにXORしてciphertextsの全てになるか調べる
→時間がかかる(最大2ˆ50)のでダメ
・XORであれば，plaintextsとciphertextsから変換に用いられたkeyの候補をXORで導ける．ciphertextsから全てのplaintextsについてXORするとkeyの候補がある．このkeyの候補は実際のkeyの集合を含む集合である．この候補が全てのciphertextから導かれる場合は，それはkeyである．
・出てきた回数はmapで管理
ex)
{"000", "111", "010", "101", "110", "001"}
{"011", "100"}
→011: 011, 100, 001, 110, 101, 010
100: 100, 011, 110, 001, 010, 101
両方のkeyの候補に含まれている．
所感
・諸事情で長時間プログラミングしていなかったので，さらに能力が落ちました．
・結論，mapは便利
コード
int N, lp, lc, ans = 0; map<string, int> mp; string myXOR (string p, string c) { string tmp(N, '0'); REP(i,N) tmp[i] = p[i] == c[i] ? '0' : '1'; return tmp; } class NetworkXOneTimePad { public: int crack(vector<string> plaintexts, vector<string> ciphertexts) { N = plaintexts[0].length(); lp = plaintexts.size(); lc = ciphertexts.size(); REP(i,lp){ REP(j,lc){ string key_tmp = myXOR(plaintexts[i], ciphertexts[j]); if (mp.find(key_tmp) == mp.end()) { mp[key_tmp] = 1; } else { mp[key_tmp]++; } } } for (auto itr = mp.begin(); itr != mp.end(); ++itr) { if (itr->second == lc) ans++; } return ans; } };
SRM 503 Div 1 - Problem 250 ToastXToast
問題
SRM 503 Div 1 - Problem 250 ToastXToast
TopCoder Statistics - Problem Statement
使用言語
C++
方針
・色々やるがぐちゃぐちゃ
→・まず，undertoastedの最{小，大}値がovertoasted の最{小，大}値を上回っているのはおかしい．なぜなら，全てのトーストのタイプは，やけなすぎとやけすぎのどちらも存在しているはずだから．
・max(u1, u2, ... , ui) < max(o1, o2, ... , oi)なら
ここの間で区切れば良い．
・その他の場合は，min(u1, u2, ... , ui)より大きく，max(u1, u2, ... , ui)より小さいところで適当にmin(o1, o2, ... , oi)未満のX1を設定してしまい，X1未満のundertoastedはタイプ1，X1より大きいのundertoastedはタイプ2としてしまえば良い．同様に，min(o1, o2, ... , oi)より大きく，max(o1, o2, ... , oi)より小さいところで適当にmax(u1, u2, ... , ui)より大きいのX2を設定してしまい，X2未満のovertoastedはタイプ1，X2より大きいovertoastedはタイプ2としてしまえば良い．（例外は上で弾いている）
ex (sample4)
1 | 2 4
3 5 | 6
(X1,2の値は｜の含まれる閉区間であればどこでも良い)
所感
・下手に考えるだけ無駄だった
・マクロ楽しい
コード
#define Min(a) *min_element(a.begin(), a.end()); #define Max(a) *max_element(a.begin(), a.end()); class ToastXToast { public: int bake(vector<int> undertoasted, vector<int> overtoasted) { int min_u = Min(undertoasted); int max_u = Max(undertoasted); int min_o = Min(overtoasted); int max_o = Max(overtoasted); if (min_u > min_o || max_u > max_o) return -1; else if (max_u < min_o) return 1; else return 2; } };
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; }
