Cielが暇つぶしに以下の一人遊びをする．
条件分岐やるだけ．powなどのメソッドを使うとループ使わずに解ける．
scoreにnA * scoreAを加える．
class FoxPlayingGame { public: double theMax(int nA, int nB, int paramA, int paramB) { double res; double scoreA, scoreB; scoreA = paramA / 1000.0; scoreB = paramB / 1000.0; res = scoreA * nA; if(scoreB >= 1.0){ if(res >= 0.0){ res = res * pow(scoreB, (double)nB); } } else if(scoreB >= 0.0){ if(res <= 0.0){ res = res * pow(scoreB, (double)nB); } } else if(scoreB > -1.0){ if(res < 0.0){ if(nB >= 1) res = res * scoreB; } } else{ if(res >= 0.0){ nB = nB / 2 * 2; } else{ if(nB > 0 && nB % 2 == 0){ nB = nB - 1; } } res = res * pow(scoreB, (double)nB); } return res; } };
トータル2回ミスで125.01点．本番だと論外．
コーナーケースだけならまだしも，条件の判断ミスがあるのはだめすぎる．
SRM |
祖父母の宅にてSRMに参戦．家せまいから，明かり暗くして挑戦
Easyを開く．
軽く問題文を読んで，XORを各暗号文，各平文についてとって，それをsetに突っ込んでsetの要素数を返すプログラムを作成．
さすがにこれは違うだろうと思い，翻訳ソフトに突っ込んで確認．
任意の平文からすべての暗号文を生成できる鍵の個数を計算しろっていう問題だった．どうやら先に書いたのはChallengeで落とされるようなものだったらしい．問題文はよく読もう．
急いで書き直し．set<string>をmap<string, int>に書き換え，平文と暗号文のXORでおなじものがいくつあるかカウント．その数と暗号文の数が同じものをカウント．それが答え．
暗号文はすべて一意であること，平文もすべて一意であること，鍵は最低でも1つは存在することが保証されている．
1つの鍵に対して特定の暗号文を生成する平文は1つしかないところがみそ．
放置プレイ．今考えるとChallengeやったら点数もらえてたかもしれんのに．
難なくPassed．
順位:391
Rating:1330->1362
英語を読むのが遅い．基本的に単語が壊滅的にやばいので，来年の編入しも考慮に入れ，英語を勉強する必要あり．
未だに黄色にすらなれないのは鍛錬不足か．
思い出したかのように鍛錬
9桁の宝くじの当選番号が与えられるので，1枚の宝くじが当選する確率を求める．
早解きゲー
class TheLotteryBothDivs { public: double find(vector <string> goodSuffixes) { double res; res = 0.0; sort(goodSuffixes.begin(), goodSuffixes.end()); vector<string>::iterator it = unique(goodSuffixes.begin(), goodSuffixes.end()); goodSuffixes.erase(it, goodSuffixes.end()); int n = goodSuffixes.size(); for(int i=0;i<n;++i){ bool contains = false; for(int j=0;j<n;++j){ int li, lj; li = goodSuffixes[i].size(); lj = goodSuffixes[j].size(); if(i!=j && li >= lj){ int k; for(k=0;k<lj;++k){ if(goodSuffixes[i][li-k-1] != goodSuffixes[j][lj-k-1]){ break; } } if(k == lj){ contains = true; } } } if(!contains){ res = res + pow(0.1, (double)goodSuffixes[i].size()); } } return res; } };
最近プログラミングやってなさ過ぎてやばい．
最近怠けすぎてたので練習．
間違ってタブ消して一から書き直し．
(0,0)にいる魔法少女（仮にマリアちゃんとしよう）が，(x,y)にいる魔女を倒しに行きたい．
しかしマリアちゃんは(±1,±n)，(±n,±1）の方向にしか動けないのだ！（ちょっとすごい桂馬跳びみたいな．nは複数個与えられます)
マリアちゃんは魔女を倒しにいくことができるだろうか．
これだけで判定．
nが2ならば，3回の動きを組み合わせることで，上下左右に移動することができる．よって，何回かかるかは知らないが，マリアちゃんは魔女を倒せにいける．
nが3以上ならば，(+1，+n)方向に移動する．(+n，-1)方向に移動する．このときの位置は(+n+1，+n-1)，さらに(-n，-1)方向に移動．位置は(+1，+n-2)
何ということだろう．これはn-2の時の動きと同じではないだろうか．
つまり，nが偶数ならばnが2の時と同様の動きをできるのでマリアちゃんは魔女がどの場所にいても倒しにいくことができる．
nが奇数のとき，x座標，y座標の和について考える．
初期値は0+0=0．
これに，±(n+1)，±(n-1)を加えることになる．nが奇数ならn+1，n-1はともに偶数．偶数にいくら偶数を足しても偶数なので，マリアちゃんはx+yが偶数の位置にいる魔女しか倒しに行けない．
class MagicalGirlLevelOneDivOne { public: string isReachable(vector <int> jumpTypes, int x, int y) { string res; int n = jumpTypes.size(); for(int i=0;i<n;++i){ if(jumpTypes[i] % 2 == 0) return "YES"; } return (x + y) % 2 == 0 ? "YES": "NO"; } };
それは解いたとは言わない．
いつぞや参加したとき，一生懸命考えたけど解けなかったので，再び挑戦．
しかし，今回はanalysisという強力な味方（？）が．．．
数列が与えられるので，任意のフィボナッチ数列(f[i] = f[i-1] + f[i-2]となるような数列)の部分列で構成された数列a, bを選ぶ．aとbを順に並べたときに，単調増加になるときのみ連結することができる．
連結した数列の最長の長さを求める．
単調増加のときのみ連結できるので，並び替える．
与えられた数列を途中で2つに分ける．
小さいほうの数列，大きいほうの数列について，それぞれの要素で構成される最大のフィボナッチ数列の部分列の長さを計算，足し合わせる．
これをループを使って計算していって，最大値を解とする．
．．．とは言ったものの，フィボナッチ数列の部分列を計算できないと意味がない．
第0項a, 第1項bのフィボナッチ数列は，
a, b, a+b, a+2b, 2a+3b, 3a+5b, 5a+8b, 8a+11b, ...
となる．
これを一般化すると，
第0項=a，第i項(i>=1)=fib(i-1)*a + fib(i)*b
(fib(i)は，fib(0)=0, fib(1)=1としたときのフィボナッチ数の第i項目)
が得られる．
第0項がaで，第d+1項がbのフィボナッチ数列があると仮定する．
このとき，第1項をcとすると，
b = a * fib(i) + fib(i+1) * c
となる1以上の整数が存在する．
式を変形すると，
c = (b - a * fib(i)) / fib(i+1) となり，第1項が求められる．
これから，フィボナッチ数列を生成していきながら，該当する数がいくつあるかカウントする．
すべてのa，b，dについて同様の処理を行い，そのうちの長さの最大値が，数列から得られるフィボナッチ数列の部分列の長さの最大値になる．
フィボナッチ数を探す際に，2分探索を用いてもよいし（Analysisはこちらのソースコードが載っている)，単調増加なことを利用して，前から順番に調べてもいい．
計算量は，数列の長さをNとするとO(N^5)．
O(N^4)の解法も存在する．Analysisの練習問題にあった．すべてのi(0<=i<N)について，iを上限として（下限として）含むフィボナッチ数列の長さを計算してから答えを計算する．実装が増えそうだったのでやっていない．</ppp>
#include <algorithm> #include <iostream> #include <sstream> #include <string> #include <vector> #include <queue> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> using namespace std; define MAX 40 long long fib[41]; class SubFibonacci { public: int solve(vector<int> &S, int low, int high){ int res = 0; if(high - low < 3){ return high - low; } for(int a=low; a<high; ++a){ for(int b=a+1; b<high; ++b){ for(int d=0; d <= MAX; ++d){ long long t = S[b] - fib[d] * S[a]; if(t <= 0 || t % fib[d+1] != 0) continue; int last = S[a]; int curr = t / fib[d+1]; int index = a + 1; int cnt = 1; while(curr <= S[high - 1]){ int tmp; while(S[index] < curr && index < high) ++index; if(index >= high) break; if(S[index] == curr) ++cnt; tmp = last; last = curr; curr = last + tmp; } res = max(res, cnt); } } } return res; } int maxElements(vector <int> S) { int res; fib[0] = 0; fib[1] = 1; for(int i=2;i<=MAX;++i){ fib[i] = fib[i-1] + fib[i-2]; } res = 0; sort(S.begin(), S.end()); int n = S.size(); for(int i=0;i<=n;++i){ res = max(res, solve(S, 0, i) + solve(S, i, n)); } return res; } };
フィボナッチ数は第39項目あたりで，与えられる数値の上限を超えます．
solve(S, low, high)は，low<=i<highとなるS[i]を用いた最大のフィボナッチ数列の部分列の長さを返します．</ppp>