りはびり！と書こうとして止めた。

[SRM]

SRM476 Div2 Easy(300) MatrixShiftings

各要素が'0'-'9'である行列が与えられる(matrix).
これの行または列を循環的に1つずつずらして、ある値(value)を持つ要素が左上(つまりij=00)に来るようにする。
この作業に必要な最小手数（ずらす回数）を求めよ。不可能な場合は-1を返すこと。

------------------------------------------
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

struct MatrixShiftings{
    int minimumShifts(vector <string> matrix, int value){
        int N = matrix.size(), M = matrix[0].length();
        int ans = N*M+1;
        for(int i=0; i<N; ++i){
            for(int j=0; j<M; ++j){
                if(matrix[i][j]-'0'==value){
                    int icost, jcost;
                    icost = min(i, N-i);
                    jcost = min(j, M-j);
                    ans   = min(ans, icost+jcost);
                }
            }
        }
        if(ans == N*M+1) return -1;
        return ans;
    }
};
------------------------------------------


各要素について0行、0列に持ってくるのにそれぞれ必要な最小手数を合計する。
これの最小値が求める答え。

手の運動。286点。

SRM476 Div2 Medium(500)

N匹のアナグマ(1<=N<=50)がいる。
i番目のアナグマは、個々ではhunger[i]の値だけの食糧を消費するが、
他のアナグマがいると、他のアナグマ一匹につき追加でgreed[i]の値だけの食糧を追加で消費する。
totalFoodを超えない範囲で飼育可能なアナグマの数の最大値を求めよ。

-------------------------------------------------------------------
#include <vector>
#include <algorithm>
using namespace std;
struct Badgers{
    int feedMost(vector <int> hunger, vector <int> greed, int totalFood){
        int N = hunger.size();
        for(int i=N; 0<i; --i){
            vector<int> tot(N, 0);
            for(int j=0; j<N; ++j) tot[j] = hunger[j]+(i-1)*greed[j];
            sort(tot.begin(), tot.end());
            int cost = 0;
            for(int j=0; j<i; ++j) cost += tot[j];
            if(cost<=totalFood) return i;
        }
        return 0;
    }
};
-------------------------------------------------------------------

Nがせいぜい50なので、Nを決め打ちして、実際にN匹飼育可能かどうかを判定する。
各アナグマが消費する食糧は hunger[i]+(N-1)*greed[i] で与えられるので、並べ替えて下からN個の総和を見てtotalFood以下であればOK.

トイレで解いて362点。

SRM478 Div2 Medium(500) CarrotJumping

xの数直線があり、 xの値が1000000007で割り切れる位置に人参が植えてある。
0 < x < 1000000007 のどこかにウサギがいる。
ウサギはジャンプ一回毎に 4x+3 または 8x+7 の位置に移動できる。
ウサギがジャンプ100000回以内で人参の位置に到達できる場合は最小のジャンプ回数を、到達できない場合は-1を返せ。

---------------------------------------------------
#include <cmath>
#include <algorithm>
using namespace std;

struct CarrotJumping{
    unsigned long long P;

    unsigned long long modularexp(unsigned long long e, unsigned long long x){
        unsigned long long ans = 1;
        for(unsigned long long mo = e; mo>0; mo>>=1){
            if(mo & 1ULL) ans = (ans*x)%P;
            x = (x*x)%P;
        }
        return ans;
    }

    int theJump(int init){
        P = 1000000007ULL;
        unsigned long long inv = modularexp(P-2ULL, init+1);

        unsigned long long DN = 1;        
        for(unsigned long long N = 1; N<=100000ULL; ++N){
            DN = (DN*4ULL)%P;
            unsigned long long j=N-2; if(N==1) j = 0;
            unsigned long long Y=DN * modularexp(j, 2);
            for(;j<=N;){
                for(;Y < inv; ++j) Y <<= 1;
                if(j<=N && Y % P == inv) return N;
                for(;Y <   P; ++j) Y <<= 1;
                Y %= P;
            }
        }
        return -1;
    }
};
---------------------------------------------------

ショートジャンプ(4x+3)の回数をn, ロングジャンプ(8x+7)の回数をmとおくと、ウサギの位置posは
pos = 4^n * 8^m * (x+1) - 1 = 2^m * 4^N * (x+1) - 1  (N := n+m)
と書ける。
pos ≡ 0 mod P を満たす位置に人参があるので、上式より
pos+1 = 2^m * 4^N * (x-1) ≡ 1 mod P.
そして、 x-1 のモジュラ逆数Z( 実は(x-1)^(P-2) ) を用いると
2^m * 4^N = 2^(2N+m) ≡ Z mod P
と書き換わる。
よって、ベキ剰余計算で 2^(2N+m) mod P の値を片っ端から調べていけばよい。

2N+mの値が等しい(N, m)の組み合わせは同一視できるので、
調べるべき組み合わせの数は、 2N+m が 1<=N<=100000, m<=N の制限のもとでとりうる場合の数に等しい。
そしてこれは高々 300000 個にすぎないので、全部やっても余裕で間に合う。

[各Nについて2N+mがとりうる範囲の図：理解はフィーリングで]
N
1-**
2---***
3-----+***
4-------++***
5---------+++***
6------------++++***

結局各Nについてたった3通り(j=N-2, N-1, N)調べればよいことになる。
N=1のみ例外であることに注意。

全然わからなかった。 150点(最低点)。
調べる(N, m)の範囲がかなり重複するので結局１つオーダーが落ちることに気づくのが遅すぎて参った。

*追記
上に貼った解はオーダーがO(N^2)であることを前提にした解なので色々汚い。
O(N)を前提としてきちんと考えた解は下に。といってもNlogNだが・・・
---------------------------------------------------
#include <algorithm>
using namespace std;

struct CarrotJumping{
    unsigned long long P;

    unsigned long long modularexp(unsigned long long e, unsigned long long x){
        unsigned long long ans = 1;
        for(unsigned long long mo = e; mo>0; mo>>=1){
            if(mo & 1ULL) ans = (ans*x)%P;
            x = (x*x)%P;
        }
        return ans;
    }

    int theJump(int init){
        P = 1000000007ULL;
        unsigned long long inv = modularexp(P-2ULL, init+1);
        
        for(int N = 1; N<=100000; ++N) for(int m=N; N-2<=m && 1<2*N+m; --m)
            if(inv == modularexp((unsigned long long)(2*N+m), 2ULL)) return N;
        return -1;
    }
};

SRM479 Div2 Medium(500) TheCoffeeDivTwo



-----------------------------------------------------
#include <algorithm>
#include <vector>
using namespace std;

struct TheCoffeeTimeDivTwo{
    int find(int n, vector <int> tea){
        sort(tea.begin(), tea.end());
        vector<int> coffee(0);
        for(int i=1; i<=n; ++i){
            int j;
            for(j=0; j<tea.size(); ++j){
                if(tea[j]==i) break;
            }
            if(j==tea.size()) coffee.push_back(i);
        }
        
        int ans = 0;
        for(int i=coffee.size()-1; 0<=i;){
            int j = max(i-6, 0);
            ans += 2*(coffee[i]) + 4*(i-j+1) + 47;
            i = j-1;
        }

        for(int i=tea.size()-1; 0<=i;){
            int j = max(i-6, 0);
            ans += 2*(tea[i]) + 4*(i-j+1) + 47;
            i = j-1;
        }
        return ans;
    }
};
-----------------------------------------------------

本来ならEasyレベルの問題だが・・・ 215点。

なぜか vector<T>::iterator find(vector<T>::iterator, vector<T>::iterator, T) が使えなくて焦りまくった。

SRM481 Div2 Medium(500) ChickenOracle

"卵が先"か"鶏が先"という問題が解決したという。
答えを知っているというn人に尋ねた結果、eggCount人が"卵"と答えた。
さてn人のうちlieCount人はウソの答えを教えられており、
またn人のうちliarCount人はウソつきであり自分が知っている答えの逆を言うことが分かっている。
以上の情報を元にして卵か鶏かを確定できるか？
・どちらもありうる場合 => "Ambiguous"
・卵のみありうる場合 => "The egg"
・鶏のみありうる場合 => "The chicken"
・どちらもありえない場合 => "The oracle is a lie"
と答えよ。

--------------------------------------------------------------------
#include <string>
#include <algorithm>
using namespace std;

struct ChickenOracle{
    string theTruth(int n, int eggCount, int lieCount, int liarCount){
        int lower, upper, sum;
        sum   = liarCount + lieCount;
        upper = min(liarCount, lieCount);
        lower = max(0, liarCount + lieCount - n);
        bool E, C;
        E = ( sum - 2*upper <= n-eggCount && n-eggCount <= sum - 2*lower && (n-eggCount) % 2 == sum % 2 );
        C = ( sum - 2*upper <=   eggCount &&   eggCount <= sum - 2*lower && (  eggCount) % 2 == sum % 2 );
        if( E &&  C) return "Ambiguous";
        if( E && !C) return "The egg";
        if(!E &&  C) return "The chicken";
        return "The oracle is a lie";
    }
};
--------------------------------------------------------------------

正解が存在すると仮定すると、n人の人間は2種に分類できる。
（１）　正解を知っていて、かつ正直　or　ウソを教えられたウソつき
（２）　ウソを教えられた正直者　or　世界を知っているウソつき

（１）の人間は必ず正解を答え、（２）の人間は必ず不正解を答える。
よって、（２）の人間の数を計算し、それが不正解者数に一致しうるかどうかを判定することになる。


（１）の人間のうち、「ウソを教えられたウソつき」の数を m とすると、
 max(0, lie + liar - n) <= m <= min(lie, liar)
が成り立つ。
上式の左辺をU、右辺をLとする(U <= m <= L)。

（２）の人間の数は
 「不正解を言う可能性のある人間」-「ウソを教えられたウソつき」
=(lie + liar - m) - m = S - 2m (S := lie + liar)
なので、上の不等式を用いて
S - 2U <= S - 2m <= S - 2L
が成り立つ。
不正解者数 = S - 2m になればよいので、
条件：　S - 2U <= 不正解者数 <= S - 2L
をチェックすればよい。
ただし、 m に2がかかっていることから、 「Sと不正解者数の偶奇が一致する」という条件も必要になる。

偶奇の一致を忘れて150点。

SRM 404 Div2 Medium(500) RevealTriangle

下図のような三角形がある（*=0-9）

****
***
**
*

各要素をa[i][j]と書くことにすると、 a[i][j] = (a[i-1][j] + a[i-1][j+1]) mod 10 が成り立っている。

各列について1つを除いてすべての要素が'?'でマスクされた三角形が与えられるので、
すべての'?'を除去して元の三角形を復元したものを答えよ。

-----------------------------------------------------------------
#include <string>
#include <vector>
using namespace std;

struct RevealTriangle{
    vector <string> calcTriangle(vector <string> questionMarkTriangle){
        vector<string> QMT = questionMarkTriangle;
        int N = QMT.size();
        for(int i=N-2; 0<=i; --i){
            int M = N-i;
            int clared = 0; for(;QMT[i][clared]=='?'; ++clared);
            for(int j=clared-1; 0<=j; --j) QMT[i][j] = ((QMT[i+1][j]-QMT[i][j+1]) + 10) % 10 + '0';
            for(int j=clared+1; j< M; ++j) QMT[i][j] = ((QMT[i+1][j-1]-QMT[i][j-1]) + 10) % 10 + '0';
        }
        return QMT;
    }
};
-----------------------------------------------------------------

a[i][j] = (a[i-1][j] + a[i-1][j+1]) mod 10

より、

a[i-1][j] = (a[i][j] - a[i-1][j+1] + 10) mod 10
a[i-1][j+1] = (a[i][j] - a[i-1][j] + 10) mod 10

が成り立つ。
よって、
「i列目が全て判明していれば、既に判明している要素a[i][k]を用いてi-1列目の要素も全て復元できる。」
最下列は必ず判明しているので、上記を帰納的に適用していけば全ての'?'が除去できる。

342点。

SRM406 Div2 Medium(500) FactoVisors

与えられた整数配列 divisors の全要素の倍数であり、
かつ与えられた整数配列 multiples の全要素の約数であるような整数はいくつあるか？

---------------------------------------------------------
#include <vector>
#include <cmath>
using namespace std;

struct FactoVisors{
    unsigned long long gcd(unsigned long long x, unsigned long long y){
        if(y>x) return gcd(y, x);
        unsigned long long z=1ULL;
        for(;z>0ULL;){
            z = x % y;
            x = y; y = z;
        }
        return x;
    }

    int getNum(vector <int> divisors, vector <int> multiples){
        int N = multiples.size();
        unsigned long long cd = multiples[0];
        for(int i=1; i<N; ++i) cd = gcd(cd, multiples[i]);
        
        N = divisors.size();
        unsigned long long cm = divisors[0];
        for(int i=1; i<N; ++i){
            unsigned long long d = gcd(cm, divisors[i]);
            cm = cm * divisors[i] / d;
            if(cm>cd) return 0;
        }
        
        if(cd % cm != 0) return 0;
        cd /= cm;
        
        int ans = 1;
        for(;cd%2==0; cd/=2) ++ans;
        int sup = sqrt(cd);
        for(int i=3; i<=sup; i+=2){
            if(cd % i == 0){
                int k = 1;
                for(;cd%i==0; cd/=i) ++k;
                ans *= k;
            }
        }
        if(cd>1) ans *= 2;
        return ans;
    }
};
---------------------------------------------------------

複数の数の最大公約数(GCD)は、
どれか2つのGCDを求める->そのGCDと他の数のGCDを求める
という手続きを繰り返すことで得られる。
最小公倍数(LCM)も同様。AとBのGCD、LCMについては次の式が成り立つ：
GCD * LCM = A * B
ので、これよりLCMも簡単に求められる。

divisors全体のLCMを Y,
multiples全体のGCDを X とおく。
条件を満たす数nは Xの約数 AND Yの倍数なので、このような数が存在するにはX mod Y ≡ 0 が必要。
そしてこのとき、nの数は X/Y の約数の個数に等しい。

***

ある数をその素因数の集合（重複を許す）として表現すると、
２つの数のGCDは２つの集合の積集合として表せる。
公約数は積集合に包含される集合となる。

LCMの場合は和集合で、任意の公倍数は和集合を包含する集合として表される。

SRM481 Div2 Medium(500) LockersDivTwo ( Div1 Easy(250) LockersDivOne でも可)　

1～Nの番号のついたドアの閉じたロッカーがN個、一列に並んでいる。
まず1番から始めて、閉じたロッカーを1つ飛びに（すなわち１，３，５，…と）開けていく。
次に、「残りの」閉じたロッカー（すなわち２，４，６、・・・）について、今度は2つ飛びに開けていく。
これを繰り返した時、最後に開けられるロッカーの番号を答えよ。

---------------------------------------------
struct LockersDivTwo{
    int lastOpened(int N){
        int n=2;
        for(;N-N*(n-1)/n>1; ++n) N = N*(n-1)/n;
        --n;
        int last = N-1;
        for(;n>1;--n) last = last*n/(n-1)+1;
        return last+1;
    }
};
---------------------------------------------

スカラーだけで、かつO(N) (もっと小さい？) でやる方法。
(Div1Easyはこの問題のN<=2000000の場合だったので、この方法じゃないとダメなようだ。
->そうでもなかった。)

簡単のため番号を0から数えることにする。

0, 1, ..., k, k+1, ... と番号のついたロッカーを n-1個飛ばしで開けていく場合、
残るロッカーの番号は整数j, mを用いて nj + m (j>=0, n>m>=0) と書ける。
nj + m の隙間を詰めて連続した整数にするためには、
(nj + m) * (n-1) / n とすればよい。
= ( n(n-1)j + (m-1)n + (n-m) ) /n = (n-1)j + (m-1) となる。
この作業の逆変換は、 (nj + m) * (n-1) / n = M として M * n / (n-1) + 1である。
= ((n-1)j + (m-1)) * n / (n-1) + 1 =  ( n(n-1)j + (m-1)(n-1) + (m-1) ) / (n - 1) + 1
= nj + (m-1) + 1 = nj+m となる。

さて、ロッカーを次々開けていくと、飛ばしの数 n が残った閉ロッカーの数(Lとする)を上回る。
こうなると、以降は残ったロッカーを前から1つずつ開けていくだけになるので、最後に開けるのはこの時最後尾にあるロッカーである。
このロッカーは(L-1)番目にあるので、上に書いた手段を用いて逆変換していけば、このロッカーが最初にいた位置が分かる。

***

時間かけすぎ。215点。

Div1EasyのSystemTestにかけたら全ケースで1ms以下だったので、速度はおそらくO(N)より小さいが正確に見積もるのがめんどくさい。
->n=iのときのNをN[i]とすると、N[i] = N[1]/i = N/i.
nのカウントアップの終了条件はN[i]-N[i+1]>1なので、上記を代入すると
N[1](1/i - 1(i+1)) = N[1]/i(i+1) > 1. -> だいたい n = √N 程度となる。
よって O(√N) かな？

SRM433 Div1 Easy(250) MagicWords

文字列集合Sと整数Kが与えられる。Sの各要素を連結して1つの文字列を作るとき、
この文字列がKについて以下に示す"Magic Word"の条件を満たすような連結の仕方は何通りあるか？
なお Sの要素数 <= 8 であり、与えられる文字列の長さはそれぞれ20以下.

*文字列Tが整数KのMagic Wordである条件
Tの長さをLとして、T[i] = T[(i+j)%L] が成り立つような j がちょうどK個あること

------------------------------------------------
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
struct MagicWords{
    int count(vector <string> S, int K){
        int N = S.size(), L=S[0].length();
        vector<int> I(N-1, 0);
        for(int i=1; i<N; ++i){
            I[i-1] = i ;
            L += S[i].length();
        }

        if(L%K != 0) return 0;

        int ans = 0;
        do{
            string s = S[0]; for(int i=1; i<N; ++i) s += S[I[i-1]];
            string t = s + s;
            int k = K-1;
            for(int i=1; i<L; ++i){
                if(s == t.substr(i,L)) --k;
                if(k<0) break;
            }
            if(k==0) ++ans;
        } while(next_permutation(I.begin(), I.end()));
        return ans*N;
    }
};
------------------------------------------------

基本的には順列をシミュレーションする。
ただし円順列なので端を固定して考えることができて、これで計算量が最大1/8になる。

135点。

SRM434 Div1 Easy(250) FindingSquareInTable

文字列ベクタtableの各文字は'0'-'9'からなる。
i, j がそれぞれ等差数列となるようにして table[i][j]の文字を結合し、これを整数として見る。
この手続きで得られる整数のうち最大の平方数を求めよ。存在しない場合は-1を返せ。

-------------------------------------------------------------------
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
using namespace std;

struct FindingSquareInTable{
    bool check(int x){
        if(x==0) return true;
        int y = sqrt(x);
        if(y * y == x) return true;
        return false;
    }

    int findMaximalSquare(vector <string> table){
        int N = table.size(), M = table[0].length();
        
        long long ans = -1;
        long long cor;
        for(int b=0; b<N; ++b) for(int a=-b-1; a<=N-b; ++a) for(int d=0; d<M; ++d) for(int c=-d-1; c<=M-d; ++c){
            cor = 0;
            if(a==0 && c==0) continue;
            for(int i=0; ; ++i){
                if(a*i+b < 0 || a*i+b >= N || c*i+d < 0 || c*i+d >= M) break;
                cor += (table[a*i+b][c*i+d]-'0');
                if( check(cor) ) ans = max(ans, cor);
                cor *= 10;
            }
        }
        return ans;
    }
};
-------------------------------------------------------------------

SRM301 Div2 Hard(1000) CorrectingParenthesization

"()[]{}"の6文字からなる偶数長さの文字列が与えられる。
三種類のカッコがそれぞれ整合した文字列または空文字列を"well formed"であるという。
与えられた文字列をwell formedにする為に必要な文字変換回数の最小値を答えよ。

( "([)]" みたいなのはwell formedとは言わない。)
----------------------------------------------------------
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct CorrectingParenthesization{
    bool areOK(char a, char b){
        if(
            (a == '(' && b == ')') ||
            (a == '[' && b == ']') ||
            (a == '{' && b == '}')
        ) return true;
        return false;
    }

    bool isOpen(char a){
        if(
            a == '(' ||
            a == '[' ||
            a == '{'
        ) return true;
        return false;
    }

    bool isClose(char a){
        if(
            a == ')' ||
            a == ']' ||
            a == '}'
        ) return true;
        return false;
    }

    int getMinErrors(string s){
        int N = s.length();
        if(N==0) return 0;
        vector<vector <int> > DP(N, vector<int>(N, N));
        for(int L=2; L<=N; L+=2){
            for(int i=0; i+L-1<N; ++i){
                int cost = 0;
                char a= s[i], b = s[i+L-1];
                if(areOK(a, b)) cost = 0;
                else{
                    cost = 1;
                    if(isClose(a) && isOpen(b)) ++cost;
                }
                if(L>2) cost += DP[i+1][i+L-2];
                DP[i][i+L-1] = cost;
                for(int k=i+1; k<=i+L-3; k+=2){
                    DP[i][i+L-1] = min(DP[i][i+L-1], DP[i][k]+DP[k+1][i+L-1]);
                }
            }
        }

        return DP[0][N-1];
    }
    
};
----------------------------------------------------------

まず、well formedな文字列はその定義から必ず長さが偶数になる。
そこで、長さL(=2n)の文字列をwell formedにするために必要な置換の回数を考える。
i,jについて、
位置iから位置jまでをwell formedにするための最小コストを<i, j>、
位置i と 位置jの カッコ を 対応させるための最小コストを[i, j]とすると、

(i, L-1) = min{ [i,L-1] + <i+1,L-2>, <i,k> + <k+1,L-1> } k: i+1 -> L-3

が成り立つ。
そこで、L: 2 -> N(全体の長さ), i: 0 -> N-L としてDPを行うと、(0, L-1)が答えになる。

***

O(N^3)でございますな。
あと偶数云々はべつにessentialではない。