Let's Go Rolling!動的計画法。ビー玉の位置でソートして、左から順に、ビー玉をある位置で止めるときに必要な金を求める。 #include <iostream> #include <vector> #include <utility> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<pair<int,int> > m(n); for ( int i=0; i<n; i++ ) cin >></n;></pair<int,int></algorithm></utility></vector></iostream>…

Vasya the Architect積み上げたレンガの重心が下のレンガの外側にあると塔が崩れる。引っかかりどころがたくさん。 誤差が怖いので整数で計算。 入力がx1>x2という場合もある。 レンガは1つずつ積む。例えば↓の入力は3個目のレンガを乗せれば安定するけど、2…

Blinds長さxの帯が何本切り取れるかをxの値を変えながら調べる。 n,l = map(int,raw_input().split()) a = map(int,raw_input().split()) ans = 0 for x in range(l,max(a)+1): ans = max(ans,sum([t/x*x for t in a])) print ans

Chess全ての置き場所を試しても余裕で間に合う。 t = raw_input() r = (ord(t[0])-ord("a"))+(ord(t[1])-ord("1"))*1j t = raw_input() k = (ord(t[0])-ord("a"))+(ord(t[1])-ord("1"))*1j move = [-1+2j,1+2j,2+1j,2-1j,1-2j,-1-2j,-2-1j,-2+1j] c = 0 for …

Army input() d = map(int,raw_input().split()) a,b = map(int,raw_input().split()) print sum(d[a-1:b-1])

A + 00:06 B + 00:22 C +1 00:42 D +6 03:28 E +1 01:10 結果 109位 1681 → 1745 Dにハマったのが痛かったが、レーティング上がったし満足。

TxMsgDiv2 250にしては面倒な気がする。 #include <string> #include <sstream> using namespace std; class TxMsg{public: string getMessage( string original ) { bool vowel[256] = { false }; vowel['a'] = vowel['e'] = vowel['i'] = vowel['o'] = vowel['u'] = true; s</sstream></string>…

QuickSortLの値を1〜len(L)の連続した値に置き換えて考えると、quick-sort(L)に渡されるLは常に連続した値である。そのようなLはn(n-1)/2通りしかない。 #include <vector> #include <algorithm> using namespace std; const int N = 50; static double memo[N+1][N+1]; double </algorithm></vector>…

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…

不参加。