AtCoder

ARC#012

A - 週末 週末 print{"Sunday":0,"Monday":5,"Tuesday":4,"Wednesday":3,"Thursday":2,"Friday":1,"Saturday":0}[raw_input()] B - アキレスと亀 アキレスと亀 N,va,vb,L = map(int,raw_input().split()) for i in range(N): L -= float(va-vb)*L/va print "…

天下一プログラマーコンテスト2012 決勝 A - ぶんたん

ぶんたん本番中は「貪欲でいけるんじゃね? 間違えたところでペナルティは5分だし、試してみようw」と貪欲で書いた。実はこれが正しくて、貪欲に大きいフィボナッチ数を引いていくだけで、答えが得られる。証明。k番目のフィボナッチ数をFkとする。①Nを最小…

天下一プログラマコンテスト2012 予選B D - 大爆発

大爆発爆弾を置くy座標を決める(同じy座標に複数の爆弾を置くのもあり)と、そのように爆弾を置いて全ての壁を破壊するのに必要な爆弾の個数が求められる。そのy座標に空きが無ければ無理。それ以外の場合は、そのy座標以外にある壁を壊すのに爆弾が何個必…

天下一プログラマコンテスト2012 予選B C - 席が足りない

席が足りない社員の部分集合ごとに何席必要かを覚えておいて、動的計画法。その社員が1席を共有できるなら、1席。そうでないならば、部分集合を2個に分割したそれぞれの席数の和の、最小値。 #include <iostream> #include <cstdio> #include <vector> using namespace std; int countb</vector></cstdio></iostream>…

天下一プログラマコンテスト2012 予選B B - camel_case

camel_caseやるだけ。だが、面倒くさい。こういう問題を、正規表現とかを使って、すっきり解けるようになりたい。 import re c = raw_input() if c=="_"*len(c): print c exit(0) pre,suf = 0,0 while c[pre]=="_": pre+=1 while c[-suf-1]=="_": suf+=1 c =…

天下一プログラマコンテスト2012 予選B A - 孫子算経

孫子算経 a,b,c = map(int,raw_input().split()) for i in range(1,128): if i%3==a and i%5==b and i%7==c: print i

ARC#006 D - アルファベット探し

アルファベット探し異なる文字が接することは無いので、接しているoを繋げていくと、文字ごとに分けられる。あとは文字ごとにAかBかCかを調べる。最左のピクセルと最右のピクセルの位置から何倍に拡大されているかがわかる。各文字はピクセル数が異なるので…

ARC#006 C - 積み重ね

積み重ね貪欲。置くことができて最も軽い箱の上に置くのが最善。ちなみに、Pythonには for a in A: XXX else: YYY という記法があって、ループを最後まで実行した(breakしなかった)場合にだけ、YYYが実行される。 T = [] for i in range(input()): x = inp…

ARC#006 B - あみだくじ

あみだくじ[0, 1, 2, 3, …, N]という配列を用意しておいて-が出てくる度に、その位置の要素を交換すれば良い。 N,L = map(int,raw_input().split()) T = range(N) for i in range(L): for j,x in enumerate(raw_input()[1::2]): if x=="-": T[j],T[j+1] = T[…

ARC#006 A - 宝くじ

宝くじ def r(): return map(int,raw_input().split()) E=r() B=input() L=r() t=len([x for x in L if x in E]) if t==6: print 1 elif t==5 and B in L: print 2 elif t==5: print 3 elif t==4: print 4 elif t==3: print 5 else: print 0

ARC#005 C - 器物損壊!高橋君 ( Search and destroy )

器物損壊!高橋君 ( Search and destroy )道への移動は距離0、壁への移動は距離2と考えて、幅優先探索。 # coding: utf-8 H,W = [int(x)+6 for x in raw_input().split()] c = ["#"*W]*3+["###"+raw_input()+"###" for y in range(H-6)]+["#"*W]*3 D = [[9]*…

ARC#005 B - P-CASカードと高橋君 ( This story is a fiction )

P-CASカードと高橋君 ( This story is a fiction ) x,y,W=raw_input().split() x=int(x);y=int(y) dx=1 if W[0]=="R" else -1 if W[0]=="L" else 0 dy=1 if W[-1]=="D" else -1 if W[-1]=="U" else 0 c = [raw_input() for i in range(9)] p = "" for i in r…

ARC#005 A - 大好き高橋君 ( Love me do )

大好き高橋君 ( Love me do ) input();print [w in["TAKAHASHIKUN","Takahashikun","takahashikun"]for w in raw_input()[:-1].split()].count(True)

ARC#004 C - 平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )

平均値太郎の憂鬱 ( The melancholy of Taro Heikinchi )(N(N+1)/2-M)/N = X/Yを変形して、N = 2(X/Y+M/N)-1Nが整数であることと、0<M/N≦1であることから、Nはfloor(2*X/Y)とfloor(2*X/Y)+1。それぞれについてMを求めて、正しいかチェック。 from fractions…

ARC#004 B - 2点間距離の最大と最小 ( Maximum and Minimum )

2点間距離の最大と最小 ( Maximum and Minimum )最大は辺の長さの総和。最小は、(最長の辺の長さ)-(それ以外の辺の長さの和)。最小が0以下になるなら、2点を重ねられる。 N = input() d = [input()for x in range(N)] print sum(d) print max(0,2*max(d)-su…

ARC#004 A - 2点間距離の最大値 ( The longest distance )

2点間距離の最大値 ( The longest distance )問題サイズが小さいので全ての組合わせを試せば良い。 import math N = input() P = [map(float,raw_input().split())for x in range(N)] print "%.10f"%max(math.hypot(p[0]-q[0],p[1]-q[1]) for p in P for q in…

AtCoder Regular Contest #002 C - コマンド入力

コマンド入力ボタンの全ての割り当て方を試す。AAB……という系列、L=AA、R=ABだった場合に、LよりもRを使った方が入力回数が少なくなるということはないので、先頭から貪欲にLとRを使えば良い。 input() c=raw_input() a=len(c) for L1 in "ABXY": for L2 in …

AtCoder Regular Contest #002 A - うるう年

うるう年 Y=input();print"YES"if Y%400==0 or Y%100!=0 and Y%4==0 else"NO"

AtCoder Regular Contest #002

A 1:36 B 33:34 RE 1回 C 17:23 D × 結果 41位ミスが痛いので、早解きに拘らず、丁寧に解こうorz