easy 頂点を4つの象限で分類して（軸は適当に含める）考えると、原点を内部に含む三角形は次の二つのうちいずれかを満たすことに気づく。 (1)頂点が向かい合う二つの象限（または軸の上）にある (2)頂点が三つの象限（または軸の上）にある(1)について、ある…

模試の結果が冷えている

勝敗を全列挙する #coding: utf-8 def solve(i,j,s,P,N,M): ret = 0 if i == j: if i == N-1: k = sorted(s) k.reverse() ss = tuple(k) if ss[0] == M: if ss not in P: P.add(ss) ret = 1 else: ret = solve(0,j+1,s,P,N,M) else: # i vs j s[j] += 2 ret …

Greedy 証明は ABAB CDCD ABAB CDCDみたいな塗り分けをするとできる #coding: utf-8 class NotTwo: def maxStones(self, width, height): a = [[0 for i in range(width+2)] for j in range(height+2)] ans = 0 for c in range(2,width+2): for r in range(2…

あり得るすべての辺の長さの組合せを列挙して最大の面積の三角形を求める． #coding: utf-8 import math EPS = 0.0001 def pitagoras(x): a = 0 ret = [] while a ** 2 <= x / 2 + 1: r = x - a ** 2 b = math.sqrt(r) b += EPS c = int(b) if c ** 2 == r: …

期待値計算 #coding: utf-8 # 1 2 3 4 5 6 7 8 9 T cs = [0, 4,4,4,4,4,4,4,4,4,16] scr= [0,11,2,3,4,5,6,7,8,9,10] def solve(v,s): if s >= 21: return 0.0 else: a = sum(v) e = 0.0 for i in range(1,11): if v[i] > 0: n = v[i] v[i] -= 1 e += (solve…

実装 # coding: utf-8 d = ((-2,-1),(-2,1),(-1,-2),(-1,2),(1,-2),(1,2),(2,-1),(2,1)) blocked = [[False for i in range(8)] for j in range(8)] def calc(y,x): if 0 <= y < 8 and 0 <= x < 8 and (not blocked[y][x]): ret = 0 for dy,dx in d: ny,nx =…

他の面に出たときは，今までいた面の反対側から出てくると考えると，1面だけ考えればよい． #coding: utf-8 cube = (('RED','BLUE','RED'), ('BLUE','GREEN','BLUE'), ('RED','BLUE','RED')) direction = ((0,1),(1,0),(0,-1),(-1,0)) class CubeWalking: de…

デバッグ用の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){ ret</vector></string></algorithm></cstdio>…

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] != '/':…

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, …

解いた．後ろから，最終的に一番上になるものだけ見るテクニックを使うと計算量が小さい． 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_inpu…

今回も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</vector></algorithm></cstdio>…

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

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(</int></vector></algorithm></cstdio>…

予選通過しました。 なんかすごく運がよかったなあという感じ

オンラインで参加した。 占いが解けなくてつらい。A:マッサージチェア 6通りしかないしコピペで全通り書いた #include <cstdio> #include <algorithm> using namespace std; int a[3]; int b[3]; int d(int x, int y, int z){ int p = abs(x-a[0]); int q = abs(y-a[1]); int r </algorithm></cstdio>…

問題要約：Aはa個の1からbまでの整数が同様に確からしい確率で出るサイコロを持っている。Bはc個の1からdまでの整数が同様に確からしい確率で出るサイコロを持っている。今A,Bがすべてのサイコロをふって自分のサイコロの総和Sa,Sbを求めたところSa>Sbであっ…

数学基礎論とか計算複雑性の理論あたりをやりたいなあとぼんやり思っている

英語を克服したと思ったら数学ができなくなってしまった 志望大学を京都大学に決めた

B-smallとB-largeを通した(735位) 実装がとても辛かった… 基本的に、1つの種類の文字からなる文字列と2種類以上にまたがっているやつにわけるということをやっている。2種類以上にまたがっているものは、文字を頂点、文字列を辺としたグラフを考えて連結成分…

easyだけ解きました。 まず横方向に見ていって横に連続したしましまの長さを記録しておく。その後、縦に見ていく。縦に見るときは、次に長方形の幅（横のながさ）が伸びるか縮むかで場合分けをする。幅が伸びるとき：伸びた長さで高さ1の長方形を追加 幅が縮…

新年度になって受験生になってしまいました。 昨年度はSuperCon,PCK,JOIに参加して一昨年よりマシな成績になってよかった…。（JMOは予選通過したけど本選がひどかった）とくにJOIでは春合宿まで参加し、他の学校の方々と交流できてとても有意義な大会でした…

接尾辞配列というのを使うと文字列検索でいろいろできるらしいので書いてみた 何も見ずに書くと蟻本のコードと比較したとき自分のコードがいかにぐちゃぐちゃか思い知らされる． #include <cstdio> #include <cstring> #include <algorithm> #include <vector> using namespace std; const int MA</vector></algorithm></cstring></cstdio>…

解説みて解いた．問題が木だったらとりあえずEuler-Tourを使えないか考えるとよさそう． 二次元にして長方形を塗るという考え方は頭がいい． #include <cstdio> #include <vector> #include <algorithm> using namespace std; const int MAXN = 2010, MAXM = 500000; typedef pair<int,int> P; in</int,int></algorithm></vector></cstdio>…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2235 クエリを平方分割する問題．平方分割した後にいらない頂点をつぶすのが超大変． Union-Find treeでがんばってつぶす． 以前からあった辺が，今みている区間のなかで破壊されるとき，あらかじ…

分割統治っぽくなって，頂点数Nの部分木にたいしてO(f(n))の計算量がかかるとすると，全体の計算量はCentroid DecompositionをするとO(f(n) log n)になってはやい．追記：コードに誤りがあったので修正しました．まだあるかもしれない #include <cstdio> #include <vector> #</vector></cstdio>…

いまごろですがJOI本選に通過していました。 本選問3バウムクーヘンで配列を2倍にするところを、なぜか2乗の長さが必要だと思い込んでいて解けませんでした。 #include <cstdio> #include <algorithm> using namespace std; #define IDX(a,n,v) distance(a,lower_bound(a,a+n,v)</algorithm></cstdio>…

いもす法を排他的論理和でやるみたいな方法で解きました。 長方形に番号をふります。 グリッドのマスの、2進数のある桁が1になっているとき、そのマスには(その桁数)番の長方形が存在する、という風に対応させます。 いもす法みたいに配置して累積XORをとる…