ColorfulCardsなるべく小さな数字を選んだとときと大きな数字を選んだときの数字が一致すればその数字、一致しなければ-1。 #include <string> #include <vector> using namespace std; class ColorfulCards{public: vector <int> theCards( int N, string colors ) { int n = (in</int></vector></string>…

CarrotBoxesEasy #include <vector> #include <algorithm> using namespace std; class CarrotBoxesEasy{public: int theIndex( vector <int> carrots, int K ) { int m = 0; for ( int i=0; i</int></algorithm></vector>

CarrotBoxes強連結成分分解して、他から情報が得られない成分のみ開ければ良い。そのような成分の個数をxとすると成功する確率は(N-x)/N。ただし、最後に回すことで箱が１つだけ残るような成分があれば、その箱を開けずとも空と分かるので、確率は(N-x+1)/N…

Pythonだと、 v1 = ["foo","bar","baz"] print v1 で ['foo', 'bar', 'baz']になるのに、C++で同じ事はできなくてデバッグがちょっと面倒だと思っていたけど、自分で書けば良いのか。 template <class T>ostream &operator<<(ostream &o,const vector<T>&v) {o<<"{";for(</t></class>…

Easy (275) 192.91 Medium (500) 0 Hard (975) 0 Challenge 0 結果 1737 → 1782(｀･ω･´)

Array2nCn-n。 小さいnに対して実際に調べて、OEISに訊いた。 理由を考えてみる。n個の数字からn個を選ぶ重複組合せは2n-1Cn通り。選んだ数字を昇順と降順に並べることでbeautiful arrayが得られる。22n-1Cn=2nCn通り。ただし、これは全てが同じ数字の数列を…

Martian ArchitectureChrisが興味を持っている場所だけ調べる。PythonだとTLE。 #include <iostream> #include <vector> using namespace std; int main() { int n,m,k; cin >> n >> m >> k; vector<int> a(m), b(m), c(m); for ( int i=0; i<m; i++ ) cin >> a[i] >> b[i] >> c[i]; long long ans </m;></int></vector></iostream>…

Square Earth? def d(n,x,y): if y==0: return x if x==n: return n+y if y==n: return 3*n-x if x==0: return 4*n-y return -1 n,x1,y1,x2,y2 = map(int,raw_input().split()) d1 = d(n,x1,y1) d2 = d(n,x2,y2) print min(abs(d2-d1),4*n-abs(d2-d1))

A 482 B 860 C 1128 Hack +100 Cでn≦100000のところn≦1000と勘違いしている人が居たのでHack。 結果 59位 1856 → 1944 (｀･ω･´)

InterestingParty #include <string> #include <vector> using namespace std; class InterestingParty{public: int bestInvitation( vector <string> first, vector <string> second ) { int n = (int)first.size(); int ans = 0; for ( int i=0; i</string></string></vector></string>

AlternatingLane例えば木の高さが1,3,6,9,7,5だったとすると、高さが3,6,7の木を切り倒すので、美しさは単に隣り合う木の高さの差の和。それぞれの木の高さは独立だから、 Σ1≦i≦n-1Σlow[i-1]≦j≦high[i-1]Σlow[i]≦k≦high[i]|j-k|/(high[i-1]-low[i-1]+1)/(hig…

PaintingO(N4)で書いたけど、O(N5)でも間に合うらしい。 #include <string> #include <vector> using namespace std; class Painting{public: int largestBrush( vector <string> picture ) { int N = (int)picture.size(); int M = (int)picture[0].size(); vector<vector<int> > P(N,vector<int>(M,1</int></vector<int></string></vector></string>…

Easy (250) 151.98 Medium (500) 0 Hard (1000) 0 Challenge 0 結果 1784 → 1737(´･ω･｀)

First or Last動的計画法。t番目の曲がり角で抜いたときのクラッシュの確率をp1[t]、抜かなかったときのクラッシュの確率をp2[t]、直後にr番目である確率をP[t][r]とすると、 P[t][r] = max(P[t-1][r+1]*(1-p1[t]),P[t-1][r]*(1-p2[t]))。 Pythonだと分数が…

After the Dance Battle幅優先探索。 #include <iostream> #include <vector> #include <string> #include <utility> using namespace std; int main() { int N; cin >> N; for ( int testcase=0; testcase<N; testcase++ ) { int R, C; cin >> R >> C; vector<string> M(R); for ( int i=0; i<R; i++ ) cin >> M[i]; int sx, sy;…</r;></string></n;></utility></string></vector></iostream>

AmoebaDivTwo #include <string> #include <vector> using namespace std; class AmoebaDivTwo{public: int count( vector <string> table, int K ) { int w = (int)table[0].size(); int h = (int)table.size(); int ans = 0; for ( int y=0; y</string></vector></string>

AmoebaCode動的計画法。何個か前までの数字を組み合わせごとに最小の距離を覚えておく。答えはK以下なので、K-1個前までに数字が出てこなければK個前に数字が出てきたとみなして構わない。↓のdのループをd<=Kから、d<P[j]にしたら間に合うようになった。P[j]の値が大きくなるjはそんなに多くない。 #include <string> #include <vector> #include <algorithm> using namespace st</algorithm></vector></p[j]にしたら間に合うようになった。p[j]の値が大きくなるjはそんなに多くない。>…

StonesGame普通のニムと違って１手前の状態に戻すことが可能なので、双方が最善を尽くして３手目以降に決着が付くことはない。 #include <string> using namespace std; bool check( int N, int M, int K, int L ) { return abs(L-M)%2 != K%2 && 2*max(M-K+1,1)+K-M</string>…

Easy (300) 0 Medium (450) 0 Hard (1000) 0 Challenge 0 結果 1872 → 17840点(´･ω･｀)

First Digit Law先頭が1である確率は[L,R]の範囲内で先頭が1であるものの個数を(R-L+1)で割れば求まる。ちょうどk個が1である確率を動的計画法で求めて足しあわせる。1018は入るけど、1019はsigned long longから溢れる。Pythonだとそういうことを気にしなく…

Cutting Jigsaw Puzzle約数の個数はそんなに多くないので全通り試しても間に合う。 def rotate(p): w,h = len(p[0]),len(p) r = [] for y in range(w): r += [[]] for x in range(h): r[-1] += [p[x][w-y-1]] return r A,B = map(int,raw_input().split()) P…

Presents N,K = map(int,raw_input().split()) C = [0]+map(int,raw_input().split())[1:]+[N+1] print sum([1+(C[i]-C[i-1]-1)/K for i in range(1,len(C))])-1

A 464 B 820 C 924 結果 61位 1787 → 1856 自己最高レート。

TimeTravellingTourA→B→C→D―(タイムマシン)→B→E という移動はBの時点でCとEに分岐して調査すると考える。都市iから開始してcities[j..k]を調査するコストをc[i][j][k]とすると c[i][j][k] = min( {c[l][i][k]+road[i][j][k]}∪{c[i][j][m]+c[i][m+1][k]} )。 …