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

ゆらのふなびと

競プロ, Python, C++

Codeforces Round #337 (Div. 2) に参加しました

2度目のCodeforces参戦。

前回は最初の1問しか解けなかったので今回は2問は取りたいなーと思っていたのですが、その結果やいかに…?

結果

f:id:pakapa104:20151228184934p:plain

結局1完でした!!

しかもA問題1回hackされてるし(場合分けさぼったせい)

そのあといろいろ考えてCまでは解けたので、解法をまとめておきます。


>>参考にさせていただいた記事

hyoga.hatenablog.com


A. Pasha and Stick

codeforces.com

長さnの棒を4つに分割するとき、正方形でない長方形は何通り作れるかという問題(辺の長さはすべて正の整数)

最初に提出したコードはこれ。

import math
print int(math.ceil(1.0*input()/4)-1)

これだとnが奇数の場合に対応できていないですね。(nが奇数だと4つの辺に分割できない)

ということで改定したのが以下。怖いのでn<6も最初に分けてしまった…(ほんとうはいらない)

import math
n = input()
if n % 2 != 0 or n < 6:
    print 0
else:
    print int(math.ceil(1.0*n/4) - 1)

B. Vika and Squares

codeforces.com

Vikaちゃんはi種類の色をa_iリットルずつ持っている。横に並んだマスを各色で順番に塗っていくとき、最大で何マス塗れるかという問題。最初に色iを選んだら次はi+1, i+2, ..., N, 1, 2, ...という風に続いていく。

色が1種類しかないときは1マスしか塗れないと思っていたのでTest5ではじかれまくった。通ったコードは以下。手順としては、

  1. 初期化:s(求める値)=0
  2. s += aの最小値*n; aの各要素から最小値を引く(絶対に使う分)
  3. s += aの中で、0でない要素が連続する最大の個数(0とNが循環してつながっているときがめんどくさいので、aに対してループを2回回している)
n = input()
a = map(int, raw_input().split())
s = 0
minimum = min(a)
a = map(lambda x: x-minimum, a)
s += minimum*n
c, max_c = 0, 0
for j in xrange(2):
    for i in xrange(n):
        if a[i] > 0:
            c += 1
        else:
            if c > max_c:
                max_c = c
            c = 0
s += max_c
print s

そういえばmap()よりリスト内包表記の方が早いらしいので、aから最小値を引くところは

a = [x-minimum for x in a]

と書いたほうがよかったかもしれない。

C. Harmony Analysis

codeforces.com

2k次元のベクトルで直交するものを2k個つくりなさいという問題。ただし要素は1か-1に限り、それぞれ"+", "*"で出力するものとする。要は2k次元の直交基底を作れということじゃな。

…というところまではわかったが規則性がわからず頓挫。それで上記の記事を拝読したわけですがそもそも再帰がわかってないので実装ができない。というか構造が理解できないのだ。

ということで、様々なサイトを巡って再帰の勉強をしつつ1日かけて書いたコードが以下です。手順は、

  1. 初期化:s = "+"
  2. 左から順にs+sとs+trans(s)をつくっていく(例:++++, ++**)
  3. 終端まで行ったら表示

結果は結構シンプルになったけど、ここに来るまでが長かったよ…。

文字列の諸々は全部pythonちゃんに任せました。Viva python

import string

def trans(s):
    return s.translate(string.maketrans("+*", "*+"))        

def orthogonal(s, n):
    if n == 0:
        print s
    else:
        orthogonal(s+s, n-1)
        orthogonal(s+trans(s), n-1)

k = input()
if k == 0:
    print "+"
else:
    orthogonal("+", k)

再帰については以下のサイトが参考になりました↓↓

www.geocities.jp

D. Vika and Segments

codeforces.com

無限に広い方眼紙にVikaちゃんがn本の線分を引きます。このとき方眼紙上の塗られているマスは何マスでしょうという問題。線分の太さは1マスに相当し、2回以上塗られているマスは1回と数える。

愚直にカウントしていけばできるのかな…?(解けたら書きます)