Educational Codeforces Round #83 参加記録 - 少ない学びをせめて記録する

Dまで4完でした。Eは解法もあっていたのですがつまらないバグを残してしまいダメでした（泣）。

A Two Regular Polygons

N%Mが0かどうか。

B Bogosort

リストを並び替えてi-aiがすべて異なるようにすればいいです。 aiを降順に並べればi-aiは狭義単調増加になります。

C Adding Powers

A=a1...an はゼロ埋めされたリストでB=b1...bnが与えられます。 k^I をajに足す操作を各iに対して高々1回行って A=Bとできるかという問題

b1...bnをk進数で表したときに各桁の値が1 or 0にならないといけないです。また、同じ桁が1のbjが2つ以上あってもダメです。それ以外の時はYESです。

結構迷った印象ですが時間を見ると10分で解けていて成長を感じます。

D Count the Arrays

問題 : M以下の数字を使って長さNのリストを作る。重複する数はちょうど1つになるようにする。また、あるjが存在してi<jならai<aj、j>iならai>ajとなる。このようなリストの数を数える。

ちょっと迷いましたが出来ました。使う数字を決めます。重複1なので数字の種類数はN-1なのでcombination(M, N-1)。重複させる数を決めます。それがN-1個の数の中で最大の数なら構成できないので決め方はN-2通り。残りの数(最大の数と重複させた数以外のN-3個)が最大の数の左右どちらにあるか決めます。2^N-3

これらをかけたら終わりです。

N=2の時がコーナーケースです。1WA またcmbinationを事前計算しておくとMLEしてしまいました。pypyでなくpythonで出すことで通りましたが、何か改善策を考えておかないといけなさそうです。この問題に合計25分くらいかかったようです。

E Array Shrinking

「隣り合う同じ数字をくっつけて1増やす」を繰り返してどれだけ列を小さくできるかという問題です。通せなかったのが本当に悔しい。

a1, a2, a3, a4, ... an とあるときに連結できる範囲をあらかじめ計算してしまいます。

a1, |a2, a3, a4, a5|, ... an

とあってa2からa5をくっつけて1つの値にできるかを調べましょう。なお、できる場合はその値はどのような順序で連結しても同じ値になります。（適当に試せば証明可能と思います）

|a2], |a3, a4, a5|

がそれぞれ１つの値になって、さらにそれぞれが同じ値なら良さそうです。なので|a2 .. ai| と|ai+1...a5|につて予め計算しておいて全部試せば全体が１つの値になるか、またどのような値になるかがわかります。

長さ１の区間 n個について初期化しておいて、次に長さ2の区間n-1個について、...という風にdpすればいいです。

具体的な配列は次のようにします。 dp1[i, j] = 範囲 i, j を１つにすると値は何になるか。1つにできないなら-1

これがあればdp2[x] = 1...axをみたときの列のサイズの最小値が計算できます。

dp1の計算量は雑に見積もればN³で、500³なのでTLEしますが、実際のループ関数はそれよりも大分少なめです。（オーダーはN³のままです）

しかし、本番ではTLEしてしまいました。理由はdpをタプルからintへの辞書を使ったからです。なのでタプルをencodeしてintにしてから計算！

これでTLEは解消できましたが、dp2の初期化にバグがありWAが取れませんでした。本当に単純なバグだったので悔しいですが反省点は次のようなものです。1. pythonを使っているのならTL厳しいのは当たり前。タプルをencodeするなどの書き方を固定してストレスなく高速化できるようにする。2. シンプルでバグりにくいコードを書きましょう！　

最終コードは以下です。

N = int(input())
X = list(map(int, input().split()))
from collections import defaultdict
dp1 = defaultdict(lambda :-1)
M=1001
def ec(i,j):
    return i*M+j

for i in range(N):
    dp1[ec(i,i+1)] = X[i]
for i in range(2, N+1):
    for j in range(N-i+1):
        for k in range(1, i):
            u, v = dp1[ec(j,j+k)], dp1[ec(j+k,j+i)]
            if u != -1 and v != -1 and u == v:
                dp1[ec(j,j+i)] = u+1
                break

dp2 = [N]*(N+1)
dp2[0] = 0
for i in range(N):
    for j in range(i+1):
        if dp1[ec(j,i+1)] == -1:
            continue
        dp2[i+1] = min(dp2[i+1], dp2[j]+1)
print(dp2[-1])