ごりちゃんがゆく

競プロをするゴリラの精進記録

CODE FESTIVAL 2017 qual C

3日ぐらい前のやつ。

ところで、先日のDDCCの本戦、辞退者が多くてどんどんボーダーラインが繰り上がってる、と風の噂。
行けたらぜひ本戦行きたいので、かな〜り気になってる。
ちなみに10/26 1:00現在、予選222位の私には連絡なし(´・ω・`)

結果

A,B,Cの3完。タイム19:43。395位。
パフォーマンス1782(highest!)、レート1303→1367(highest!)(+64)

A,Bで少しモタついてしまい600位ぐらい → Cで冷静に挽回できて300位ぐらい。
あとはDの700が難しく、あまり順位が下がらず救われた。(救われてはいけない)
どうも、あるレベル(400-500点?)より難しい問題だと、手も思考もフリーズしてしまうのをなんとかしたい。

A - Can you get AC?

A - Can you get AC?

2〜5文字までの入力があって、文字列'AC'を含むかどうか。

S = input()
print('Yes' if 'AC' in S else 'No')

はい。
なんだけど、pythoninのイディオムが咄嗟に思い出せずにググった。。
ゴリゴリとforループ回した方が早かったかも。
ど忘れコワイよー。

B - Similar Arrays

B - Similar Arrays

整数の数列が入力として与えられて、各項が±1の範囲の整数になってる数列を「似ている」数列と呼ぶとき、
似ている数列の中で、全ての項の積が偶数になるものがいくつあるか。

これ、最近の200点にしては難しかったので、焦った。 体感300点ぐらい。

N = int(input())
src = list(map(int,input().split()))
 
whole = 3**N
even = 0
for i in range(N):
    if src[i]%2 == 0: even += 1
 
print(whole - 2**even)

コード自体は、一言で言うと、
偶数の数を数えて、3^Nから2^[偶数の個数]を引いてるだけ。

なぜそうなるのか。プチ解説

各項、+1,±0,-1の3通りが許されるので、「似ている」数列は全部で 3^N 通りある。
この問題は偶奇だけを考えれば良いので、似ている数列では、
「奇・偶・奇」または、「偶・奇・偶」がN個並んでいることになる。
内訳は、数列に偶数がe個あったとすると、
「奇・偶・奇」がe個、「偶・奇・偶」が(N-e)個になる。

整数どうしの積は、
奇数同士はいくら掛けても奇数 ↔︎ 偶数が1つでも含まれていれば偶数
という性質がある。
これを使って、全体から「奇数のみからなる数列の個数」を引く と良さそう。

「似ている」数列の中から、奇数のみからなる数列を作るには、

  • (N-e)個の「偶・奇・偶」については、真ん中の奇数を取るしかない。1通り。
  • N個の「奇・偶・奇」については、どちらかの奇数が選べるので、2通り。

奇数のみからなる数列は、
1^(N-e) * 2^e = 2^e 個。
つまり、答えは全体から引いて
(3^N - 2^e) 個。

ちなみに、Nが10と小さいので、3^Nを全探索しても良い、という問題でした。

C - Inserting 'x'

C - Inserting 'x'

文字列が与えられて、'x'と言う文字を何回か挿入して回文になるなら、その最小回数を出力し、回文にならなければ-1を出力する問題。

これはB問題とは逆に、400点にしては少し簡単に感じた。
むしろBより楽だったかも。

S = input()
l = 0
r = len(S)-1
cnt = 0
while l < r:
    if S[l] == S[r]:
        l += 1
        r -= 1
    elif S[l] == 'x':
        l += 1
        cnt += 1
    elif S[r] == 'x':
        r -= 1
        cnt += 1
    else:
        cnt = -1
        break
print(cnt)

コード見てもらえばわかると思うけど、lrの添字を文字列の頭とお尻に設定して、そこから挟み討ちのようにlは増やし、rは減らしていく方針
途中、lまたはrのうち一方が'x'だったら、'x'のカウントを1増やして、'x'だったほうの添字を進める。
lrが異なっててどちらも'x'でないときは、いくら'x'を挿入しても回文になり得ないので、-1

whileの終了条件が少し不安なままsubmitしてしまったのはちょっと秘密。
実際はもしl==rだとしても同じ文字を参照するから変にカウントは増えない。大丈夫。

ところで、これはしゃくとり法の一種なのかな?

よくあるしゃくとり法って、 頭をr、お尻をlって決めて、しゃくとり虫みたいにlrを進めていくイメージ。
今回のやつは、
ビヨーンと最大に伸びきったしゃくとり虫が、縮んでいって最後には無になるイメージ。

しゃくとり法は単純な割に、実はO(N)と知って、あなどれないと思った。
この手の問題のときには優先的に思い浮かべることにしてる。