俵言

しがない社会人が書く、勉強とかのこと。最近は機械学習や kaggle 関連がメイン。

SRM684 div2 参加記

ブログ書くのもう三ヶ月ぶりくらいですね。

とりあえずどうにか卒業出来ることが決まり、めっちゃ久々にSRM に参加しました。

せっかくなので久々に参加記も書くことにします。

Easy (250) - Istr

問題概要

アルファベットの文字列  S に対して、文字列に含まれる各アルファベットの数の二乗の総和をその文字列のスコアとする。この文字列から文字を  k 個削除してスコアを最小にせよ。

制約

 1 \le |S| \le 50,  0 \le k \le |S|, 文字列に含まれるのは "a - z" のアルファベットのみ

解法

含まれる数の多いアルファベットから一個ずつ減らしていけばよい。制約が緩いので、一回削除するごとにソートしてました。

実装

class Istr:
    def count(self, s, k):
        cnt = collections.Counter(s)
        l = cnt.values()
        l.sort()
        for i in xrange(k):
            if l[-1] == 0: break
            l[-1] -= 1
            l.sort()
        return sum(i**2 for i in l)

 0 \le k \le |S| だから if 文の判定が実は要らないってあとから気付きました。まあ実害は無いですが。

Med (600) - DivFreed2

問題概要

以下の条件を満たす長さ n の数列 a_n は何通り作れるか。10^9+7で割った余りを答えよ。

  •  1 \le i \le n について  1 \le a_i \le k
  •  1 \le i \le n-1 について  a_i  \le a_{i+1} または  a_i \bmod a_{i+1} \ != 0

制約

 1 \le n \le 10, 1 \le k \le 10^5

解法

a_n を先頭から順番に決めていくとき、 a_{i+1} は直前の  a_i にのみ依存します。もう明らかにDPの匂いがプンプンする。

末尾の値が t であるような問題文の条件を満たす長さ (i+1) の数列の数を dp[i+1][t]とすると、dp[i+1][t]は以下のいずれかを満たす s に対する dp[i][s] の総和になります。

  •  s \le t
  •  s \bmod t \ != 0

問題は各 t に対して s がこれらの条件を満たしているかを全てのsについて確かめると、計算量が  O(n \ k^2)になってTLEすること。この部分で工夫が必要です。

この問題を解決するために累積和を用います。一つ目の条件を満たすsに対するdp[i][s]の総和については、先にdp[i][s]の累積和を小さい方から取っておけば  O(1)で答えられます。

ポイントとなるのは二つ目の条件の方の求め方です。一つ目の条件を満たさないかつ二つ目の条件を満たすsに対するdp[i][s]の総和は、

( s > t かつ  s \bmod t \ != 0 を満たす sに対する dp[i][s]の総和) =

( s > t を満たす sに対する dp[i][s]の総和) - ( s > t かつ  s \bmod t \ = 0 を満たす sに対する dp[i][s]の総和)

と考えてやることで簡単に求められます。

( s > t を満たす sに対する dp[i][s]の総和)については、一つ目の条件のときと同様に先にdp[i][s]の累積和を大きい方から取っておけば  O(1)で答えられます。

( s > t かつ  s \bmod t \ = 0 を満たす sに対する dp[i][s]の総和)については、要するに t の倍数であるような s に対する dp[i][s]の総和です。tの倍数を順番に確かめるのは  O(\log_t k) で行えるので、t+1 から k まで全部確かめるよりも計算量が格段に減ります。

以上により計算量は大体  O(n k \log k) となるのでTLEを脱せます。ちょっとpythonつらそうだったので C++で出しました。

実装

using namespace std;

#define P 1000000007

long long dp[10][100001],acum_u[100002],acum_l[100002];

class DivFreed2 {
    public:
    int count(int n, int k) {
        int i,j,cnt;
        
        long long comp_sum, ans = 0;
        for (i = 0; i < k+1; i++) dp[0][i] = 1;
        dp[0][0] = 0;
        for (i = 1; i < n; i++) for (j = 0; j < k+1; j++) dp[i][j] = 0;
        for (i = 1; i < n; i++){
            for (j = 0; j < k+1; j++) acum_u[j] = acum_l[j] = dp[i-1][j];
            acum_u[k+1] = acum_l[k+1] = 0;
            for (j = 0; j < k; j++){
                acum_l[j+1] = (acum_l[j+1] + acum_l[j]) % P;
                acum_u[k-j-1] = (acum_u[k-j-1] + acum_u[k-j]) % P;
            }
            for (j = 1; j < k+1; j++){
                comp_sum = 0;
                for (cnt=j*2;cnt < k+1;cnt+=j){
                    comp_sum = (comp_sum + dp[i-1][cnt]) % P;
                }
                dp[i][j] += (acum_l[j]%P + ((acum_u[j+1] - comp_sum) % P + P))%P;
                dp[i][j] %= P;
            }
        }
        for (j = 1; j < k+1; j++) ans = (ans + dp[n-1][j]) % P;
        return ans;
    }
};

accumがacumになってるところに英語力の無さを感じる..

Hard (900) - Autohamil

問題概要

0か1のみからなる文字列を読んで動作するある決定性有限オートマトンを考える。このオートマトンの状態は 0 から n-1 の計 n 個で、状態 iのときに0を読むと状態 z0[i] に、1を読むとz1[i]に遷移する。

このとき、全ての状態にちょうど一回だけなるような文字列が存在するか?

制約

 1 \le n \le 50, |z_0| = |z_1| = n, 0 \le z_{0 i} , z_{1 i} \le n-1

感想

解けなかったので感想だけ。問題概要があまり概要になってませんが、要はこのオートマトンの状態遷移図を有向グラフと見たときに、ハミルトン路が存在するか?という問題。今気付いたんですが、よくみたら問題名もAuto''hamil''でちゃんとハミルトンって主張してました笑

正直全然分からなかったのとMedバグらせて時間無かったのもあって手がつけられませんでした。また挑戦したいと思います。

まとめ

結果はdiv2 50位でレートも50ほど上がったので久々にしては頑張った方だと思いたい。ただしょうもないミスでバグらせるのはいい加減止めたいなあと思います。

レートが1163になり、やっと青くなるチャンスが巡ってきました。次こそはdiv1に上がれるようがんばります!