裏紙

ほぼ競プロ、たまに日記

2016/6 Solved(1)

6/1

A+Bが特殊な形で実装されているので穴を探す問題.3番に関しては適当にいじってたら反例を見つけてしまったのでよくわかってない...

6/2

シンプルな桁DP.dp[now][sum][small](今上からnow文字目に注目してて,そこまでの和のdでの剰余はsum,nより小さいことが確定しているかどうか)=組み合わせ数を持って,下からテーブルを更新していく.配る感じで実装した(submission).

1から始めて,その数を割りきらないものを小さい方から2つ選び,その値とのlcmを取っていくということをまず最初にやっておく.そして,その列挙が終わった後である数がある数の約数になっている時に引いておくことで個数を掛けた時の被って数え上げてしまうのを避けている(submission),正直これよりも全然綺麗な解法を他の方が書いていてくれて,そっちを見たほうが早いと思った...

6/3

imulan.hatenablog.jp

imulan.hatenablog.jp

ARC 055に参加

1完.BのDPは思いつけなかったけど,シカの視点になれば自然な遷移という感じがする.「その時点での」最大がくる確率というののイメージが難しかった...

6/4

imulan.hatenablog.jp

imulan.hatenablog.jp

6/5

imulan.hatenablog.jp

imulan.hatenablog.jp

根をxとする木を構成し,各頂点に訪れるべきかどうかは,その各頂点の子どもに1つでも宝石があるノードがあればおとずれるべきであると分かるので,論理和を取りながらまずはDFSでこれを更新していく.それが終わったあとで,BFSにより訪れるべき頂点を探しながら見つけ次第+2(行きと帰り)していけばよい(submission).

最初はUnionFindとか使おうかと思ったけど,BFSで十分間に合った.連結成分の個数-1が全ての頂点を結ぶために必要な辺の本数であるから,連結成分の個数をBFSしながら数えれば良い.

6/6

グラフとして考える.一文字違いの頂点同士を辺で結び,最短距離を親を保存しながら求めて,経路復元をすればよい(submission).

6/7

組み合わせの総数としては,まずN人の中からK人,自分の招待状じゃないものが渡される人を選ぶ,そして,このK人に対して,どの人に対しても自分のものではない招待状が渡される組み合わせの個数を求めるということをすればよい.このような招待状の渡し方は完全順列(Wikipedia)という考え方に当てはまっていて,モンモール数と呼ばれており,漸化式によって線形時間で計算可能である. \begin{eqnarray} {}_n C _k \end{eqnarray} をどのように計算するのが楽かということに関しては,Kの上限が大きくないので, \displaystyle \frac{N!}{K!(N-K)!} = \frac{N(N-1)(N-2) ... (N-K+1)}{K!}と約分してしまえば掛け算の回数を減らせる.今回は素数で割った余りを求めるので,逆元を取るのも簡単である(submission).

まず,startとgoalから訪れられる場所の範囲をBFSで求めておく.そして,startから訪れられる場所に隣接している1個壁を壊したら訪れられる場所とgoalから訪れられる場所に隣接している1個壁を壊したら訪れられる場所をそれぞれBFSでまた求めると,2回壁を壊してstartからgoalに行けるかの判定はこの2つの範囲が隣接しているかどうかによって判定することが可能になる(submission).

imulan.hatenablog.jp

6/8

文字のスタート位置と,幅に関して全探索をすればよい.

6/9

まず,正常な動作をしたものに対してはその3つのパーツが正常であることが確定する.そして,その状態の中で不合格になったものは少なくとも1つは故障部品を含むが,それを確定させることが出来るのはそれ以外の2つが正常であるとわかっている時に限られるので,そのような条件を考慮しながら更新していく.

色を変える位置と,その色を全探索していく.実際に消えていく様子のシミュレーションは,配列に詰めて落下させて...などとやってると時間がかかってしまうので,しゃくとり法的な感じでその地点から上と下にそれぞれ何個消えるかをindexの差として計算しながら4個以上なら次のステップへ進んでおなじことをやり,なければそこでストップし,最小値を更新していく.計算量はO(N^2)

バックトラック.

素直なDP.dp[i][j]=街iにj日目にいる時に溜まっている疲労度の最小値として,その日に出来る行動は次の街に行く・待機のどちらかなのでdp[i][j]からはdp[i+1][j+1]とdp[i][j+1]へ遷移させる.

2点を決めると,他の2点としてあり得る位置が2通りしかなくなるので,その両方に点があれば面積の最大値を更新していく.点の存在判定をsetで行ったので計算量はO(N^2 logN)

座標圧縮の用な感じで,(色,個数)のペアが並んでいるという感じで考えると,かならずどの状態でも色に関しては交互になっている.なので,奇数番目の場合は色に応じて新たにペアを作るか末尾のペアの個数を1増やす,偶数番目の場合は末尾のペアの個数を1増やすか,末尾の前後を結合させて個数を管理するかという方法を取ることで,O(N)で実現できる.なかなか悩んで,面白い問題だった.

6/10

それぞれの文字の終端を決めた時の共通部分列の長さを保存しながらDPする.文字列の長さをNとすれば計算量はO(N^2)で実現できる.

長方形内の個数を数えるために使われるDP.左上からの累積和を予め計算しておくと,クエリに対して足し引きをすることでO(1)で答えることが出来る.

Bの山のスタート位置を決めると,そこから貪欲にAとBに共通するものを選んでいくことで局所的な最適解が得られ,それを最大値を持ちながら更新していけば良い.

移動日程から,各鉄道を利用する回数が分かる.また,その計算のためには累積和を使うことによって素早く計算することが出来る.後は,各鉄道に関して切符で乗り続けるかICカードを買ってICカードで乗り続けるかの安い方法を選んだその和を取れば良い.

dp[i][j][d][t]=現在位置(i,j)で,左から来たか下から来たか(d=0/1),この位置で曲がることは出来るか(t=0/1) という状態における経路数を持ちながらDPしていく.普通の経路問題に加えてちょっと制約が入ったことで,DPの遷移の複雑さが跳ね上がって良い問題だと思った.

6/11

建物がないところに関して,そこが外部なのかどうかをBFSによって調べる.それが終わった後で,建物があるところに関して,そこに隣接するところが外部になっていればそこにイルミネーションが必要なので+1をカウントして,その合計を答えとする.

dpの状態をどう持たせるか迷った.最初は日数と参加状況に加え鍵を持つ人まで状態に持たせてしまい,表面上は同じ人の集まりを重複してカウントしてしまうということが起きていた.それは問題の意図とは異なるということに気づき,思い切ってその状態をなくした.前日の参加状況がわかっていれば,その日の参加状況との差分で1人でも同じ人がいればそのひとに鍵をもたせたということにしてしまえばいいということなので,この状態は余計だったということがわかって,すっきり解ける.

何回目の波でその位置が崩れるかを持ちながらDPし,その中の最大値を選ぶ.

ABC 039に参加

ABCDの4完.今回のDはできてる人も多くてやっぱり簡単だったのかなという印象.

6/12

最初に伸び始めるつららの次に伸び始めるのは,隣のつららになるので,それをBFSしながら更新していく.そのつららが折れるのにかかる時間は(左隣が折れる時間+自分が折れる時間),(右隣が折れる時間+自分が折れる時間),自分が折れる時間のmaxを取りながら更新していけば良い.

ICPC模擬国内予選Bに参加

チームで参加.今回は本番みたいに3人でPC1台で練習してみようみたいな感じでやった.結局ABDEの4完.Cは自分がAをやったあとに読んでいたけど,なかなか効率の良さそうな方法が思いつけなかったので,とりあえず後回しにして自分はDとEについて考えていた.結局それが終わった後もCが残り,もう最期の最後の方で自分がアイデアを投げたらいけそうってことに気づく.気づくのが遅すぎた.でもそのあと実装してみたらバグらせまくって2時間ぐらいやってたのもひどかった.まあ結果的にD,Eを先に目を通せてよかったねという感じだったけど...幾何は練習が足りないという感じしかしない.

6/13

dp[a][b]=ジャンルaに注目し,今売った本の合計がbの時の金額の最大値を持ちながらDP.

6/14

夜店を回る順番は小さい順と決まっているので,dp[a][b]=いま時刻bで,店aまでについていくかどうかを決めた時の最大の満足度を更新していく.

はじめに,デフォで何個の紋章があるのかと,その位置を確認しておく.そして,変更する位置と変更文字を全探索する.変更箇所によって影響がでるのはそのまわりだけなので,周りだけをどう変化するかをチェックして,最大値を更新していけば良い.

まずは饅頭i個を入れるために必要な箱の購入額の最小値を0-1ナップサック問題とほぼ同様のdpによって計算しておく.それを計算しておけば,饅頭は値段が高い方から選ぶほうが利益が大きいので,降順にソートしておき,累積和をとっておいて饅頭i個売る時の利益を全探索して最大値を求めれば良い.色々からみ合っていて好きな問題だった.

左端と右端の値を持ちながらDP.区間DPみたいな感じ.

imulan.hatenablog.jp

6/15