矮小

井の中の蛙

Codeforces Round 313 Div. 2 AからC

Python 3で参加したらデバッグが大変だった．公式のEditorialとほとんど同じだけど一応……．

560A Currency System in Geraldion

貨幣が5種類与えられるので，その貨幣をそれぞれ0回以上使った時にどうしても表現できない最小の値を答える．任意の値を表現できる場合は -1 を出力する．

解法

1 があったら 1 を無限に使うことで任意の値を表現できる．1 が無かったら他の何を使っても 1 を表現できない．これは最小の unfortunate sum．

プログラム

さすがにここまで単純とは思わなくて怖かったけど普通に通った．ちなみに今見たら他の誰かのコードと一致したのか Skipped になってた．そらこんな簡単なの誰かと一致するだろ．だからレート下がったのか．

n = int(input())
a = map(int, input().split())
if 1 in a:
    print(-1)
else:
    print(1)

560B Gerald is into Art

長方形の絵を2つ買った．長方形のでかいフレームの中に収まるかどうかを判定したい．

解法

（横に並べる・縦に並べる），（1つ目の回転），（2つ目の回転）で 2 \cdot 2 \cdot 2 = 8 通りある．左上に詰めて置くと考えればいいので，横に並べる時は横の長さが sum で縦の長さが max，縦に並べる時は縦の長さが sum で横の長さが max になることが分かる．8通り全部やる．

プログラム

愚直も愚直．

a1, b1 = map(int, input().split())
a2, b2 = map(int, input().split())
a3, b3 = map(int, input().split())

if (max(a2, a3) <= a1 and b2 + b3 <= b1) or \
   (max(a2, b3) <= a1 and b2 + a3 <= b1) or \
   (max(b2, a3) <= a1 and a2 + b3 <= b1) or \
   (max(b2, b3) <= a1 and a2 + a3 <= b1) or \
   (a2 + a3 <= a1 and max(b2, b3) <= b1) or \
   (a2 + b3 <= a1 and max(b2, a3) <= b1) or \
   (b2 + a3 <= a1 and max(a2, b3) <= b1) or \
   (b2 + b3 <= a1 and max(a2, a3) <= b1):
    print("YES")
else:
    print("NO")

560C Gerald's Hexagon

正三角形から成る六角形の中に詰まっている三角形の数を数える．

想定解法

始めに，正三角形から成る正三角形は，上の列からそれぞれ個数を数えると 1, 3, 5, … というように奇数列になっていることが分かる．奇数列は 2k - 1 で表せるので，この sum を取ると {n}^2 になることが分かる．問題で与えられるような六角形は，1辺が a_1 + a_2 + a_3 の大きい正三角形から上と右下と左下の小さい正三角形を削り取ったものと考えられるので， {(a_1 + a_2 + a_3)}^2 - {a_1}^2 - {a_3}^2 - {a_5}^2 で答えが求められる．Editorial もうちょっと詳しく書いてくれ．

プログラム

想定解法とは違うやり方で提出していました．だいたい同じですが，平行四辺形を作って右上と左下を削るみたいな計算をしました．上底の長さは a_1 + a_2 で，1列にはその2倍の三角形が詰まっているので，平行四辺形の中にはそれに高さ a_2 + a_3 を掛けた分だけ三角形が詰まっています．後は右上と左下を上と同じように引くだけ．奇数列の総和が {n}^2 という公式に辿り着くまでの計算を渋って補助のメソッドを書いたのがダサい．ちなみにこの解法の式を整理したら 2(a_1a_2 + a_2a_3 + a_3a_1) + {a_2}^2 - {a_5}^5 とかいう基本対称式の線形結合みたいな式が出てきて特別綺麗でもなく何とも言えない気持ちになりました．

def f(x):
    ans = 0
    for i in range(1, x + 1):
        ans += 2 * i - 1

    return ans

a = list(map(int, input().split()))
print((a[0] + a[1]) * 2 * (a[1] + a[2]) - f(a[1]) - f(a[4]))

DとEは愚直に書いたら両方TLEで落ちた．お疲れ様でした．C問題はDiv 1のA問題なわけだしこれからもコンスタントにDiv 2で3完していきたいなあと思いました．