Codeforces Beta Round #6 (Div. 2 Only)
はい。
A. Triangle
brute force, geometry
ざっくりと大意
・Johnny と Anne は兄妹。妹は賢い。妹は宿題を持ってきた。 ・4本の棒で三角形を作る。(棒は長さを変えたり一部分だけを使ったりは出来ない)そして棒は1本余るっぽい。 ・正の領域の三角形を作れなかったり、縮退三角形(degenerate triangle)を作ることがある(縮退三角形は棒を4本使うことになる)。 ・3本で正の三角形が作れるか、4本で縮退三角形になるか、何も作れないかで分ける。
方針のようなもの
全然分からなかったのでパクったソースからの推定です。 辺の長さでソートしておいて、 ・三角形の判定 一番短い+二番目に短い > 三番目に短い 二番目に短い+三番目に短い > 四番目に短い まぁ、この場合4本の棒なので四番目は一番長いのですが。。。 おそらく長さでソートして 短い方の2本の和 > 3本目 な大小関係が成り立てばいいのかな?
・縮退三角形(degenerate triangle)の判定 一番短い+二番目に短い == 三番目に短い 二番目に短い+三番目に短い == 四番目に短い これも多分 短い方の2本の和 == 3本目 という関係が成り立てばいいのかな?
3846984のbusyjayさんのパクリ
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() a=map(int, raw_input().split()) a.sort() if a[0]+a[1]>a[2] or a[1]+a[2]>a[3]: print 'TRIANGLE' elif a[0]+a[1]==a[2] or a[1]+a[2]==a[3]: print 'SEGMENT' else: print 'IMPOSSIBLE'
C.Alice, Bob and Chocolate
greedy,two pointers
ざっくりと大意
・アリスは左から右へ消費する
・ボブは右から左へ消費する
・最後の一つは先に手を付けた方のモノかな?
・最後の一つが同時になったらaliceのモノ
方針のようなもの(パクリなので推定)
・消費しようとしているものがaliceのが小さい/bobのが小さい/同じ大きさの場合に分けて処理。
・残っている大きさのチェックも大事。
パクリ元は1761581のaajjbbさんから。多分twitterで何度か話したことがある人だと思う。
#!/usr/bin/env python # -*- coding: UTF-8 -*- import time import sys, io import re, math start = time.clock() alice=0 bob=0 n=int(raw_input()) l=map(int,raw_input().split()) i,j=0,len(l)-1 #1つしか与えられなかった時の判定 if len(l)==1: alice+=1 print alice,bob #これで後のwhile処理させないらしい。すげえ。 exit (0) while 1: #tmp_iはaliceの食べる方、tmp_jはbobの食べる方。 tmp_i=l[i] tmp_j=l[j] #bob側のが大きければ先にaliceが一つ食べ終わるのalice1加算 if tmp_i<tmp_j: alice+=1 #aliceが食べ終わったのと同じ量を食べるけどちょっと残る l[j]-=l[i] #残量をチェックし余裕があれば次のを食べる準備 if i+1<len(l): i+=1 #余裕がなかったのでbobの食べ途中も1加算して終了 if i==j: bob+=1 break #alice側のが大きければ先にbobが一つ食べ終わるのでbob1加算 elif tmp_i>tmp_j: bob+=1 #bobが食べ終わったのと同じ量を食べるけどちょっと残る l[i]-=l[j] #残量をチェックし余裕があれば次のを食べる準備 if j-1>=0: j-=1 #余裕がなかったのでaliceの食べ途中も1加算して終了 if i==j: alice+=1 break #aliceのとbobの食べようとしてるのが同じ量の時 else: #共に1加算する alice+=1 bob+=1 #新しいのを食べに行く準備 if i+1<len(l): i+=1 if j-1>=0: j-=1 #余裕がなかったので終了 if i-j == 1: break #最後の1つはalice優先で終了 if i==j: alice+=1 break print alice,bob