じゅっぴーダイアリー

雑談・競プロ参加記・ライブラリ残し Twitter: @juppyjappy

AGC031 - A Colorful Subsequence , B Reversi - Python 競技プログラミング Atcoder

こんにちは。でもそうはならなかった、じゅっぴーです。


 
Atcoder Grand Contest 031 - A Colorful Subsequence , B Reversi - とA問題亜種のPythonのコードです。
 

  • コンテストについて

No subでした。。。A問題の増加部分列を連続部分列と読み間違えて解き、サンプル1を試して気づいた時点で15分。predictorで茶~緑パフォがほぼ確定していたので、撤退しました。久しぶりのRatedで、長い期間かけて準備してきたので、残念です。連続部分列の場合は、今回のB問題にかなり近いのでその解答も載せておきます。悔しい。
  
 
A問題
Atcoder Grand Contest 031 A問題 Colorful Subsequence のPythonのプログラムです。
A - Colorful Subsequence
f:id:jupy:20190317091937p:plain
 

  • 問題概要

Sの増加部分列のうち、同じ文字が含まれない取り出し方は?
 

  • 考えたこと

それぞれの文字についてどれか取る 或いは どれも取らない → その文字の文字数 + 1
 なので、(文字数+1)の積 - 1で解けます。(-1 は空の文字列を除いている)
 
mod 10**9+7で間違えてる友達が複数いたので気を付けなきゃ。

文字数のカウントには素直にCounterを用いればよいでしょう。
juppy.hatenablog.com

from collections import Counter
n = int(input())
s = list(input())
mod = 10**9+7

c = Counter(s)
res = 1
for e in c.values():
    res = res*(e+1)%mod
print(res-1)

 
A問題 亜種
 

  • 問題概要

Sの連続した部分列のうち、同じ文字が含まれない取り出し方は?
ex ) 'abcab' では a b c a b ab bc ca ab abc bca cabの12通りです。
 

  • 考えたこと

簡単のため、-1 文字目は a~zまでの全ての文字があるとします。
i 番目を末尾の要素とした部分列を考えます。
下図のように i 番目から一つずつ伸ばしていくと、"ダメライン" K までの部分列の個数" i - K "が求めるものです。
f:id:jupy:20190317093725j:plain
 
では K とはなんぞ?となりますが、これは i 番目より前で、
 (1) i 番目と同じ文字で最も近いもののindex
 (2) 遡った時、2度目の同じもののindex
のうち大きいほうとなります。(下図参照)
これは
 tank : 二回以上出現した文字の内、
    後ろから二回めに出現したものが最もおそいもののindex
 used : A ~ Z のそれぞれについて、最後のindexを記録する 配列
としたとき、下図のようになります。
f:id:jupy:20190317095529j:plain
  

  • used について

 used : [Aが最後に出現したindex , Bが最後に出現したindex, ... ]
とすればよいですが、これはord を用いれば簡単に実装できます。
juppy.hatenablog.com

以上より以下のようになると思います。O(N)
コンテスト中、はじめはheapqを用いていたので、その名残にtankなどがあります。ごめんなさい。

n = int(input())
s = list(input())
mod = 10**9+7

def f(x):
    return ord(x) - 97

used = [-1]*26
tank = -1

res = 0
for i in range(n):
    res += i - max(used[f(s[i])],tank)
    tank = max(tank,used[f(s[i])])
    used[f(s[i])] = i
    res = res % mod
print(res)


B問題
Atcoder Grand Contest 031 B問題 Reversi のPythonのプログラムです。
B - Reversi
f:id:jupy:20190317101758p:plain
 

  • 問題概要

コピペ
すぬけ君は、以下の操作を 0回以上の任意の回数行います。
・同じ色で塗られている 2つの石の間に置かれている石を選んだ石と同じ色で塗りかえる。
石の並び方の場合の数は?
 

  • 考えたこと

・上のA問題亜種とかなり似てない?
・隣り合ったものが同じときは圧縮
・また、used[ i ] : 色 i が最後登場した index とすればよい
・dp[ i ] = dp[ i -1 ] + dp[ used[i] ] で終わり。。。?
・modを忘れない!!!!!!!!!
・MODを忘れない!!!!!!!!!!!!!!!!!!
 

import sys
input = sys.stdin.readline
N = int(input())
c2 = [int(input()) for _ in range(N)]
mod = 10**9+7
#圧縮
c = [c2[0]-1]
n = N
for i in range(1,N):
    if c2[i] == c2[i-1]:
        n -= 1
        continue
    c.append(c2[i]-1)

#used[i]:色iが最後に登場したindex
#初期値:-1
used = [-1]*(max(c)+1)
used[c[0]] = 0
#dp[i]:i番目まででの場合の数
dp = [0]*n
dp[0] = 1
for i in range(1,n):
    if used[c[i]] == -1:
        dp[i] = dp[i-1]
    else:
        dp[i] = (dp[i-1]+dp[used[c[i]]])%mod
    used[c[i]] = i

print(dp[-1])