SRM 626 div2
250
class SumOfPower { public: int findSum( vector <int> array ) { vi v(array); int sum = 0; for(int i=1;i<=v.size();i++){ for(int k=0;k<v.size();k++){ if(k+i > v.size())continue; for(int j=k;j<k+i;j++){ sum += v[j]; } } } DUMP(sum); return sum; } };
500
class FixedDiceGameDiv2 { public: double getExpectation( int a, int b ) { int sums = 0; for(int i=1;i<=a;i++){ for(int j=1;j<=b;j++){ if(i>j)sums++; else break; } } double ret = 0; for(int i=1;i<=a;i++){ int cnt = 0; for(int j=1;j<=b;j++){ if(i>j)cnt++; else break; } ret += (double)i * ((double)cnt/(double)sums); } return ret; } };
1000
long long dp[1002][50]; int d[51][51]; class NegativeGraphDiv2 { public: long long findMin( int N, vector <int> s, vector <int> t, vector <int> weight, int charges ) { for(int i=0;i<1000;i++){ for(int j=0;j<50;j++){ dp[i][j] = INF; } } for(int i=0;i<50;i++){ d[i][i] = 0; for(int j=0;j<50;j++){ if(i!=j)d[i][j] = INF; } } for(int i=0;i<s.size();i++){ s[i]--;t[i]--; if(s[i]!=t[i])d[s[i]][t[i]] = weight[i]; } for(int k=0;k<50;k++){ for(int i=0;i<50;i++){ for(int j=0;j<50;j++){ d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } } } for(int i=0;i<N;i++)dp[0][i] = d[0][i]; for(int k=1;k<=charges;k++){ for(int i=0;i<s.size();i++){ dp[k][t[i]] = min(dp[k][t[i]], dp[k-1][s[i]] - weight[i]); } } long long ans = INF; for(int i=0;i<=charges;i++)ans = min(ans, dp[i][N-1]); return ans; } };
Competition
easy若干読めなかった。
midは期待値求めるの時間かかった。
結果：○○-
Practice
hardを解いた。
解法
- easy
特に必要無いよね
- mid
これも・・・必要ないよね。
- hard
Warshall-Floydでchargesが0の場合を求めてから
chargesを使った場合に関してDP。
Warshall-Floydを使わない場合はDPにNのループが付随するらしい。
まぁでも、これのほうが早いと思います。
hard、div1だと行列累乗じゃないと解けないって聞いたけど、まださっぱりわからん。
AOJ 2200 Mr. Rito Post Office
解法
動的計画法
dp[i][j] : i番目まで集配するとき、船をjに泊めていた場合にかかる最小のコスト
陸と海の距離に関してはWarshall-Floydで求めた。
ただ、Dijkstraでもできるらしい(知らん)
コード
//-------------include #include<cstdio> #include<string> #include<iostream> #include<cstring> #include<queue> #include<stack> #include<map> #include<set> #include<algorithm> #include<cmath> #include<cstdlib> #include<climits> #include<vector> #include<list> #include<deque> #include<functional> #include<sstream> //-------------define #define ALL(a) (a).begin(),(a).end() #define PB push_back #define MP make_pair #define SORT(c) sort((c).begin(),(c).end()) #define DUMP(x) cerr << #x << " = " << (x) << endl; #define CLR(a) memset((a), 0 ,sizeof(a)) #define rep(i,n) for(int i=0;i<(int)n;i++) #define fi first #define se second #define INF 1 << 28 //-------------namespace using namespace std; //-------------inline inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;} template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();} //-------------typedef typedef long long ll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<string> vs; typedef pair<int, int> pii; //-------------var int dx[]={0,-1,0,1,1,1,-1,-1}; int dy[]={1,0,-1,0,1,-1,1,-1}; int l[201][201]; int s[201][201]; int dp[1001][201]; int main() { int n,m; while(cin >> n >> m,n){ for(int i=0;i<200;i++){ s[i][i] = l[i][i] = 0; for(int j=0;j<200;j++){ if(i!=j)s[i][j] = l[i][j] = INF; } } for(int i=0;i<1000;i++){ for(int j=0;j<200;j++){ dp[i][j] = INF; } } for(int i=0;i<m;i++){ int a,b,t; char p; cin >> a >> b >> t >> p; a--;b--; if(p=='S'){ s[a][b] = s[b][a] = t; }else{ l[a][b] = l[b][a] = t; } } for(int k=0;k<n;k++){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ s[i][j] = min(s[i][j], s[i][k] + s[k][j]); l[i][j] = min(l[i][j], l[i][k] + l[k][j]); } } } int r; cin >> r; vi v(r); for(int i=0;i<r;i++){ cin >> v[i]; v[i]--; } dp[0][v[0]] = 0; for(int i=1;i<r;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ dp[i][k] = min(dp[i][k], dp[i-1][j] + l[v[i-1]][j] + s[j][k] + l[k][v[i]]); } dp[i][j] = min(dp[i][j], dp[i-1][j] + l[v[i-1]][v[i]]); } } int ans = INF; for(int i=0;i<n;i++){ ans = min(ans, dp[r-1][i]); } cout << ans << endl; } return 0; }
初CTF
@everysick がんばって: https://t.co/6qbXqvm2kR
— インターネット会社 (@KOBA789) June 22, 2014なんか超ビッグなデータが降ってきた。(Not ビッグデータ - Wikipedia
)
だうんろーよヽ(´ー｀)ノ
展開ヽ(´ー｀)ノ
20GB...まじかよ...
開くヽ(´ー｀)ノ
Emacs
開こうとしたら落ちた。無理。
SublimeText
頑張ってくれたけどメモリ足りなくなるし無理。
で、分割することにした
split -b 100000000 flag small
よいっしょっと。
適当なのを開いてみると、ぬるぬるした文字ばっかりだったので
flagのありそうなファイルを探す
p = [*'a'..'z'] base = "" p.each do |head| p.each do |tail| file_name = path + "/small" + head + tail target = File.open(file_name, "r+b").read base = target.hash if (head + tail) == "aa" puts file_name if base != target.hash end end
一個だけ出てきた
/MISERARENAIYO/bigdata/smallea
中身げろげろしてもらう
target = File.open("/MISERARENAIYO/bigdata/smallea", "r+b").read puts target
いかにもエンコードされてそうな文字出現
AQEHnwD0Dwt0ASEMHUD9CDb=
ここまで15分ヽ(´ー｀)ノ
ここから1時間ヽ(´ー｀;)ノ
デコードできない。
base64に何か引っ掛けてるのはわかるんだけど、
如何せん知識が無いので進めない。
...
...
...
手をあげる
@KOBA789 見つけた文字のデコードがさっぱりわからんヽ(´ー｀)ノｵﾃｱｹﾞ
— しっく (@everysick) June 22, 2014@everysick hint: rot13
— インターネット会社 (@KOBA789) June 22, 2014私「rot13 is 何」
シーザー暗号のなんとからしいことがわかった。なるほどね。そんなものもあるのか、始めて知った。
よいしょする
>>> print 'AQEHnwD0Dwt0ASEMHUD9CDb='.decode('rot13') NDRUajQ0Qjg0NFRZUHQ9PQo= >>> print 'AQEHnwD0Dwt0ASEMHUD9CDb='.decode('rot13').decode('base64') 44Tj44B844TYPt==
おっ、それっぽいの出てきたじゃん。
>>> print 'AQEHnwD0Dwt0ASEMHUD9CDb='.decode('rot13').decode('base64').decode('base64') ���|��>
...は？
>>> print 'AQEHnwD0Dwt0ASEMHUD9CDb='.decode('rot13').decode('base64').decode('rot13') 44Gw44O844GLCg==
おっ、こうか。
よしよしflagは....
>>> print 'AQEHnwD0Dwt0ASEMHUD9CDb='.decode('rot13').decode('base64').decode('rot13').decode('base64') ばーか
時間を無駄に消費した気がするのです
— しっく (@everysick) 2014, 6月 22結論：CTF楽しい
