OneRegister +はレジスタを2倍にする演算子、-はレジスタを0に、*はレジスタを2乗、/はレジスタを1に。-は使わないし、/を使うのは最初のみ。後は+と*を全探索すれば最低でも2倍になるのですぐにtの値を超えるはず。 #include <string> using namespace std; string </string>…

Easy (300) 180.89 デバッグに時間がかかった orz Medium (450) Failed System Test ピボットで分けてからそれぞれをソートするプログラムではなく、ピボットの両端をソートしてからマージするプログラムを書く。何となく変だという気はしたもののサンプルの…

Old Berland Language短い順に単語を割り当てていく。例えば長さが、3, 3, 3, 5, 5ならば、 000 001 010 01100 01101多倍長整数を使うと楽。 N = input() l = map(int,raw_input().split()) ans = [""]*N c = 0 d = 0 while True: p = -1 for i in range(N):…

Computer Gameそのときに詠唱可能な最も強い呪文を唱える。NOとなるのは、ボスのHPが減らないかつ新たに唱える呪文が無い場合。ボスのHPが減らないだけだと↓の入力にNOを返してしまう。 3 100 29 100 10 100 10 100 10import itertools N,max,reg = map(int,…

Towers input() l = map(int,raw_input().split()) print max([l.count(x) for x in l]), len(set(l))

久しぶりに参加。 A 480 B System Test Failed C 1098 結果 160位 1672 → 1681

Cosmos線分で分割されたグループ内で白とピンクのコスモスが同じ数になるように線分を結んでいけば良い。単純に実装すると50点。予めp番目までで白いコスモスが何本多いかを計算しておいて計算量を線形にすれば100点。けっこう制限時間が厳しい気がする。que…

Banksia例えば問題文中の図1のトーナメントだと、4より確実に強いのは4に勝った1と4に勝った1に勝った5。トーナメント表を辿っていて出てくる人は自分よりも強い。そのような人がK人未満なら上位K人の可能性がある。 #include <iostream> #include <vector> #include <algorithm> using na</algorithm></vector></iostream>…

Anemone1型のグラフはこんな感じ ∧ 2型は ∧∧ 3型は ∧∧∧∧ n型のアネモネの成長度のグラフは2n-1個の山を持つ。k=1となるのは2n-1回、0<k<1となるのは2n回、k=0となるのは2n-1回。ここまでで、30点。p=0が入力された場合には1より大きい任意の値をkとする。 #include <iostream> using namespace std; int main() { int p; cin >> p; if ( p == 0 ) { cout<<"1 2.0"<</k<1となるのは2n回、k=0となるのは2n-1回。ここまでで、30点。p=0が入力された場合には1より大きい任意の値をkとする。>

面白いそうなコンテストがあると聞いて夜の部に参加。 A 100/2B 100/1C 100/4D 15/1E 60/1F ---/-結果 375/647 5位 思いの外、調子が良かった。この順位は昼の部も含めてらしい。部分点というのが面白い。

RectangleAvoidingColoringDiv2より最大サイズが大きいので、そのままでは幅が1と2の場合が間に合わない。幅が1の場合は任意の色が塗れるので?の個数をcとして2c。幅が2の場合は、WWとBBという塗り方を高々1つ含みそれ以外はWBかBWと塗る方法の個数を動的計…

RectangleAvoidingColoringEasy盤面が大きい場合はrectangle-avoidingに塗ることができないので0を返す。小さい場合は探索。 #include <string> #include <vector> using namespace std; vector<string> B; int N, M; int BT() { for ( int a=0; a</string></vector></string>

AfraidOfEvena[i+1]-a[i]<a[i]-a[i-1]ならばa[i]を2倍に、そういうiが無くなりa[N-1]-a[N-2]>a[N-2]-a[N-3]ならばa[N-1]を2倍に、と繰り返す。それで駄目ならa[0]を２倍にして最初から。としても解けるけど、そんな面倒なことをする必要は無いと教わった。等差数列は、 偶偶偶偶…… 偶奇偶奇…… 奇偶奇偶…… 奇奇奇奇…… のいずれ</a[i]-a[i-1]ならばa[i]を2倍に、そういうiが無くなりa[n-1]-a[n-2]>…

MicrowaveSelling int attract( int n ) { int c = 0; for ( ; n%10==9; n/=10 ) c++; return c; } class MicrowaveSelling{public: int mostAttractivePrice( int minPrice, int maxPrice ) { int ans = 0; int att = -1; for ( int i=maxPrice; i>=minPric…

Easy (250) 0 System Test Failed。簡単な解き方に気付かなかったとはいえミスしなければ通っていた。残念。 Medium (500) 225.25 Hard (1000) 0 Challenge +50 Mediumで幅が2の場合に探索している人が居たので撃墜。 結果 1710 → 1839 満足。

Fractal input = open("input.txt","r") output = open("output.txt","w") n,k = map(int,input.readline().split()) S = list(input) for y in range(n**k): s = "" for x in range(n**k): c = "." tx,ty = x,y for i in range(k): if S[ty%n][tx%n]=="*": …

Extra-terrestrial Intelligenceファイル入出力だとデバッグが地味に面倒。 input = open("input.txt","r") output = open("output.txt","w") input.readline() if len(set(input.readline().split("1")[1:-1])) <= 1: output.write("YES") else: output.wri…

CubeColoring頂点0,2,5,7の色を決めれば、頂点1,3,4,6の色は独立に選べる。 #include <string> #include <vector> using namespace std; class CubeColoring{public: long long theCount( vector <string> colors ) { int n = (int)colors[0].length(); long long c = 0; for ( int v</string></vector></string>…

NumberMagicEasy #include <string> class NumberMagicEasy{public: int theNumber( string answer ) { int r = 0; for ( int i=0; i<4; i++ ) r = r*2 + ( answer[i]=='Y' ? 0 : 1 ); return r + 1; }};</string>

PuyoPuyo例えばL=4のとき、長さnの全消しできるぷよの並びは、 ○××○××○××○□□ と表せる。ただし、××と□□は長さ0以上n未満の全消しできるぷよの並びで、××は消している途中に○が底に付かない。長さと全消し中に底に付くぷよの色数ごとに全消しできる並びの数を…

RabbitNumberS(n+m)≦S(n)+S(m)。等号成立はn+mの計算で繰り上がりが発生しないとき。x=Σdi10iとすると、S(x)*S(x)=ΣiΣjdidj。筆算を考えれば、繰り上がりが発生しないときS(x*x)=S(x)*S(x)。その必要条件は任意のiについてdi≦3。 int next( int n ) { n++; i…

不参加。

Bribes賄賂の効力は指数的に減少するので、ある程度離れた人には影響しない。i番目の有権者の周囲への賄賂の配り方をjとして、i番目までの有権者が折れる最小の贈賄回数を記憶し、動的計画法。 #include <vector> #include <algorithm> using namespace std; int countbit( int </algorithm></vector>…

BestApproximationDiv2○○Div1と○○Div2があったらDiv2の方が簡単かと思いきや、今回はDiv2の方が難しい。numberの長さがintで扱いきれないので自前で割り算を実装。O(maxDen2)では間に合わないので、Bの値からAの値を計算。 #include <string> using namespace std; i</string>…

MovieSeatingnumFriends=1の場合を別に扱う必要がある。 #include <string> #include <vector> using namespace std; long long P( int n, int m ) { long long r = 1; for ( int i=0; i<m; i++ ) r *= n-i; return r; } class MovieSeating{public: long long getSeatings( int numFriends, vector <string> hall ) { int h = (int)hall.…</m;></vector></string>

DigitHoles class DigitHoles{public: int numHoles( int number ) { int hole[] = { 1, 0, 0, 0, 1, 0, 1, 0, 2, 1 }; int ans = 0; for ( ; number>0; number/=10 ) ans += hole[number%10]; return ans; }};

BestApproximationDiv1A,Bの取り得る範囲を全部試しても間に合う。ただ誤差が怖い。本番の時はコメントアウトしているコードで通ったけど、例えば"%.10f"を"%.20f"とすると、 Problem: 250 Test Case: 10 Succeeded: No Execution Time: 221 ms Args: {656, …

Easy (250) 216.83 Medium (500) 0 Hard (900) 0 Challenge 0 Easyはfor(A=1;A

A decorative fence分からないのでカンニング。なるほど、途中まで板の長さを決めたときに残りの板の選び方が何通りあるかを先にDPで求めておくのか。 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { const int M = 20; // [i][j][k] 残</algorithm></vector></iostream>…

Spell checker手抜きで編集距離=1としたらTLEだった。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; bool replace( string a, string b ); int main() { vector<string> dict; while ( true ) { string s; cin >> s; if ( s == "#" ) break; dict.</string></algorithm></vector></string></iostream>…