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?
2〜5文字までの入力があって、文字列'AC'
を含むかどうか。
S = input() print('Yes' if 'AC' in S else 'No')
はい。
なんだけど、python のin
のイディオムが咄嗟に思い出せずにググった。。
ゴリゴリとforループ回した方が早かったかも。
ど忘れコワイよー。
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'
文字列が与えられて、'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)
コード見てもらえばわかると思うけど、l
とr
の添字を文字列の頭とお尻に設定して、そこから挟み討ちのようにl
は増やし、r
は減らしていく方針。
途中、l
またはr
のうち一方が'x'
だったら、'x'
のカウントを1増やして、'x'
だったほうの添字を進める。
l
とr
が異なっててどちらも'x'
でないときは、いくら'x'
を挿入しても回文になり得ないので、-1
。
while
の終了条件が少し不安なままsubmitしてしまったのはちょっと秘密。
実際はもしl==r
だとしても同じ文字を参照するから変にカウントは増えない。大丈夫。
ところで、これはしゃくとり法の一種なのかな?
よくあるしゃくとり法って、
頭をr
、お尻をl
って決めて、しゃくとり虫みたいにl
やr
を進めていくイメージ。
今回のやつは、
ビヨーンと最大に伸びきったしゃくとり虫が、縮んでいって最後には無になるイメージ。
しゃくとり法は単純な割に、実はO(N)
と知って、あなどれないと思った。
この手の問題のときには優先的に思い浮かべることにしてる。