Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

LeetCode Weekly Contest No.157

考察の訓練です。方針案のみ示します。実装意味ない。

https://leetcode.com/contest/weekly-contest-157

C

問題

N2グリッドに0から100以下の整数が並べてある。あなたは好きな位置からはじめて、上下左右に動ける。ただし、すでに訪れたところは0になり、0のマスには行くことが出来ない。

制約: N=15, 0以外のマスはたかだか25個

方針(案)

状態は、グリッドの状態とどこにいるか(225とおり)で表すことが出来る。はいDP、では終わらない。グリッドの状態があるなしを考えた時点で2225で爆発してる。

おもむろに制約の0以外のマスは25個しかないことに気づく。すると225=107の状態に落ちる。このビットDPをする。(例えば、まだ0じゃないところを1とする)

さらにビットマスク自体が今いる場所を表しているため、4 x 25 x 7乗????めでたくTLEですね。はて?実際にマスクのうち0のところは減っていくから、これで間に合うということだろうか。

1010などとなった時に、これを2回しか辿らない魔法があるかは気になる。

例えば、Rustのtrailing_zerosなんかはCPUの命令を使ってるだろうから、あとはその分シフトするというのでどうかなぁ?

こんな感じ。

fn main()
{
    let mut x: i64 = 0b11000001;
    let mut i = 0;
    loop {
        if x&1>0 { println!("{}",i); }
        x>>=1;
        if x==0 { break; }
        i+=1;
        let n = i64::trailing_zeros(x);
        i+=n;
        x>>=n;
    }
}

D

問題

aiueoをN個並べて文字列を作る。

この時、それぞれの文字の次における文字は種類が限られている(例:eの次はaかi)

何種類の文字列がありえるか?

制約: N=104

方針(案)

https://atcoder.jp/contests/dp/tasks/dp_cとか、題名は忘れたが1x2のドミノを2xNの領域に敷き詰めていくやつと全く同じに見える。

最後に置いた場所iと最後に置いた文字cを状態とするDPを行うだけではないのかな。105程度で間に合う。

しかしこれだとHardではないから、何か間違ってるんだろうか。