読者です 読者をやめる 読者になる 読者になる

君はまるで砂漠に咲く、一輪の花。

僕はその花に引き寄せられる蝶。

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