SRM 519 Div 1 - Problem 250 BinaryCards
問題
SRM 519 Div 1 - Problem 250 BinaryCards
TopCoder Statistics - Problem Statement
使用言語
C++
問題概要
0から63までの数字のカード(全て1枚ずつ)を使う．数字xのカードには2ˆxのドットが描かれている．
最初全てのカードは伏せられている．AからBまでの連続する整数について，カードを表にして，カードに描かれるドットの数で表す．表になったカードのドットの合計を求める．
方針
表のカード(のドットの数)について考えると，
6: 2 4
7: 1 2 4
8: 8
となる．表になったドットは 1+2+4+8=15
→各数字のビット和でわかりそう
しかし，O(N)で最大10ˆ18になるので連続する整数のビット和を全て取るのは現実的でない．
ここで単純化して考える．
A = 2ˆ30 + 1, B = 2ˆ30 + 24とする．
答え(Cとする)にはもちろんA, Bが含まれる(C|A==A, C|B==B)
差分について考えると，23 = 16 + 4 + 2 + 1 = 0x10111
これの最上位ビット以下のは全て1になりそう（例 20ˆ3+8）
なのでそれ以下を1にする．
所感
・わかりにくすぎる問題文に反して，楽しい問題
・コード短すぎ問題
コード
class BinaryCards { public: long long largestNumber(long long A, long long B) { ll ans = A | B; //差分の最上位ビット以下のビットが1になるようにOR //どうせ最上位以下のビットは全て1になるので，最上位1つずつ左シフトしてforループ for (ll i = B - A; i > 0; i = i>>1) ans |= i; return ans; } };
SRM 518 Div 1 - Problem 250 LargestSubsequence
問題
SRM 518 Div 1 - Problem 250 LargestSubsequence
TopCoder Statistics - Problem Statement
使用言語
C++
問題概要
与えられた文字列から各文字の相対的な順序は変えずに，文字列を抽出し，その中で辞書順で最も大きくなる文字列を返す．
方針
文字列 .*XY.* について，
X>=YならXは残す
X
・文字列の連結が自然にできるのはありがたい．言語仕様に感謝．
コード
class LargestSubsequence { public: string getLargest(string s) { string ans = ""; int l = s.length(); ans += s[l-1]; for (int i = l-2; i >= 0; i--) { if (ans[0] <= s[i]) ans = s[i] + ans; } return ans; } };
Tax Rate Changed (1192)
問題
Tax Rate Changed (1192)
税率変更 | Aizu Online Judge
使用言語
C++
方針
・一つの数式で強引に解こうとする→失敗
・素直に本来の値段で全探索
所感
・素直に生きたい
コード
#define xplice(p,q) p * (100 + x) / 100 + q * (100 + x) / 100 #define yplice(p,q) p * (100 + y) / 100 + q * (100 + y) / 100 int x, y, s, ans; int main() { while (cin>>x>>y>>s, x) { ans = 0; for (int a = 1; a <= s; a++) { for (int b = 1; b <= s; b++) { int tmp = xplice(a,b); if (tmp < s) { continue; } else if (tmp == s) { ans = max(ans, yplice(a,b)); //cout<<a<<" "<<b<<" "<<tmp<<" "<<yplice(a,b)<<endl; } else { break; } } } cout<<ans<<endl; } return 0; }
AtCoder Beginner Contest 111 C - /\/\/\/
問題
AtCoder Beginner Contest 111 C - /\/\/\/
C - /\/\/\/
使用言語
C++
方針
・iが奇数，偶数の時に登場する数の個数で考える．奇数，偶数でaiがどれくらい出てきたかをp1[i], p2[i]で管理．
・場合分け
p1，p2のどちらかに複数の最頻値があるor p1，p2の唯一の最頻値が使う
→その最頻値を使う
上記以外
→p1の最頻値とp2の2番目かp2の最頻値とp1の2番目のどちらかを使う(片方の最頻値ともう片方の2番目が同じ数字になることはない，上で弾かれるため)
所感
・バグ祭りで死にましたかかってしまった．無念．．
・ACまでに想定していた時間の5倍くらい
コード
#include <iostream> #include <algorithm> #include <vector> using namespace std; #define FOR(i,a,b) for (size_t i = a; i < b; i++) #define REP(i,b) FOR(i,0,b) #define RFOR(i,a,b) for (size_t i = a-1; i >= b; i--) #define RREP(i,a) RFOR(i,a,0) #define INF 1e7 #define num 111111 int p1[num], p2[num]; vector<int> a, b; int main() { int n, m1 = 1, m2 = 1, tmp; cin>>n; REP(i,n/2) { cin>>tmp; p1[tmp]++; cin>>tmp; p2[tmp]++; } REP(i,num) { if (p1[i] > m1) { a.clear(); a.push_back(i); m1 = p1[i]; } else if (p1[i] == m1) { a.push_back(i); } if (p2[i] > m2) { b.clear(); b.push_back(i); m2 = p2[i]; } else if (p2[i] == m2) { b.push_back(i); } } if (a.size() > 2 || b.size() > 2) { cout<<n - m1 - m2<<endl; } else if (a[0] != b[0]) { cout<<n - m1 - m2<<endl; } else { sort(p1, p1+num); sort(p2, p2+num); int r = max(m1 + p2[num-2], m2 + p1[num-2]); cout<<n-r<<endl; } return 0; }
SRM 517 Div 1 - Problem 250 CompositeSmash
お久しぶりです．
問題
SRM 517 Div 1 - Problem 250 CompositeSmash
TopCoder Statistics - Problem Statement
使用言語
C++
問題概要
Nを任意の回数（0回でも良い）分割して，targetに（どちらかの整数が）一致したらYes，一致しなければNoを返す．
分割とは，整数xを分割するとき，2以上のy,zに分割され，それらの積はxになる．
方針
・任意の回数→再帰？
・再帰の中身
数値がtargetと一致→Yes
それ以外→全ての分割した数字の組みについてtargetと一致するか判定or更に分割
所感
・動かしたら動いたのでよかった．
コード
bool smash (int a, int b) { if (a == b) { return true; } else { //flag: 素数じゃないか（分割できるか）判定 //rtn: 全ての分割した結果がtargetに行き着くかを返す bool flag = false, rtn = true; for (int i = 2; i * i <= a; i++) { if (a % i != 0) continue; else { flag = true; rtn = rtn & (smash(i,b) | smash(a/i,b)); } } if (flag) return rtn; else return false; } } class CompositeSmash { public: string thePossible(int N, int target) { if (smash(N, target)) return "Yes"; else return "No"; } };
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; } };
