模擬国内予選2014
いつものチラシ裏。
- -
C : 壊れた暗号生成器
- writerでした。国内予選レベルの構文解析の練習にと考えてみた問題。
- ?数制限はかなり迷った結果、謎の組織の会議によって3個制限を付けることに。
- 上位層は置換でサクッと通すだろうと思っていたら、意外と全探索してバグらせるチームがちらほら。
- でも一番仕事したのは、"++(たくさん)++R"と"--(いっぱい)--U"だった。剰余計算は闇ですね。
- 最後のサンプルがLOLだったり、1個目の出力に"GOODLUCKANDHAVEAFUN"が入ってたり、2個めの出力に"AZUNYAN"が入ってたりしますが、暗号生成器こわれてるから仕方ないね。
- 以下のコードは解説に従って書きなおしたもの。
#include <iostream> #include <string> #include <algorithm> using namespace std; string readCipher(const string& str, int& idx); string readString(const string& str, int& idx); char readLetter(const string& str, int& idx); string readCipher(const string& str, int& idx){ string res = ""; while(idx < str.size() && str[idx]!=']') res += readString(str, idx); return res; } string readString(const string& str, int& idx){ string res; if(str[idx]=='['){ ++idx; res = readCipher(str, idx); reverse(res.begin(), res.end()); ++idx; } else { res = readLetter(str, idx); } return res; } char readLetter(const string& str, int& idx){ char c = str[idx++]; char res; if(c == '+'){ res = readLetter(str, idx); if(res != '?') res = (res-'A'+1)%26+'A'; } else if(c == '-'){ res = readLetter(str, idx); if(res != '?') res = (res-'A'+25)%26+'A'; } else { res = c; } return res; } int main(){ string str; while(cin >> str){ if(str == ".") break; int idx = 0; string res = readCipher(str, idx); for(int i=0;i<res.size();i++) if(res[i] == '?') res[i] = 'A'; cout << res << endl; } }
E : 流れ星に願いを
- writerでした。昨年の夏くらいに、男3人で花火大会を見た思い出から作った問題。
- 考えたのが昨年なので、国内予選のために的な気持ちは入ってなかった。
- 最初はお姫様の願い事を叶えてあげよう的な問題文を書いたものの、他の問題を見て空気読んだ。
- 誤差まわりはそんなに気にしなくて良いはずだけど、「t<10^{-8}では接触しない」をスルーすると場合によっては引っかかる。
- 3分探索は想定してなかった。
#include <iostream> #include <vector> #include <valarray> #include <algorithm> #include <cstdio> using namespace std; double EPS = 1e-12; class P3{ public: double x, y, z; P3(double x = 0, double y = 0, double z = 0) : x(x), y(y), z(z) {} P3 operator + (const P3 &p) const { return P3(x+p.x,y+p.y,z+p.z); } P3 operator - (const P3 &p) const { return P3(x-p.x,y-p.y,z-p.z); } P3 operator * (const P3 &p) const { return P3(x*p.x,y*p.y,z*p.z); } P3 operator * (const double &p) const { return P3(x*p,y*p,z*p); } P3 operator / (const double &p) const { return P3(x/p,y/p,z/p); } double sum() const { return x+y+z; } double squareSum() const { return x*x+y*y+z*z; } }; struct Star { P3 p; P3 v; double r, d; }; int main(){ int n; while(cin >> n && n){ vector<Star> vs(n); for(int i=0;i<n;i++){ cin >> vs[i].p.x >> vs[i].p.y >> vs[i].p.z; cin >> vs[i].v.x >> vs[i].v.y >> vs[i].v.z; cin >> vs[i].r >> vs[i].d; } vector< pair<double, pair<int, int> > > vp; for(int i=0;i<n;i++){ vp.push_back(make_pair(vs[i].r/vs[i].d, make_pair(i, -1))); } for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ double a = (vs[i].v-vs[j].v).squareSum() - (vs[i].d+vs[j].d)*(vs[i].d+vs[j].d); double b = ((vs[i].v-vs[j].v)*(vs[i].p-vs[j].p)).sum() + (vs[i].r+vs[j].r)*(vs[i].d+vs[j].d); double c = (vs[i].p-vs[j].p).squareSum() - (vs[i].r+vs[j].r)*(vs[i].r+vs[j].r); if(abs(a) < EPS){ if(abs(b) < EPS) continue; double t = -c/b; if(t > 0) vp.push_back(make_pair(t, make_pair(i,j))); } else { if(b*b-a*c < 0) continue; double t1 = (-b-sqrt(b*b-a*c))/a; double t2 = (-b+sqrt(b*b-a*c))/a; if(t1 > t2) swap(t1, t2); if(t1 > 0){ vp.push_back(make_pair(t1, make_pair(i, j))); } else if(t2 > 0){ vp.push_back(make_pair(t2, make_pair(i, j))); } } } } sort(vp.begin(), vp.end()); vector<double> res(n, 1e12); vector<int> hit(n, 0); for(int i=0;i<vp.size();i++){ int idxA = vp[i].second.first; int idxB = vp[i].second.second; if(hit[idxA] || (idxB!=-1 && hit[idxB])) continue; res[idxA] = vp[i].first; hit[idxA] = 1; if(idxB != -1){ res[idxB] = vp[i].first; hit[idxB] = 1; } } for(int i=0;i<n;i++) printf("%.12lf\n", res[i]); } }
G : ゴルフ
- 担当じゃなかったけど撃墜祭りに乗ってみた
- 解説が素晴らしいのでご一読いただければと
- 非実在問題にならないかドキドキしてたけど、提出あって良かった
- a/x=bを満たすxを求める方法を知らず、2分探索したアカウントがこちらになります
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <cmath> using namespace std; const long long MAX_VALUE = 1LL<<36; const long long MAX_DIGIT = 11; vector< pair<int, long long> > power; map<long long, int> term; int getLength(long long t){ int res = 1; for(long long i=t;i>=10;i/=10){ res++; } return res; } int getTermLen(long long t){ if(term.count(t)) return term[t]; return getLength(t); } bool checkUpdate(long long value, int length){ if(length < getLength(value)){ if(term.count(value)){ int curBest = term[value]; if(length < curBest){ term[value] = length; return true; } } else { term[value] = length; return true; } } return false; } void makePower(){ for(long long i=2;i*i<MAX_VALUE;i++){ long long value = i*i; int p = 2; int baseLen = getLength(i); while(value < MAX_VALUE){ int length = baseLen + getLength(p) + 1; checkUpdate(value, length); value *= i; p++; } } for(map<long long, int>::iterator it=term.begin(), end=term.end();it!=end;++it){ power.push_back(make_pair(it->second, it->first)); } sort(power.begin(), power.end()); } void termSearch(long long curValue, int curLength, bool mul){ if(curLength >= getLength(curValue)-1) return ; for(long long i=2;;++i){ long long nextValue = mul ? curValue*i : curValue/i; long long nextLen = curLength + getLength(i) + 1; if(nextValue >= MAX_VALUE) break; if(nextLen > MAX_DIGIT-3) break; if(nextLen >= getLength(nextValue)){ if(!mul) break; continue; } if(checkUpdate(nextValue, nextLen) && nextLen <= MAX_DIGIT-5){ termSearch(nextValue, nextLen, !mul); } } } void makeTerm(){ for(int i=0;i<power.size();i++){ termSearch(power[i].second, power[i].first, true); termSearch(power[i].second, power[i].first, false); } } void precalc(){ power.clear(); term.clear(); makePower(); makeTerm(); } int getDivNum(long long a, long long b){ // a/x = b if(a < b) return -1; int L = 1, R = 1000; while(R-L > 1){ int mid = (L+R)/2; if(a/mid > b) L = mid; else R = mid; } if(a/R == b) return R; return -1; } int solve(const long long s){ int res = getLength(s); if(term.count(s)) res = term[s]; for(map<long long, int>::iterator it=term.begin(), end=term.end();it!=end;++it){ long long baseValue = it->first; int baseLen = it->second; if(baseLen+2 >= res) continue; // baseValue +- v = s long long v = abs(s - baseValue); if(v < MAX_VALUE){ res = min(res, baseLen + getTermLen(v) + 1); } // baseValue * v = s if(s%baseValue == 0){ v = s/baseValue; res = min(res, baseLen + getTermLen(v) + 1); } // baseValue / v = s v = getDivNum(baseValue, s); if(v != -1){ res = min(res, baseLen + getLength(v) + 1); } } for(int i=0;i<power.size();i++){ // (power[i].second-v)*t for(int v=1;;v++){ int lenV = getLength(v); if(power[i].first+lenV+3 > res-2) break; long long baseValue = power[i].second - v; if(baseValue < 0) break; if(s%baseValue == 0){ long long t = s/baseValue; res = min(res, power[i].first+lenV+4+getLength(t)); } } for(int j=0;j<i;++j){ if(power[i].first + power[j].first > res-2) break; // pow2つ long long valA = power[i].second; long long valB = power[j].second; // valA + valB if(valA + valB == s){ res = min(res, power[i].first + power[j].first + 1); } // valA + valB +- v long long v = abs(s - (valA+valB)); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA - valB if(abs(valA - valB) == s){ res = min(res, power[i].first + power[j].first + 1); } // valA - valB +- v v = abs(s - abs(valA-valB)); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA * valB if((double)valA*valB < 1e15 && valA*valB < MAX_VALUE){ // valA * valB if(valA*valB == s){ res = min(res, power[i].first + power[j].first + 1); } // valA * valB +- v v = abs(s - valA*valB); res = min(res, power[i].first + power[j].first + getLength(v) + 2); // valA * valB / v v = getDivNum(valA*valB, s); if(v != -1){ res = min(res, power[i].first + power[j].first + getLength(v) + 2); } } } } return res; } int main(){ precalc(); long long s; while(cin >> s && ~s){ cout << solve(s) << endl; } }
