Atcoder Regular Contest 056
Tasks - AtCoder Regular Contest 056 | AtCoder
レギュラーコンテストの方にも挑戦してみたいなと思っていたところ、ちょうど開催されていたのでやってみた。
ABCでも苦戦中なのでだいぶ厳しいのかなと思っていたが、A,B問題はABCのC,D問題のような感じで、点も取ることができた。
リアルタイムで挑戦。
1時間しか時間が取れそうになかったので、とりあえずARCに参加してみようという感じで挑戦。
A 意外と簡単でABCのB問題で出そうな難易度。
B 部分点ゲット。 O(NM)の解答はすんなり実装できた。
正しい解法はダイクストラ法でO(NLogM). ダイクストラ = 最短経路というイメージがあったので思いつかなかった。
目的地をxとした時に、xまでの経路でx以下の数値の場所があったらだめ。 大事なのが、ある経路のminの数値で、この数値が高い経路がより残る、遠くまで行ける経路。
S地点から順に、各地点の上記の数値を確定していく。
後からチャレンジ
C
問題
少し変わった組み合わせの問題。 うまい方法は思いつかなかったので、愚直に組み合わせを計算して部分点取得。
組み合わせの数は、N-1のすべての組み合わせの部門にN番目の人を入れたもの ＋ N番目の人一人の部門とそれ以外の組み合わせということで、大体2N. この辺りの組み合わせの実装とオーダー数の理解が得意ではないので自信なし。
C 問題 解説を見て
N個のグループ分けの組み合わせ数はベル数というらしい。
全組み合わせの列挙の仕方は、vectorで実際にグループ化していくより、グループ番号を振る形の方が簡単。
dfsでグループ数を伝搬して、一つ前のグループそれぞれに入る処理と、新しくグループを作ってそこに入る処理をする。
bit dp
各ビットを社員と見立てることで、ビット列で全部分グループを表現できる。
また、部分ビット列内の全パターンを網羅するのは、 subgroup = (subgroup - 1) & group で可能。
1 から2 ^ n までのインクリメントで各部分グループ内のベストスコアを入れていく。
部分グループ内のベストスコアの導き方は、 部分グループ内で一つグループを作る。
このベストスコアは K + 作ったグループ以外のグループのベストスコア - グループ間の信頼値の和
となる。
上記で作るグループを部分グループ内で作れる全部分グループを施行し、そのMAXをとることで、部分グループのベストスコアを導き出せる。
グループ間の信頼値の総和
愚直に考えると、Aに所属している社員それぞれに対して、Bに所属する全社員との信頼値を参照するので、O(N2).
先に全部分グループ内の信頼値の総和を計算しておくことで、 全体 - A内の総和 - B内の総和 で計算できる。O(1).
感想
最終的な実装自体はシンプルだけど、そこに行き着くまでの発想がBeginnerで求められるものより大分厳しい。。
ビット列で部分集合を表現できるのは解りやすいけど、K + ~~~~ の式を思ういつかないと部分集合を使おうとも思わないし、初見でこの式がパッと思うつける感じがしない。
数をこなしていけばパターン化できるもの？
D
入力値と、サンプルケースは理解できた。
よく解らなかったので解説動画を見た。
データ構造自体はセグメントツリーを使うということで知っている知識だったか、そこに行き着くまでの過程が複雑で未だにスッキリとは理解できていない。
t のタイミングで飲むと決めた時のスコアの最大値をDPでtをインクリメントさせていき、DP[0] ~ DP[MAX] の間の最大値が答えになる。 各DPの求め方は、DP[0] ~ DP[t - 1] それぞれに対して、tとの間で取得できるスコアを足したものの最大値を求める。 この部分をうまくセグメントツリーを使う形で実装するとオーダー数を抑えられる。
まずdpを上記のような形で行えば答えが導き出せるという発想することのハードルが高そう。。慣れの問題か？問題をしっかりと理解することでロジカルに導き出せるものか？
dpの条件を自分でクリアに導き出せれば、セグメントツリーに落とし込むことは、難しいができないこともなさそう。
