足跡-sokuseki-

りかの日進月歩の記録

技術室奥プログラミングコンテスト #3 E - デフレゲーム

E - デフレゲーム

問題概要

 N 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。
前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。
 1 \le N \le 5 \times 10^5

解法

期待値の線型性より
\displaystyle \sum_{i=1}^N (サイコロを  i 回振ったときの目の総和)  \times  i+1 回目で初めて目が重複する確率)
を求めればよいことがわかる。

サイコロを  i 回振ったときの目の総和は、サイコロを  i 回振ったときの目の総和の期待値を考えると良くて、
サイコロを1回振ったときの目の期待値が  \frac{N+1}{2} なので、サイコロを  i 回振ったときの目の総和の期待値は  \frac{N+1}{2} \times i となる。

また、 i+1 回目で初めて目が重複する確率は、初めの  i 回は目が重複せず、  i+1 回目にいままで出た  i 個の目のうちどれかが出ればいいので
 \frac{N}{N} \times \dots \times \frac{N-i+1}{N} \times \frac{i}{N} = \frac{_{N} P _{i}}{N^i} \times \frac{i}{N}
になる。
よってこれらの積の和が答えとなる。

Submission #4013511 - 技術室奥プログラミングコンテスト #3

競技プログラミング2018総括

2017の総括を書き忘れていたことに最近気付いたので2018の総括を書きます。

今年あったこと

1月
  • RUPC2018のATNDを公開したら1日くらいで枠がいっぱいになって競プロ人口の増加を感じた
2月
  • 競プロサークルの部長になってしまった…
3月
  • 学内の理系ゼミサークル(?)の合宿で競プロ布教講演をしました。学内競プロ人口も増えたんじゃないかな…?
  • RUPC2018がありました。たくさんの競プロerと交流できて楽しかったです。
4月
5月
  • 記憶がないです。死んでたのかもしれません。
6月
  • AtCoder で着水します。長い水色の旅が再び始まった……
7月
8月9月
  • JAG夏合宿・ACPC2018に行きました。ACPCday2の懇親会が楽しすぎた印象があります。
  • インターンで東京にいたり研究室の課題に苦しんだりしていました。
10月
  • こどふぇす予選がありました、今年はさんくすすら行けず……。来年こそはパーカーを得に行きたいです。
11月
  • DDCC予選がありました。DDCC2019行くぜ!(ガタッ
12月

各サイトについて

AtCoder

522AC -> 823AC (+301)
f:id:wk1080id:20181230205347p:plain
Rate: 1556(highest:1556) -> 1474(highest:1618)
f:id:wk1080id:20181230205510p:plain
4月に青くなり6月に着水し、そこからAtCoderのやる気が消滅してしまう…
今年はあんまり埋めが進まなかったので来年はこつこつとやっていきたいですね。

AOJ

299AC -> 427AC (+128)(Course抜きのAC数)
Course合わせた全体だと今488ACかな

ICPCに熱が入りすぎていたのでAOJ-ICPC埋めをずっとやっていました。とくに10月~の右肩上がりがやばいね。f:id:wk1080id:20181230201958p:plain

codeforces

?AC -> 45AC
Rate : 1396(highest:1425) -> 1717(highest:1717)
f:id:wk1080id:20181230211438p:plain

AtCoderのやる気が消滅したのとかいろいろで、12月はcodeforcesのやる気が高い。
12月に青くなったし、これからもこどふぉでがんばっていきたい。

まとめと来年の抱負

青安定をめざしたいのと、着実にACを増やして経験をつみたい。来年も企業コンたくさんいきたいなー!

AtCoder : 1200AC
AOJ : 700AC
codeforces : 250AC
を目標に過去問をたくさん解いていきたいです。

Suffix ArrayのO(NlogN)構築

この記事はCompetitive Programming (1) Advent Calendar 2018 - Adventar の25日目の記事です。

はじめに

競技プログラミングの問題でSuffix Arrayを使う場合、蟻本で紹介されている  O(N log^2 N)の構築で間に合う問題がほとんどです。しかし、 O(N log^2 N)では定数倍高速化をしないとTLEしてしまう問題もあるらしい*1ので、より高速な構築アルゴリズムを紹介したいと思います。

Suffix Arrayの定義

Suffix Arrayを日本語にすると「接尾辞配列」です。
長さ  n の文字列  s の接尾辞は全部で  n 個あります。
たとえば、 s = abracadabra の接尾辞は以下の11個あります。文字列の左にある数は、それぞれの接尾辞のインデックス(文字列  s の何文字目以降か)を表しています。

0 abracadabra
1 bracadabra
2 racadabra
3 acadabra
4 cadabra
5 adabra
6 dabra
7 abra
8 bra
9 ra
10 a

この  n 個の接尾辞をソートした時に、それぞれの接尾辞が辞書順で何番目であるかを配列にしたものが接尾辞配列になります。
文字列  s の接尾辞配列を SA とすると
SA[ i ] = 辞書順で i 番目に小さい接尾辞のインデックス
となります。

たとえば  s = abracadabra の接尾辞配列は以下のようになります。

i SA[i] 接尾辞
0 10 a
1 7 abra
2 0 abracadabra
3 3 acadabra
4 5 adabra
5 8 bra
6 1 bracadabra
7 4 cadabra
8 6 dabra
9 9 ra
10 2 racadabra

接尾辞配列があると文字列検索などが高速でできます。

アルゴリズム

接尾辞のソートと巡回シフト

厳密に言うと、紹介するアルゴリズムは接尾辞をソートするのではなく、文字列の巡回シフトをソートするのですが、これは文字列の末尾に記号$を追加すれば実現できます。ここで、$はどのアルファベットよりも辞書順で小さいことにします。
ソートされた巡回シフトの順序はソートされた接尾辞の順序と等しくなります(接尾辞は巡回シフトにおける$以降を無視したものと同じなので)。

例えば、 dabbb の巡回シフトと接尾辞をソートしたものは以下のようになります。

1.  abbb$d  abbb
4.  b$dabb  b
3.  bb$dab  bb
2.  bbb$da  bbb
0.  dabbb$  dabbb

巡回シフトをソートするために、巡回部分文字列について考えます。
 s の部分文字列についてs[  i … j ]という表記をします。ここで i > j のときは文字列s[ i … n-1 ]と文字列s[ 0 … j ]を連結したものを表します。
(以下では適宜、文字列のインデックスはmod  n の値と考えてください)

このアルゴリズム \lceil log n \rceil + 1 回の反復が行われます。 k 番目( k = 0 … \lceil log n \rceil )の反復では、 s の長さ 2^kの巡回部分文字列  n 個をソートします。最後の  \lceil log n \rceil 番目の反復では、長さ2^{\lceil log n \rceil}の部分文字列がソートされます。 n \le 2^{\lceil log n \rceil}より、これは巡回シフト全体をソートすることと同じです。

巡回シフトのソートに使用する配列

p[  i ] を、長さが  2^k である部分文字列のうち、辞書順で  i 番目となる部分文字列のインデックスとします。
例えば  s = aaba  k = 2 のとき  p = (3, 0, 1, 2) となります。

アルゴリズムの各反復では、順列p[ ]に加えて、配列c[ ]も保持します。c[ i ]は  i 番目の部分文字列が属する同値類に相当します。この同値類は0から始まる数で管理され、ある文字列が別の文字列より辞書順で小さい場合は同値類のラベルも小さくなり、2つの文字列が等しい場合は等しくなります。
なぜ同値類を意識する必要があるかというと、部分文字列の中には全く同じ文字列も含まれていて、アルゴリズムはそれらを等しく扱う必要があるからです。
以下のソースコードでは、同値類の数はclassesという変数に保存されます。

 s = aabaのとき、それぞれの反復における部分文字列、p[ ]、c[ ]は以下のようになります。

k = 0 : (a,a,b,a)
        p = (0,1,3,2), c = (0,0,1,0)

k = 1 : (aa,ab,ba,aa)
        p = (0,3,1,2), c = (0,1,2,0)

k = 2 : (aaba,abaa,baaa,aaab)
        p = (3,0,1,2), c = (1,2,3,0)

重要な点は、p[ ]の値がすべて異なるということです。
また、たとえば、 k = 0 のとき、p[ ]は(3, 1, 0, 2)でも(3, 0, 1, 2)でも良いです。等しい部分文字列のp[ ]の値は入れ替わっても問題ありません。等しい部分文字列であるかどうかはc[ ]が管理しているからです。

巡回シフトのソートアルゴリズム

文字列  s を引数にして、巡回シフトをソートした順列を返す関数sort_cyclic_shiftsを考えます。
最初(  k=0 のとき)は長さ1の部分文字列をソートします。長さ1の部分文字列の種類は多くないので、カウントソートを使うと  O(N) で実装できます。カウントソートでは、各文字について文字列に何回出現するかを数え、この情報を使ってp[ ]を構築します。その後、p[ ]を使ってc[ ]を構築します。

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);

    //k=0のソート

    for (int i = 0; i < n; i++){
        cnt[s[i]]++;
    }
    for (int i = 1; i < alphabet; i++){
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i < n; i++){
        p[--cnt[s[i]]] = i;
    }
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]]){
            classes++;
        }
        c[p[i]] = classes - 1;
    }

    //以下k=1…logn+1の反復をする(省略)

}

 k-1 回目の反復をしてp[ ]とc[ ]が求められたとき、 O(N)  k 回目の配列の値を求めたいです。これが実現できれば、反復は  \lceil log n \rceil + 1 回実行されるので全体の計算量は O(NlogN) になります。

これを行う際の重要な点は、長さ  2^k の巡回部分文字列は、長さ  2^{k-1} の2つの巡回部分文字列から構成されるということです。そして、前のステップで得た長さ 2^{k-1} の巡回部分文字列に対応する配列c[ ]の値の情報を使うと、長さ  2^k の巡回部分文字列をO(1)で比較することができます。
したがって、位置  i と位置  j で始まる長さ  2^k の2つの部分文字列を比較するときは  (c[i], c[i+2^{k−1}]) のペアと (c[j], c[j+2^{k−1}]) のペアを比較すれば良いです。

f:id:wk1080id:20181221153344p:plain

では実際に  k 回目の配列の値はどうやって求めるといいのでしょうか。これは非常に簡単な解決法があり、長さ  2^k の部分文字列をこれらの数値のペアでソートします。これにより、次のp[ ]を得ることができます。ただし、通常のソートを使うと  O(NlogN) になってしまうので工夫が必要です。ペアの要素は高々  n なので、再びカウントソートをすることができますが、カウントソートを用いるよりも効率的な方法が存在します。

ここでは基数ソートの基礎となるテクニックを使います。
ペアのソートをするために、まずペアの2つ目の要素に着目してペアを並べ替え、その後で1つ目の要素を使って並べ替えます。(1つ目の要素のソートは安定ソートでなければいけません。安定ソートだと等しい要素の相対的な順序を変えることなくソートできるので、初めに行った2つ目の要素でのソートの順番を生かすことができます。)
しかし、ペアの2つ目の要素は  k-1 回目のステップですでにソートされていました。したがって、2つ目の要素によってペアをソートするためには、p[ ]の値から  2^{k-1}を引くだけで良いです。(長さ  2^{k-1} の辞書順最小の部分文字列が位置  i からはじまるとき、長さ  2^k の部分文字列の後半の辞書順最小の部分文字列が始まる位置は  i - 2^{k-1} になります。)
よって、単純な減算だけでp[ ]におけるペアの2つ目の要素をソートできます。次に1つ目の要素によって安定ソートを実行する必要があります。これはカウントソートで実現できます。


例えば  s = aaba  k = 2 のときを考えます。 k = 1 のとき p[ ]とc[ ]はそれぞれ(0,3,1,2), (0,1,2,0)だったとします。位置  i から始まる長さ4の巡回部分文字列は (c[i], c[i+2]) のペアを見ればよいので、

i ペア 対応する部分文字列
0 (0,2) (aa, ba)
1 (1,0) (ab,aa)
2 (2,0) (ba,aa)
3 (0,1) (aa,ab)

となります。
2つ目の要素によってペアをソートするためには、p[ ]の値から  2^{k-1} = 2 を引けば良いので  p = (0,3,1,2)  (2,1,3,0) になります。よって  i = 2, 1, 3, 0 について (c[i], c[i+2]) のペアを見ると

i ペア 対応する部分文字列
2 (2,0) (ba,aa)
1 (1,0) (ab,aa)
3 (0,1) (aa,ab)
0 (0,2) (aa, ba)

となり、2つ目の要素でソートできました。あとは1つ目の要素を使ってカウントソートをすれば、ペアのソートが完了します。

p[ ]が計算できたので、残るはc[ ]ですが、これは  k=0 のときと同様に、p[ ]を順に調べて隣接するペアを比較すれば計算できます。

以下は残りの実装です。一時的な配列pn[ ]とcn[ ]を使用して、2つ目の要素と新しい同値類c[ ]のインデックスの順列を保存しておきます。

vector<int> sort_cyclic_shifts(string const& s) {
    int n = s.size();
    const int alphabet = 256;
    vector<int> p(n), c(n), cnt(max(alphabet, n), 0);

    //k=0のソート

    for (int i = 0; i < n; i++){
        cnt[s[i]]++;
    }
    for (int i = 1; i < alphabet; i++){
        cnt[i] += cnt[i-1];
    }
    for (int i = 0; i < n; i++){
        p[--cnt[s[i]]] = i;
    }
    c[p[0]] = 0;
    int classes = 1;
    for (int i = 1; i < n; i++) {
        if (s[p[i]] != s[p[i-1]]){
            classes++;
        }
        c[p[i]] = classes - 1;
    }


    //以下k=1…logn+1の反復をする
    vector<int> pn(n), cn(n);
    for (int k = 0; (1 << k) < n; ++k) {
        for (int i = 0; i < n; i++) {
            pn[i] = p[i] - (1 << k);
            if (pn[i] < 0){
                pn[i] += n;
            }
        }
        fill(cnt.begin(), cnt.begin() + classes, 0);
        for (int i = 0; i < n; i++){
            cnt[c[pn[i]]]++;
        }
        for (int i = 1; i < classes; i++){
            cnt[i] += cnt[i-1];
        }
        for (int i = n-1; i >= 0; i--){
            p[--cnt[c[pn[i]]]] = pn[i];
        }
        cn[p[0]] = 0;
        classes = 1;
        for (int i = 1; i < n; i++) {
            pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << k)) % n]};
            pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << k)) % n]};
            if (cur != prev){
                ++classes;
            }
            cn[p[i]] = classes - 1;
        }
        c.swap(cn);
    }
    return p;
}
最後の処理

前述の通り、このアルゴリズムは接尾辞をソートするのではなく、文字列の巡回シフトをソートします。そのため、与えられた文字列の末尾に、どのアルファベットよりも辞書順で小さい記号$を追加しています。なので、巡回シフトをソートし終わった順列の先頭は、$から始まる巡回シフトになっています。つまり、ソートが終わった後の順列の先頭を最後に取り除く必要があります。それが終われば接尾辞配列の構築は終了になります。

vector<int> suffix_array_construction(string s) {
    s += "$";
    vector<int> sorted_shifts = sort_cyclic_shifts(s);
    sorted_shifts.erase(sorted_shifts.begin());
    return sorted_shifts;
}

計算量について

このアルゴリズムは時間計算量  O(NlogN) 、空間計算量  O(N) です。文字列に使われる文字が少なければ少ないほど(たとえばアルファベットの小文字しか使われないなど)、計算量は小さくなります。

実装例

実装量は蟻本のやつとあんまり変わらないです。

参考文献

この記事の内容は以下のページの日本語訳+αです。構築後に問題に応用する部分の説明も詳しく載っています。また、codeforcesなどの問題も載っています。
Suffix Array - Competitive Programming Algorithms
このページには接尾辞配列をつくるときの文字列には$がないのでこの記事でもそういう説明にしていますが、蟻本とかその他の書籍を見ると大体の場合$も接尾辞配列に含まれています。どっちがいいのかよくわかってないです。

最後に

今日12/25はアドベントカレンダー最終日かつクリスマスです。
それなのにほぼ英語を日本語に直しただけの記事で終わりにするのは少し心苦しいので、昔につくったSA-IS*2の解説スライドを手直ししたやつも貼っておきます。ぜひ読んでください。
SA-IS.pdf - Google ドライブ
それではみなさん、素敵なクリスマスと素敵な年末をお過ごしください。

*1:A - IOIOIが険しいらしい

*2:接尾辞配列を  O(N) で構築するアルゴリズム

ICPC2018 アジア地区横浜大会 参加記

12/8~10に行われたICPC2018アジア地区横浜大会にpriMe.caTというチームで参加しました。
Asia Yokohama Regional Contest 2018 | ACM-ICPC 2018 Asia Yokohama Regional

国内予選の様子→ACM-ICPC 2018 国内予選 参加記 - 足跡-sokuseki-

ぼくは初めてのアジア地区でしたが、める先輩とT.M先輩は昨年もアジア地区に出場し15位を取っていたので、その順位を上回りたいなあという目標が密かにありました。

チーム練

アジア地区を見据えた初めてのチーム練はJAG夏合宿(JAG夏合宿2018 / 会津合宿2018 参加記 - 足跡-sokuseki-)でした。
夏休みが明けてから、週2のサークルの活動でAOJ-ICPCの英語の問題を解いていました。
本番まで2週間を切ったあたりから5時間セットをやりました(codeforcesの北ユーラシアのミラーとLive Archiveにあったアジア地区の過去問を4セット)。

day1

受付が13時~14時なので当日入りで間に合うため朝から新幹線。


昼食を北大の人たちと食べようと思っていたんですが、飛行機が欠航/遅延になる罠があったらしく険しい感じになる。

たぶさんとえびちゃんとめる先輩と4人で中華街に行く。


中華料理を楽しむ。やさいをたべる。

中華街ではいたるところで豚まんが売られていておいしそうだなあと思っていたんですが、受付時間が迫っていることに気づき会場に向かう。

会場についたらすぐにチームの写真を撮った。運営はオタクに厳しい。

開会式が始まるまでは知り合いと†オフ会†をしていた。マスコットとして雛鶴あいちゃんのフィギュアを持ち込んでいる人がいておもしろかった。

開会式では英語で注意事項とかスケジュールとかを話していたみたいなんですが、英語ができないのでよくわかりませんでした。気づいたらpracticeが始まっていた。
エディタの設定やTLやMLの確認、ライブラリの整理をしていました。印刷クエリをたくさん投げてた。

practiceが終わるとチーム紹介が始まる。大学名の辞書順で、前に出て英語でチーム紹介する間にスライドが各モニターに映るという感じだった。ネタに走っている人が多くて面白かったけど、席が一番後ろで前に立っている人が一切見えなかったのが悲しかったです。
ぼくはチーム紹介中に頭にティッピーを乗せる仕事をしていました。
チーム紹介フェーズの途中にカツやお菓子やアイマスクなんかが配られていて意味不明だった。これは何ですか?




これは暁美ほむらです。



チーム紹介が終わるとすぐに解散だったので、ホテルに向かう。
どうして横浜に来て天一なんてたべているのか…(ホテルの近くでおいしそうな匂いがしていたのがすべて悪い)


そのあと夜ご飯を食べました。ラーメンは夜ご飯じゃないです。

ABCがあって、時間がいい感じにこどふぉったので出ました。
えらいので日付が変わる前におふとんいんしました。

day2

7時半くらいにおきる。
会場に行く。会場についたらすぐ電子機器を預けたので写真とったりとかツイートしたりできなかったです。かなしい。




以下コンテスト。

始まってすぐAをぼくが読んでBをT.M先輩が読んでエディタの設定やテンプレ写経をめる先輩がする。Aはやるだけなのでとりあえず実装してもらう。その間にCをT.M先輩が、D以降をぼくが読んでいく。Aを提出するとWAって、実装を聞いてもまちがっているところがよくわからなかったので先にBを実装してもらう。ぼくはAのコーナーケースを考えるやつをする。Bの実装が終わったらしく提出したらTLE。チームが不穏な感じになる。Aでどういうケースがだめなのかを調べる。Cの解法もわかったらしいのでそっちを実装してもらう。AC。Aのミスも発見できてAC。Bもなんか工夫して提出したらACできたみたい。1時間以内に3ACできてよかったけどペナルティが結構大きくて険しい雰囲気になる。
順位表からGが簡単そうな感じだったのでGをやる。Gは転倒数みたいな感じでBITを持てばできるのでやる、AC。この段階で上位チームがDとEとKを解いていたので考える。3人でしばらく考えて、Kは前から順番に考えて行ったらできそうな感じがするのに対し、Dは文字列が1つだとできそうだけど2つになったらわからない、Eは補グラフを考えてフロー?みたいな話になる。Kを実装してもらうことにする。このくらいからIJのACが増えてきてとりあえず目を通す。わかんない。AC数の多いDとEを考える。KがACする。再び3人で考察する。残り2時間弱くらい。
DがDPぽいという話になるけど遷移がよくわからないなあとなる、Eは頂点数が奇数のときは完全グラフにすればよくて、偶数のときは完全グラフにしてから辺をn/2個削ればいいという方針になるけど具体的なやり方がわからない。煮詰まったのでIとJの問題概要を2人に共有して考えてみるけどこっちも良い方針が立たない。しばらくして順位表が凍結し、順位表DのAC数がKとあまりかわらないしなんとかしてDを通したいなあとなるけど、何も浮かばず無を過ごしていました。

コンテストが終わって隣の建物に移動し、解説を聞く。英語なのでスライドの雰囲気で理解しようと努める(無理)。偉い人や企業の人のお話をきく。みなさん英語が流暢だなあという感想を抱く。最後にyes/noがあってぼくたちはnosubなのであんまり関係ないなあと思っていたけど、知り合いのチームや優勝争いのチームのyes/noは盛り上がって楽しめたのでよかったです。

f:id:wk1080id:20181212014843p:plain

結果は5完17位で、Dを通せていたら3つくらい順位があがった、という感じでした。Dは実装ではなく考察なのでもっと考察力があればなあという後悔が強いです。


結果発表後、コンテストをしていた会場に戻って企業賞の発表と集合写真の撮影がありました。priMe.caTが突然呼ばれてよくわからないまま壇上にあがったけど(全部英語なので何もわからない)、どうやらGoogleの企業賞をもらえたようです。Google Home Miniをいただけました。

そのあとはclosing partyで乾杯をした後、各企業ブースを回りました。ニコニコのマスコット(?)とindeedTシャツをゲットできたのはよかったです。ドワンゴボドゲが最初から最後まで盛り上がっていてすごかった。勝ったらカチューシャもらえるらしくて欲しかったんですがボドゲわからないので仕方ない…。あとは い つ も の をしていたり、マスコットオフ会をしたりしていました。

closing partyも終わり、解散の時間になったので解散しました。

そのあとは10人くらいで横浜に戻ってゲーセン旅行をしました。

みんなと別れてホテルに戻るをする。企業ブースで大量の荷物をもらったのでホテルについた頃には体が壊れた。

youtubeのコンテスト中継を見て寝た。

day3

3日目は企業見学で、bitFlyerindeed → LINE でした。



きゅうりさんの頭にティッピーを乗せるをした。


社内をあんまり撮れないからマスコットの写真を撮りがち。
企業見学が終わって、同じグループのメンバーとサイゼ。



各大学の強い人の話や企業コンの話をして盛り上がった。


その後みんなと別れ、秋葉原に行った。てんぷらさんと初エンカ。

そんな感じでICPCが終了しました。


最後に

priMe.caTは今年限りのチームですが、とても楽しくて、たくさんの思い出ができました。
また、横浜大会はいろんな人と会うことができて、新しい知り合いができたりみんなで遊んだりして充実した3日間でした。交流していただいたみなさんありがとうございました。
ぼくは来年もICPC出場資格があるので、チームメンバーは変わってしまいますが、また横浜大会に来たいし、そのためにいっぱい頑張ろうと思いました。

AOJ2321 Butterfly

Butterfly | Aizu Online Judge

問題概要

 N 個の用事があり、  i 個目の用事は時間が  M_i 区間拘束され、  j 個目の区間 s_j 時から  e_j 時である。また  i 個目の用事をすると満足度が  L_i 得られる。
時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。

制約

 1 \le N \le 100
 1 \le M_i \le 16
 1 \le L_i \le 10^8
 6 \le S_i < E_i \le 22

解法

制約から、時間は16個しかないので

dp[i][j] := i個目の用事までするかしないか決めたときに拘束される時間がjの状態のときに得られる最大の満足度

とするbitDPをすると、状態は  N \times 2^{16} 個しかないので間に合う。
入力で  i 個目の用事の区間を受け取るときに、bitに変換しておく( 6+j 時から  6+j+1 時まで拘束されるときに  j ビット目を1にする)と、遷移できるかどうかは&をとればわかるので楽になる。

AIZU ONLINE JUDGE: Code Review

AOJ1336 The Last Ant

The Last Ant | Aizu Online Judge

問題概要

長さ  l cmのトンネルに蟻が  n 匹いる。最初、蟻  i はトンネルの左端から  p_i cmの場所に向き  d_i の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で蟻と蟻が逆向きに歩いて来るとき、その場所が広い場所だと2匹の蟻はすれ違うことができるが、狭い場所だと2匹の蟻はすれ違うことはできず、衝突して今までと逆を向くことになる。

与えられた状態から同時に蟻が動き出すとき、トンネルを最後に出る蟻の番号と、その蟻がトンネルを出るまでにかかる時間を答えよ。

制約

 1 \le n \le 20
 n + 1 \le l \le 100
 d_i は"L"(左向き)または"R"(右向き)
 1 \le p_1 < p_2 < ... < p_n \le l - 1

解法

蟻本の最初に載っているAntsという問題を知っていると、どの蟻についても、トンネルから出る時間がトンネルの長さより大きくなることはないということがわかります。
よって、1秒後から  l 秒後までのすべての時間について、各蟻がどの場所でどの方向を向いているのかをシミュレーションしてあげると良いです。
計算量は  O(l^2) となります。

AIZU ONLINE JUDGE: Code Review

AOJ1237 Shredding Company

Shredding Company | Aizu Online Judge

問題概要

整数  t と数字のみからなる文字列  num が与えられる。文字列  num をいくつかの箇所で分割し、分割後の数の総和が  t 以下になるようにするとき、総和の最大値とそのときの分割の仕方を答えよ。なお、分割後の数の総和が  t 以下にならないときは"error"、答えとなる分割の仕方が複数存在するときは"rejected"と出力せよ。

制約

 t < 10^6
 | num | \le 6

解法

分割の仕方は高々  2^{|num|-1} 通りなので、全て試して、総和が  t 以下になる最大のものを調べてあげればよいです。
AIZU ONLINE JUDGE: Code Review