2014-10-14

SRM 636 div 1

SRM

デバッグ用のprintfを消し忘れていたせいでTLEした．つらすぎ

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

int choco[55][55];
int sum[55][55];

class ChocolateDividingEasy{
public:
    int h,w;
    int S(int a, int b, int x, int y){
        return sum[x][y] + sum[a][b] - sum[x][b] - sum[a][y];
    }
    int findBest(vector <string> chocolate){
        h = chocolate.size();
        w = chocolate[0].size();
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                choco[i+1][j+1] = (int)(chocolate[i][j] - '0');
                sum[i+1][j+1] = sum[i][j+1] + sum[i+1][j] - sum[i][j] + choco[i+1][j+1];
            }
        }
        int ans = 0;
        for(int i = 0; i < h-1; i++){
            for(int j = i+1; j < h-1; j++){ 
                for(int s = 0; s < w-1; s++){
                    for(int t = s+1; t < w-1; t++){
                        //printf("i=%d j=%d s=%d t=%d\n",i,j,s,t);
                        int r = S(0,0,i+1,s+1);
                        r = min(r,S(0,s+1,i+1,t+1));
                        r = min(r,S(0,t+1,i+1,w));
                        r = min(r,S(i+1,0,j+1,s+1));
                        r = min(r,S(i+1,s+1,j+1,t+1));
                        r = min(r,S(i+1,t+1,j+1,w));
                        r = min(r,S(j+1,0,h,s+1));
                        r = min(r,S(j+1,s+1,h,t+1));
                        r = min(r,S(j+1,t+1,h,w));
                        ans = max(ans,r);
                    }
                }
            }
        }
        return ans;
    }
};

2014-10-12

444 div1 easy

SRM

TLEしたので枝刈りしたら通った

# coding: utf-8
def unfold(grid, limit, i, j, n):
    if i - n + 1 < 0:
        return False
    if j + n > len(grid)-1:
        return False
    tri = 0
    for h in range(n):
        if grid[j+h][i+1] == '#':
            return False
        if grid[j+h][i-h] != '/':
            return False
        for w in range(h):
            if grid[j+h][i-w] == '/':
                tri += 1
                if tri > limit:
                    return False
            if grid[j+h][i-w] == '.':
                return False
    for w in range(n):
        if grid[j+n][i-w] == '#':
            return False
    return True

class UnfoldingTriangles:
    def solve(self, grid, unfoldLimit):
        y = len(grid)
        x = len(grid[0])
        g = [[c for c in s] for s in grid]
        g.append(['.' for i in range(x+1)])
        for i in range(y):
            g[i].append('.')
        ans = -1
        for j in range(y):
            for i in range(x):
                for k in range(min(x,y)):
                    k += 1
                    if k > ans and unfold(g, unfoldLimit, i, j, k):
                        ans = k
        if ans == -1:
            return -1
        return ans * (ans + 1) / 2

2014-10-11

SRM 433 div1 easy

SRM

pythonで解いた．C++より気軽に書ける気がする

# coding: utf-8
def distance2(p, q):
    return (p[0]-q[0])**2 + (p[1]-q[1])**2

def isinCircle(c,r,p):
    if distance2(c,p) < r**2:
        return True
    return False

class CirclesCountry:
    def leastBorders(self, X, Y, R, x1, y1, x2, y2):
        p = (x1,y1)
        q = (x2,y2)
        ans = 0
        for c,r in zip(zip(X,Y),R):
            if isinCircle(c,r,p):
                ans += 1
            if isinCircle(c,r,q):
                ans += 1
            if isinCircle(c,r,p) and isinCircle(c,r,q):
                ans -= 2
        return ans

最近，無機化学をすっかり忘れている

2014-09-29

AOJ 1129

AOJ

解いた．後ろから，最終的に一番上になるものだけ見るテクニックを使うと計算量が小さい．

while True:
    n,r = map(int,raw_input().split())
    if n == 0 and r == 0 :
        break
    p = [None] * r
    c = [None] * r
    for i in range(r):
        p[i],c[i] = map(int, raw_input().split())
    top_idx = 0;
    for i in range(r):
        j = r-i-1
        if top_idx < c[j]:
            top_idx += p[j] - 1
        elif top_idx < c[j] + p[j] - 1:
            top_idx -= c[j]
    print n - top_idx

受験勉強の進捗は，数学の記述で減点されるのをなんとかしたいなあという感じ

2014-09-06

SRM 632 div 1

SRM

今回もeasyだけ解いてsystest通った．
解法を思いつくのが遅すぎ
1294 -> 1335
解法は適当な長さだけ答えを埋め込んで各[i,j]に対して一致するかをひたすらチェックするだけ

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int b[] = {0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,7,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0};
class PotentialArithmeticSequence{
public:
    vector<int> D;
    bool ch(int i, int j){
        int ma = 0;
        int p = -1;
        for(int k = i; k <= j; k++){
            if(D[k] > ma){
                p = k;
                ma = D[k];
            }
        }
        if(ma >= 5){
            int idx = 0;
            for(int k = p+1; k <= j; k++){
                if(D[k]!=b[idx]) return false;
                idx++;
            }
            idx = 0;
            for(int k = p-1; k >= i; k--){
                if(D[k]!=b[idx]) return false;
                idx++;
            }
        }else{
            int k;
            for(k = 0; k < 50; k++){
                if(b[k] == ma){
                    break;
                }
            }
            int idx = 1;
            for(int t = p+1; t <= j; t++){
                if(D[t] != b[k+idx]) return false;
                idx++;
            }
            idx = 1;
            for(int t = p-1; t >= i; t--){
                if(D[t] != b[k+idx]) return false;
                idx++;
            }
        }
        return true;
    }
    int numberOfSubsequences(vector <int> d){
        int n = d.size();
        int ans = n;
        D = d;
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++){
                if(ch(i,j)) ans++;
            }
        }
        return ans;
    }
};

2014-08-31

情報オリンピック夏季セミナー2014 参加記

JOI

8/26〜29にJOIss2014参加しました

一日目

新幹線で東京に行く
本決め
「情報理論と符号理論」を希望する
一人だけですぐに決定
joisinoさんともう一人が加わる
第一章を読む
サーディナス・パターソンの定理が強い
壁から人権が生えると思いきや生えない
D棟の一階でしゃべったりする

二日目

第二章と第三章を読む
ハフマン符号の最適性を証明する
シャノンの第一基本定理を証明する
joisinoさんが第二章の解説をする．わかりやすい
stibearさんに人権を提供してもらって夜11時からCFに参加
激冷え
tozanさんにdiv2Dの解説をしてもらう

三日目

8時に起きて危うく朝食を解きそうになる
第四章と第五章を読む
行列怖い
第三章の解説をする．途中で証明の順番を忘れてしまいよくない
発表のテーマどうしようかなあ
六章をちらっと見たらめっちゃ代数してた
交流で頭複数所持ツル（5個）とミウラ折を折る
名札がswapされまくる

四日目

第六章を読む
ガロア体って何だよ…
ハミングの球充填限界式を見る
いいかんじの問題を作ることができたので発表しようと思う
スライドを書き始める
クラフトの不等式とマクミランの不等式の証明をもう一度やる
証明をスライドで説明するの難しすぎでしょ
夜1時ごろに完成した

五日目

デング熱が怖い
発表
Lookingを読んでみたいなあ
死なないためには符号理論をやるとよい
twitter分析された
バランスゲームすごい
発表終了
satashunさんが蚊に刺されまくっていた
デング熱が怖い
夏季セミナー楽しかったです
快適なネット環境のありがたみを実感した

2014-08-12

SRM 629 div 1

SRM

easyだけ提出して通った
1220->1294

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

class RectangleCovering{
public:
	int HH, WW;
	int n;
	int solve(int L, vector<int> V){
		sort(V.begin(), V.end());
		reverse(V.begin(), V.end());
		int ans = 0;
		while(L > 0){
			if(ans == V.size()) return 100;
			L -= V[ans];
			ans++;
		}
		return ans;
	}
	int minimumNumber(int hH, int hW, vector <int> bH, vector <int> bW){
		vector<int> H, W;
		n = bH.size();
		for(int i=0;i<n;i++){
			int h = bH[i], w = bW[i];
			int t = -1;
			if(h>=hH+1) t = w;
			if(w>=hH+1) t = max(h, t);
			if(t!=-1) H.push_back(t);
			int s = -1;
			if(h>=hW+1) s = w;
			if(w>=hW+1) s = max(h, s);
			if(s!=-1) W.push_back(s);
		}
		int ans = min(solve(hW, H), solve(hH, W));
		if(ans == 100) return -1;
		return ans;
	}
};