あけましておめでとうございます するめは新年早々、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 =…

デバッグ用の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, …

今回も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>…

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

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