Codeforces Beta Round #3
はい。
http://codeforces.com/contest/3
A. Shortest path of the king
greedy,shortest paths
ざっくりと大意
・チェスの盤上を想定してスタートとゴールの座標が与えられる。
・キングの動き方で最短でゴールに辿り着ける移動回数を求める。
方針のようなもの
・縦、横の座標が両方共違えば斜めに移動。
・縦だけ一致なら横に移動、横だけ一致なら縦に移動。
s=list(raw_input()) g=list(raw_input()) a=['a','b','c','d','e','f','g','h'] s[0]=a.index(s[0])+1 s[1]=int(s[1]) g[0]=a.index(g[0])+1 g[1]=int(g[1]) ans=max(abs(g[0]-s[0]),abs(g[1]-s[1])) x=g[0]-s[0] y=g[1]-s[1] f=[] if x>0: [f.append('R') for i in range(x)] else: [f.append('L') for i in range(-x)] if y>0: [f.append('U') for i in range(y)] else: [f.append('D') for i in range(-y)] print ans for i in range(ans): if f[0]!=f[-1]: print f[0]+f[-1] f.pop(0) f.pop(-1) else: print f[0] f.pop()
私の初回のコードは削除して新しい方のみ残してます。スタートとゴールの座標にord()とか使ってたのは以前のが賢かった。最短移動回数はネタバレ済。座標移動の仕方は前よりは短く書けていたので良かった。
補足:最短移動回数は横か縦の差分が大きい方の数だけが最大移動回数になる。当たり前のようで最初は気付かなかった。e.g. 右に5 上に3の差分の時はRU3回とR2回の5回の移動回数。差分の小さい方は斜め移動の間に先に済んでしまう。
他の方の回答を拝見して、5443306のasmnさんの
import sys __author__ = 'asmn' #引用で日本語コメ付け足しました。 #sys.stdin=file('in') #受け取りの時点でord指定できたらしい。 #位置・座標の計算をするだけなので-96は絶対必要なわけでなし si,sj=map(ord,raw_input()) ei,ej=map(ord,raw_input()) #縦、横のズレを計算してズレの大きいほうが移動回数になる。 di,dj=ei-si,ej-sj print max(abs(di),abs(dj)) #縦、横のズレをチェックして移動 #移動した方向の文字をopに+=する。移動を現在地に反映させる。 while (di,dj) != (0,0): op='' if di > 0: op+='R' di-=1 elif di <0: op+='L' di+=1 if dj >0: op+='U' dj-=1 elif dj<0: op+='D' dj+=1 print op
B.Lorry
combinatorics,greedy,sortings
ざっくりと大意
・2種類でkayakが重さ1、そしてcatamaranは重さ2のボートがn隻ある
・それぞれのボートはキャパがpある。選べる制限vまでで最大キャパになるように選ぶ
・キャパ合計と選んだ船の行数を出力
方針のようなもの
・vに2以上余裕がありkayakが2つ以上とcatamaran1つ以上あるときはコスパ？優先で使用
・kayakが1つのみとcatamaran1つ以上あるときは単純にpの大きさを優先してvの制限か舟が無くなるまで
・一度はてきとーに舟が無くなるかvの制限まで処理
・選んだ舟の内で置き換えが出来るものがないかをチェック
過去はパクリ、写経だったものをなんとか最初は自分で書いてTLEが解決できずで、過去提出分と原因になりそうなところを探りつつ書き直しを重ねてなんとかAC出せた。。。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import sys import time import itertools start = time.clock() n,v=map(int,raw_input().split()) w1,w2,chk,nico,cnt,ans=[],[],[],[],0,0 for i in xrange(n): # t,p=map(int,raw_input().split()) t,p=[int(x) for x in sys.stdin.readline().split()] #(キャパ,番目)で収納 if t==1: w1.append((p,i+1)) else: w2.append((p/2.0,p,i+1)) #とりあえずsort w1.sort() w2.sort() def kai(ans,chk): print ans if len(chk): print ' '.join(map(str,chk)) exit() for i in xrange(n): if cnt<=v-2: if len(w1)>1 and len(w2)>0: if w2[-1][1]>w1[-1][0]+w1[-2][0]: ans+=w2[-1][1] cnt+=2 chk.append(w2[-1][2]) nico.append(w2[-1]) w2.pop(-1) else: ans+=w1[-1][0] cnt+=1 chk.append(w1[-1][1]) w1.pop(-1) elif len(w1)>0 and len(w2)>0: if w2[-1][1]>w1[-1][0]: ans+=w2[-1][1] cnt+=2 chk.append(w2[-1][2]) nico.append(w2[-1]) w2.pop(-1) else: ans+=w1[-1][0] cnt+=1 chk.append(w1[-1][1]) w1.pop(-1) elif len(w1)==0 or len(w2)==0: if len(w1)==0: ans+=w2[-1][1] cnt+=2 chk.append(w2[-1][2]) nico.append(w2[-1]) w2.pop(-1) else: ans+=w1[-1][0] cnt+=1 chk.append(w1[-1][1]) w1.pop(-1) else: if len(w1): ans+=w1[-1][0] cnt+=1 chk.append(w1[-1][1]) w1.pop(-1) else: break #リミットぴったりか足すものが無くなって一旦終了 if cnt==v or len(w1)==len(w2)==0: break #探す必要なければ回答する if cnt<v or len(w1)<1 or len(nico)==0: kai(ans,chk) for j in xrange(len(w1)): #nicoがなくなるか、nicoと1を入れ替えても増やせなくなってたら終わり if len(w1)<2 or len(nico)==0: break if w1[-1][0]+w1[-2][0]<=nico[-1][1]: break if w1[-1][0]+w1[-2][0]>nico[-1][1]: ans-=nico[-1][0] ans+=w1[-1][0] ans+=w1[-2][0] chk.remove(nico[-1][2]) chk.append(w1[-1][1]) chk.append(w1[-2][1]) w1.pop(-1); w1.pop(-1) nico.pop(-1) kai(ans,chk)
3329713のbusyjayさんをパクリました。
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
start = time.clock()
def main():
n,v=map(int, raw_input().split())
pool=[]
inset=[]
for i in xrange(1, n+1):
t,p=[int(x) for x in sys.stdin.readline().split()]
# t,p=[int(x) for x in raw_input().split()]
pool.append((p*1.0/t, p, t, i))
pool.sort(key=lambda item: item[0], reverse=True)
sumary=0
#参考先さまでは(0,n)だったけど単純に(n)にするのと違いが分からじ
# for i in xrange(0, n):
for i in xrange(n):
#下に出てくるvの減算と連動。0以下で中断させる。
if v<=0: break
#価値を足す
sumary+=pool[i][1]
#v(使える最大の重さ)から使った重さを引く
v-=pool[i][2]
#使ったものの元のリストでの順番を記録する
inset.append(pool[i][3])
if v==-1:
#フラグをFalseにしておく
found=False
#poolリストの中を加算した順に遡って探す
#iは加算した最終地点で、jは-1から減算されていく
for j in xrange(-1, -i-1, -1):
#重さ1のものがあればTrueフラグにして終わる
if pool[i+j][2]==1:
found=True
break
#foundフラグがFalseの時はjを-1にする
if not found: j=-1
#重さ1のものを使ってた時は最後に使われた重さ1の(より優先度が低い)ものが取り除かれる
#重さ1のものを使ってなかった時は最後に加算されたものが取り除かれる
#価値の合計をその1へ代入
sumary1=sumary-pool[i+j][1]
found=False
#使える重さが0以下になって中断したところから開始
for k in xrange(i, n):
#優先度の低い方へ見ていき重さ1のものがあればTrueにして中断
if pool[k][2]==1:
found=True
break
#最後に加算されたものが取り除かれる
#価値の合計をその2へ代入
sumary2=sumary-pool[i-1][1]
if found:
#重さ1で発見されたものを足す
sumary2+=pool[k][1]
if sumary1>sumary2:
#その1の方が価値が高ければ代入して、使ってるものリストからj番目を取り除く
sumary=sumary1
inset.pop(j)
else:
#その2の方を代入して、末尾を取り除く
sumary=sumary2
inset.pop()
if found:
#使った物リストへk番目の順番を追加する
inset.append(pool[k][3])
sys.stdout.write(str(sumary))
sys.stdout.write('\n')
sys.stdout.write(' '.join(str(x) for x in inset))
if __name__=='__main__':
main()
気になったソートの結果
pool.sort(key=lambda item: item[0], reverse=True) ソート前 [(2.0, 2, 1, 1), (3.5, 7, 2, 2), (3.0, 3, 1, 3)] ソート後 [(3.5, 7, 2, 2), (3.0, 3, 1, 3), (2.0, 2, 1, 1)]
C. Tic-tac-toe
brute force,games,implementation
ざっくりと大意
・まるばつゲームの状態を判定する。
・既に勝ちか、これからどちらかの手番か、全て埋まって引分か、ゲームでありえない状態か。
方針のようなもの
・ボードの大きさが3*3なので全部見る。
l=[] cx=co=cd=0 for i in xrange(3): w=raw_input() cx+=w.count('X') co+=w.count('0') cd+=w.count('.') l.append(w) def ill(m): chk=0 if m==l[0][0]==l[1][0]==l[2][0]: chk+=1 if m==l[0][1]==l[1][1]==l[2][1]: chk+=1 if m==l[0][2]==l[1][2]==l[2][2]: chk+=1 return chk def iee(m): chk=0 if m==l[0][0]==l[0][1]==l[0][2]: chk+=1 if m==l[1][0]==l[1][1]==l[1][2]: chk+=1 if m==l[2][0]==l[2][1]==l[2][2]: chk+=1 return chk def ixx(m): chk=0 if m==l[0][0]==l[1][1]==l[2][2]: chk+=1 if m==l[2][0]==l[1][1]==l[0][2]: chk+=1 return chk ans=['first','second','illegal','the first player won','the second player won','draw'] if co==cx: if ill('X')==iee('X')==ixx('X')==ill('0')==iee('0')==ixx('0')==0: print ans[0] elif ill('X')==iee('X')==ixx('X')==0 and ill('0')+iee('0')+ixx('0')>0: print ans[4] else: print ans[2] elif cx-co==1: if ill('X')==iee('X')==ixx('X')==ill('0')==iee('0')==ixx('0')==cd==0: print ans[5] elif ill('X')==iee('X')==ixx('X')==ill('0')==iee('0')==ixx('0')==0: print ans[1] elif ill('X')+iee('X')+ixx('X')>0 and ill('0')==iee('0')==ixx('0')==0: print ans[3] else: print ans[2] else: print ans[2]
強引に全部見たけどもう少し短く書けた気がする。。後で。
