https://local.ugene.unipro.ru/tracker/secure/attachment/12144/Linear+Suffix+Array+Construction+by+Almost+Pure+Induced-Sorting.pdf を読んで実装した。 まだverifyしていないので正しいか知らない。 [追記4/28] http://uva.onlinejudge.org/index.php…

京都大学理学部理学科に合格しました

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1142&lang=jp D言語らしいコードが書けた mutableじゃないとreverseできない（当たり前）とかimmutableだと~が使えない（なんでだろう？）で引っかかった 例えば，下の解答の一部で char[] v = st…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2317 二分探索。場合分けを冷静にしてオーバーフローに気をつける import std.stdio; import std.string; import std.conv; import std.algorithm; import std.range; import std.typecons; int a…

センター試験まで1週間です。 気分転換に解いた http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2600 解法 imos法を使ってカバーできているかどうか調べる。 コーナーケースがあって、マスの辺はカバーできているけど中身がカバーできていないと…

あけましておめでとうございます するめは新年早々、unratedだったeasy はじめにソートする 尺取りみたいに見て、osize[i]-osize[j]>Kとなった瞬間に(j-i-1)C(M-1)を答えに加算する(osize[i]を最小のお好み焼きとして必ず選ぶときのありえる組合せの数) 組合…

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