Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)
問題概要
頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。
木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成できる辺の取り除き方は何通り存在するか?
制約
木には赤の頂点と青の頂点がそれぞれ1つ以上存在する
解法
まず、木に存在する全ての赤を含む最小の連結成分と、木に存在する全ての青を含む最小の連結成分を作り、作った連結成分の頂点は赤や青に変えてしまいます。これは帰りがけdfsで、自分の子孫に赤/青の頂点があるか?を調べながら色ぬりをしてあげるとよいです。
このとき、赤の連結成分と青の連結成分の両方に含まれる頂点が存在した場合、答えとなるような辺は存在しないので、この時点で 0 を出力してプログラムを終了します。
赤と青の連結成分がそれぞれ 1 つになったあと、答えとなる辺を探索します。
赤の連結成分と青の連結成分を繋ぐパスは必ず 1 つだけ存在し、そのパスに含まれる辺が問題の条件をみたす辺になるので、パスを探してその長さを出力します。
まず、与えられる辺を順に見ていきます。
辺に繋がっている2つの頂点が同じ色の場合は、その辺は求めるパスに含まれていないことが明らかなので何もしません。2つの頂点がどちらも塗られていない場合も何もしません(この辺が求めるパスに含まれているケースも存在しますが、そのときは求めるパスの長さが 3 以上であり、この辺で探索しなくても良く、別の辺のときに求めるパスであるかを判定します)。
そうでない場合で、2つの頂点が赤と青の場合は、この辺がパスになるので 1 が答えになります。
上のどちらでもない場合は、この辺が求めるパスに含まれているかを探索します。片方の頂点が赤でもう片方の頂点は塗られていない頂点の場合、色が塗られていない頂点から赤の頂点とは反対方向に、青の頂点が見つかるまで探索します。ここで、青の頂点が見つかれば、最初の赤の頂点から見つけた青の頂点までのパスが求めるパスなので、そのパスの長さを出力します。
もし見つからなければ、この辺は求めるパスに含まれる辺ではないことがわかるので、別の辺を探索します。
「今見ている辺が求めるパスに含まれているか?」を調べる回数は、与えられる木によっては多くなることがありますが、全体でそれぞれの辺は高々2回ずつしか見ないので、辺に繋がっている2つの頂点の色が違うときに毎回調べても になります。
技術室奥プログラミングコンテスト #3 E - デフレゲーム
問題概要
面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。
前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。
解法
期待値の線型性より
(サイコロを 回振ったときの目の総和) ( 回目で初めて目が重複する確率)
を求めればよいことがわかる。
サイコロを 回振ったときの目の総和は、サイコロを 回振ったときの目の総和の期待値を考えると良くて、
サイコロを1回振ったときの目の期待値が なので、サイコロを 回振ったときの目の総和の期待値は となる。
また、 回目で初めて目が重複する確率は、初めの 回は目が重複せず、 回目にいままで出た 個の目のうちどれかが出ればいいので
になる。
よってこれらの積の和が答えとなる。
競技プログラミング2018総括
2017の総括を書き忘れていたことに最近気付いたので2018の総括を書きます。
今年あったこと
1月
- RUPC2018のATNDを公開したら1日くらいで枠がいっぱいになって競プロ人口の増加を感じた
2月
- 競プロサークルの部長になってしまった…
3月
- 学内の理系ゼミサークル(?)の合宿で競プロ布教講演をしました。学内競プロ人口も増えたんじゃないかな…?
- RUPC2018がありました。たくさんの競プロerと交流できて楽しかったです。
4月
- AtCoderで念願の青!!!!!!!
- AtCoder Rating Comparisonをつくりました。
5月
- 記憶がないです。死んでたのかもしれません。
6月
- AtCoder で着水します。長い水色の旅が再び始まった……
7月
- ICPC国内予選がありましたね。
8月9月
- JAG夏合宿・ACPC2018に行きました。ACPCday2の懇親会が楽しすぎた印象があります。
- インターンで東京にいたり研究室の課題に苦しんだりしていました。
10月
- こどふぇす予選がありました、今年はさんくすすら行けず……。来年こそはパーカーを得に行きたいです。
11月
- DDCC予選がありました。DDCC2019行くぜ!(ガタッ
12月
- ICPC2018のアジア地区横浜大会に行きました。
- はじめて アドベントカレンダーをかきました。接尾辞配列がちょっとわかってきた感がある。
- まだ完成してないのでおおっぴらにしてないんですが、こんなものをつくっています。来年の精進に生かすぞ。
各サイトについて
AtCoder
522AC -> 823AC (+301)
Rate: 1556(highest:1556) -> 1474(highest:1618)
4月に青くなり6月に着水し、そこからAtCoderのやる気が消滅してしまう…
今年はあんまり埋めが進まなかったので来年はこつこつとやっていきたいですね。
AOJ
299AC -> 427AC (+128)(Course抜きのAC数)
Course合わせた全体だと今488ACかな
codeforces
?AC -> 45AC
Rate : 1396(highest:1425) -> 1717(highest:1717)
AtCoderのやる気が消滅したのとかいろいろで、12月はcodeforcesのやる気が高い。
12月に青くなったし、これからもこどふぉでがんばっていきたい。
まとめと来年の抱負
青安定をめざしたいのと、着実にACを増やして経験をつみたい。来年も企業コンたくさんいきたいなー!
AtCoder : 1200AC
AOJ : 700AC
codeforces : 250AC
を目標に過去問をたくさん解いていきたいです。
Suffix ArrayのO(NlogN)構築(とおまけでSA-IS)
この記事はCompetitive Programming (1) Advent Calendar 2018 - Adventar の25日目の記事です。
はじめに
競技プログラミングの問題でSuffix Arrayを使う場合、蟻本で紹介されている の構築で間に合う問題がほとんどです。しかし、では定数倍高速化をしないとTLEしてしまう問題もあるらしい*1ので、より高速な構築アルゴリズムを紹介したいと思います。
Suffix Arrayの定義
Suffix Arrayを日本語にすると「接尾辞配列」です。
長さ の文字列 の接尾辞は全部で 個あります。
たとえば、 の接尾辞は以下の11個あります。文字列の左にある数は、それぞれの接尾辞のインデックス(文字列 の何文字目以降か)を表しています。
0 | abracadabra |
1 | bracadabra |
2 | racadabra |
3 | acadabra |
4 | cadabra |
5 | adabra |
6 | dabra |
7 | abra |
8 | bra |
9 | ra |
10 | a |
この 個の接尾辞をソートした時に、それぞれの接尾辞が辞書順で何番目であるかを配列にしたものが接尾辞配列になります。
文字列 の接尾辞配列を SA とすると
SA[ i ] = 辞書順で i 番目に小さい接尾辞のインデックス
となります。
たとえば の接尾辞配列は以下のようになります。
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 |
接尾辞配列があると文字列検索などが高速でできます。
アルゴリズム
接尾辞のソートと巡回シフト
厳密に言うと、紹介するアルゴリズムは接尾辞をソートするのではなく、文字列の巡回シフトをソートするのですが、これは文字列の末尾に記号$を追加すれば実現できます。ここで、$はどのアルファベットよりも辞書順で小さいことにします。
ソートされた巡回シフトの順序はソートされた接尾辞の順序と等しくなります(接尾辞は巡回シフトにおける$以降を無視したものと同じなので)。
例えば、 の巡回シフトと接尾辞をソートしたものは以下のようになります。
1. abbb$d abbb 4. b$dabb b 3. bb$dab bb 2. bbb$da bbb 0. dabbb$ dabbb
巡回シフトをソートするために、巡回部分文字列について考えます。
の部分文字列についてs[ ]という表記をします。ここでのときは文字列s[ ]と文字列s[ ]を連結したものを表します。
(以下では適宜、文字列のインデックスはmod の値と考えてください)
このアルゴリズムは回の反復が行われます。 番目()の反復では、 の長さ の巡回部分文字列 個をソートします。最後の 番目の反復では、長さの部分文字列がソートされます。より、これは巡回シフト全体をソートすることと同じです。
巡回シフトのソートに使用する配列
p[ ] を、長さが である部分文字列のうち、辞書順で 番目となる部分文字列のインデックスとします。
例えば は のとき となります。
アルゴリズムの各反復では、順列p[ ]に加えて、配列c[ ]も保持します。c[ ]は 番目の部分文字列が属する同値類に相当します。この同値類は0から始まる数で管理され、ある文字列が別の文字列より辞書順で小さい場合は同値類のラベルも小さくなり、2つの文字列が等しい場合は等しくなります。
なぜ同値類を意識する必要があるかというと、部分文字列の中には全く同じ文字列も含まれていて、アルゴリズムはそれらを等しく扱う必要があるからです。
以下のソースコードでは、同値類の数はclassesという変数に保存されます。
のとき、それぞれの反復における部分文字列、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[ ]の値がすべて異なるということです。
また、たとえば、 のとき、p[ ]は(3, 1, 0, 2)でも(3, 0, 1, 2)でも良いです。等しい部分文字列のp[ ]の値は入れ替わっても問題ありません。等しい部分文字列であるかどうかはc[ ]が管理しているからです。
巡回シフトのソートアルゴリズム
文字列 を引数にして、巡回シフトをソートした順列を返す関数sort_cyclic_shiftsを考えます。
最初( のとき)は長さ1の部分文字列をソートします。長さ1の部分文字列の種類は多くないので、カウントソートを使うと で実装できます。カウントソートでは、各文字について文字列に何回出現するかを数え、この情報を使って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の反復をする(省略) }
回目の反復をしてp[ ]とc[ ]が求められたとき、 で 回目の配列の値を求めたいです。これが実現できれば、反復は 回実行されるので全体の計算量は になります。
これを行う際の重要な点は、長さ の巡回部分文字列は、長さ の2つの巡回部分文字列から構成されるということです。そして、前のステップで得た長さ の巡回部分文字列に対応する配列c[ ]の値の情報を使うと、長さ の巡回部分文字列をO(1)で比較することができます。
したがって、位置 と位置 で始まる長さ の2つの部分文字列を比較するときは のペアと のペアを比較すれば良いです。
では実際に 回目の配列の値はどうやって求めるといいのでしょうか。これは非常に簡単な解決法があり、長さ の部分文字列をこれらの数値のペアでソートします。これにより、次のp[ ]を得ることができます。ただし、通常のソートを使うと になってしまうので工夫が必要です。ペアの要素は高々 なので、再びカウントソートをすることができますが、カウントソートを用いるよりも効率的な方法が存在します。
ここでは基数ソートの基礎となるテクニックを使います。
ペアのソートをするために、まずペアの2つ目の要素に着目してペアを並べ替え、その後で1つ目の要素を使って並べ替えます。(1つ目の要素のソートは安定ソートでなければいけません。安定ソートだと等しい要素の相対的な順序を変えることなくソートできるので、初めに行った2つ目の要素でのソートの順番を生かすことができます。)
しかし、ペアの2つ目の要素は 回目のステップですでにソートされていました。したがって、2つ目の要素によってペアをソートするためには、p[ ]の値から を引くだけで良いです。(長さ の辞書順最小の部分文字列が位置 からはじまるとき、長さ の部分文字列の後半の辞書順最小の部分文字列が始まる位置は になります。)
よって、単純な減算だけでp[ ]におけるペアの2つ目の要素をソートできます。次に1つ目の要素によって安定ソートを実行する必要があります。これはカウントソートで実現できます。
例えば の のときを考えます。 のとき p[ ]とc[ ]はそれぞれ(0,3,1,2), (0,1,2,0)だったとします。位置 から始まる長さ4の巡回部分文字列は のペアを見ればよいので、
i | ペア | 対応する部分文字列 |
---|---|---|
0 | (0,2) | (aa, ba) |
1 | (1,0) | (ab,aa) |
2 | (2,0) | (ba,aa) |
3 | (0,1) | (aa,ab) |
となります。
2つ目の要素によってペアをソートするためには、p[ ]の値から を引けば良いので は になります。よって について のペアを見ると
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[ ]ですが、これは のときと同様に、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; }
計算量について
このアルゴリズムは時間計算量 、空間計算量 です。文字列に使われる文字が少なければ少ないほど(たとえばアルファベットの小文字しか使われないなど)、計算量は小さくなります。
実装例
実装量は蟻本のやつとあんまり変わらないです。
参考文献
この記事の内容は以下のページの日本語訳+αです。構築後に問題に応用する部分の説明も詳しく載っています。また、codeforcesなどの問題も載っています。
Suffix Array - Competitive Programming Algorithms
このページには接尾辞配列をつくるときの文字列には$がないのでこの記事でもそういう説明にしていますが、蟻本とかその他の書籍を見ると大体の場合$も接尾辞配列に含まれています。どっちがいいのかよくわかってないです。
最後に
今日12/25はアドベントカレンダー最終日かつクリスマスです。
それなのにほぼ英語を日本語に直しただけの記事で終わりにするのは少し心苦しいので、昔につくったSA-IS*2の解説スライドを手直ししたやつも貼っておきます。ぜひ読んでください。
2019/3/15追記:スライドの一部が間違っていたため修正しました。
sais.pdf - Google ドライブ
それではみなさん、素敵なクリスマスと素敵な年末をお過ごしください。
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時なので当日入りで間に合うため朝から新幹線。
きたぜ pic.twitter.com/2wVzuL1wvB
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
昼食を北大の人たちと食べようと思っていたんですが、飛行機が欠航/遅延になる罠があったらしく険しい感じになる。
たぶさんとえびちゃんとめる先輩と4人で中華街に行く。
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
中華料理を楽しむ。やさいをたべる。
うさー!!!! pic.twitter.com/o2ZLq7eEjP
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
もぐもぐ pic.twitter.com/aB3W0FaZuR
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
中華街ではいたるところで豚まんが売られていておいしそうだなあと思っていたんですが、受付時間が迫っていることに気づき会場に向かう。
!!! pic.twitter.com/0wAe5EaSf4
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
会場についたらすぐにチームの写真を撮った。運営はオタクに厳しい。
今日は「今日も1日がんばるぞい」ってかいたTシャツを着る予定だったんですが、着いた瞬間に「写真撮影するからさっさと着替えろ」と言われて泣く泣く脱いだ
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
開会式が始まるまでは知り合いと†オフ会†をしていた。マスコットとして雛鶴あいちゃんのフィギュアを持ち込んでいる人がいておもしろかった。
開会式では英語で注意事項とかスケジュールとかを話していたみたいなんですが、英語ができないのでよくわかりませんでした。気づいたらpracticeが始まっていた。
エディタの設定やTLやMLの確認、ライブラリの整理をしていました。印刷クエリをたくさん投げてた。
今日のpracticeでA問題に"Do you like a cat?"ってclarを投げたら"Absolutely!"って返ってきたのを思い出して一人でウケてる
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
practiceが終わるとチーム紹介が始まる。大学名の辞書順で、前に出て英語でチーム紹介する間にスライドが各モニターに映るという感じだった。ネタに走っている人が多くて面白かったけど、席が一番後ろで前に立っている人が一切見えなかったのが悲しかったです。
ぼくはチーム紹介中に頭にティッピーを乗せる仕事をしていました。
チーム紹介フェーズの途中にカツやお菓子やアイマスクなんかが配られていて意味不明だった。これは何ですか?
記念撮影をしました pic.twitter.com/OqDJfu0CTF
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
これは暁美ほむらです。
チーム紹介が終わるとすぐに解散だったので、ホテルに向かう。
どうして横浜に来て天一なんてたべているのか…(ホテルの近くでおいしそうな匂いがしていたのがすべて悪い)
匂いに釣られてしまった… pic.twitter.com/agJthpP4Zv
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
そのあと夜ご飯を食べました。ラーメンは夜ご飯じゃないです。
夜ご飯です pic.twitter.com/RrOKJHtG2p
— そすうさ(素数うさぎ) (@wk1080id) December 8, 2018
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は盛り上がって楽しめたのでよかったです。
結果は5完17位で、Dを通せていたら3つくらい順位があがった、という感じでした。Dは実装ではなく考察なのでもっと考察力があればなあという後悔が強いです。
結果発表後、コンテストをしていた会場に戻って企業賞の発表と集合写真の撮影がありました。priMe.caTが突然呼ばれてよくわからないまま壇上にあがったけど(全部英語なので何もわからない)、どうやらGoogleの企業賞をもらえたようです。Google Home Miniをいただけました。
そのあとはclosing partyで乾杯をした後、各企業ブースを回りました。ニコニコのマスコット(?)とindeedTシャツをゲットできたのはよかったです。ドワンゴのボドゲが最初から最後まで盛り上がっていてすごかった。勝ったらカチューシャもらえるらしくて欲しかったんですがボドゲわからないので仕方ない…。あとは い つ も の をしていたり、マスコットオフ会をしたりしていました。
昨日のマスコットオフ会の様子です pic.twitter.com/b4hM8QdKct
— そすうさ(素数うさぎ) (@wk1080id) December 9, 2018
closing partyも終わり、解散の時間になったので解散しました。
かわいー pic.twitter.com/9WLKLGaRTj
— そすうさ(素数うさぎ) (@wk1080id) December 9, 2018
そのあとは10人くらいで横浜に戻ってゲーセン旅行をしました。
🙏🙏🙏🙏🙏🙏 pic.twitter.com/6tUZ5HpNTv
— そすうさ(素数うさぎ) (@wk1080id) December 9, 2018
みんなと別れてホテルに戻るをする。企業ブースで大量の荷物をもらったのでホテルについた頃には体が壊れた。
今夜はこの子と共に…♡ pic.twitter.com/XlzLoWCMlP
— そすうさ(素数うさぎ) (@wk1080id) December 9, 2018
youtubeのコンテスト中継を見て寝た。
day3
3日目は企業見学で、bitFlyer → indeed → LINE でした。
オフ会 at bitFlyer pic.twitter.com/rV8cLI3NT4
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
indeed なう pic.twitter.com/3y0F4Wtt18
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
きゅうりさんの頭にティッピーを乗せるをした。
LINEです pic.twitter.com/Ukom7AJcrd
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
ティッピーです pic.twitter.com/4WnEwIoHYm
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
社内をあんまり撮れないからマスコットの写真を撮りがち。
企業見学が終わって、同じグループのメンバーとサイゼ。
きたぜ pic.twitter.com/mcu6PrXATM
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
キャベツマシマシ pic.twitter.com/6Z7ZLvneWJ
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
各大学の強い人の話や企業コンの話をして盛り上がった。
その後みんなと別れ、秋葉原に行った。てんぷらさんと初エンカ。
おうちに帰るまでがICPCですからね! pic.twitter.com/vCm7vuc5d3
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
そんな感じでICPCが終了しました。
きのうの pic.twitter.com/owL6bS3Lx7
— そすうさ(素数うさぎ) (@wk1080id) December 9, 2018
icpc中にとった写真、9割以上がマスコットかフィギュアなのでやばい(icpcってなんだっけ
— そすうさ(素数うさぎ) (@wk1080id) December 10, 2018
最後に
priMe.caTは今年限りのチームですが、とても楽しくて、たくさんの思い出ができました。
また、横浜大会はいろんな人と会うことができて、新しい知り合いができたりみんなで遊んだりして充実した3日間でした。交流していただいたみなさんありがとうございました。
ぼくは来年もICPC出場資格があるので、チームメンバーは変わってしまいますが、また横浜大会に来たいし、そのためにいっぱい頑張ろうと思いました。
AOJ2321 Butterfly
問題概要
個の用事があり、 個目の用事は時間が 区間拘束され、 個目の区間は 時から 時である。また 個目の用事をすると満足度が 得られる。
時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。
制約
解法
制約から、時間は16個しかないので
dp[i][j] := i個目の用事までするかしないか決めたときに拘束される時間がjの状態のときに得られる最大の満足度
とするbitDPをすると、状態は 個しかないので間に合う。
入力で 個目の用事の区間を受け取るときに、bitに変換しておく( 時から 時まで拘束されるときに ビット目を1にする)と、遷移できるかどうかは&をとればわかるので楽になる。
AOJ1336 The Last Ant
The Last Ant | Aizu Online Judge
問題概要
長さ cmのトンネルに蟻が 匹いる。最初、蟻 はトンネルの左端から cmの場所に向き の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で蟻と蟻が逆向きに歩いて来るとき、その場所が広い場所だと2匹の蟻はすれ違うことができるが、狭い場所だと2匹の蟻はすれ違うことはできず、衝突して今までと逆を向くことになる。
与えられた状態から同時に蟻が動き出すとき、トンネルを最後に出る蟻の番号と、その蟻がトンネルを出るまでにかかる時間を答えよ。
制約
は"L"(左向き)または"R"(右向き)
解法
蟻本の最初に載っているAntsという問題を知っていると、どの蟻についても、トンネルから出る時間がトンネルの長さより大きくなることはないということがわかります。
よって、1秒後から 秒後までのすべての時間について、各蟻がどの場所でどの方向を向いているのかをシミュレーションしてあげると良いです。
計算量は となります。