裏紙

ほぼ競プロ、たまに日記

2016/10 solved(1)

10/1

方針自体は(現在地,訪れた超点数)=かかる時間の最小値というシンプルなDPだったのだけど、queueとBFSで実装してしまい本番はMLEで死んだ。dfsに書き直して様々な修正をしてようやくできた(submission)。

できるだけ絶対値の小さいものを大きくしていく方向性が、積を大きくすることができる。まず、それよりも前に積を負にしておきたいので、負の値の個数を数えて偶数個だったら負の数を奇数にしておく。そのときに、手っ取り早いのは正の数の最小値を負にするか、負の数の最大値を正にするかのどちらかになる。絶対値が小さい方が早くできるのでその処理をした後に、priority_queueをつかって絶対値が最小のものに対して処理をし続ければ最大化出来る(submission)。

10/2

最初、UnionFindとsetをつかってmergeしていくことを考えていたが、色が2種類しかないので全ての色が同じ色になるまでにかかる回数が実は結構少なくなり、全て同じ色になるまでを普通に処理し、その後は色だけ保存しておくのが速い(submission)。

時間がかかると思ってたUnionFindとsetを使う方針もデータ構造をマージする一般的なテクなどの利用により上のsubmissionよりも速く動く解にすることが出来た(submission)。

10/3

PythonのDecimalで殴った。

はじめから?のところまでをシミュレーションし、後ろから?のところまでを戻すようにシミュレーションして、その2つの配列を見比べて値が違うところを答えにすれば良い。

mapを使って全ての部分文字列を数え上げてからm個の文字列が何個あるかを数え上げた。部分文字列の上限が短かったからできた解法。

蟻本のDPの練習問題のところにあったからやってみたけど、別にDP使わなくてもできてしまうし、貪欲が通ってしまうというなんとも微妙な問題だった...

stackを使うと簡単。

要素の値が小さいところから順番に見ていき、setに既に訪れた値のindexを入れて管理する。するとそのときに今注目している要素が最小値となる区間が何個になるかを決定でき、それを足し上げることで答えを求めることが出来る(submission)。setやmapに対してlower_boundを行う時は、algorithmのものではなくオブジェクトが持っている方を呼ばないと効率が悪い。

構成できる条件を考えていく。絵を描いてみるとわかるが、最大値を見たときに、まずそれが対にならないといけないので最大値を持つ値は複数個必要というのは検討がつく。そして、その最大値に対応して最小値も決まってくる(最大値+1個のノードを一直線に繋いでみると察しがつく)。そして、その最小値は最大値の偶奇によって1個か2個かが決まり、最小値+1~最大値の値は全て2個以上あればよいということがわかる(submission)。制約が小さいのは惑わしかな...?

10/4

10/5

imulan.hatenablog.jp

10/6

考えてみたらLISを取るだけだった...

高さをDPの要素に持てたらできそうだな、というところからこれa[i]に出てこない値は使わなくていいじゃんって気づいて、O(N^3)のDPができて、更新過程をよく見たらdp[i][j]の更新が一時変数を用意してすぐにできることがわかったのでO(N^2)にできた。

高さ制限でソートしてから、ナップサック的に解く。自分は高さiへの到達可能性をbool値で実現して答えを求めていたが、それでは商品個数に依存してしまう(O(K * A * C ) になる)(submission)が、高さiに到達するために商品を何個残せるかを保存しておくようなDPにすれば、O(K*A)で実現できる。参考になりました。

dp[i][ts]=i番目までcowを展示するか否か決めたときのsmartnessの合計がtsのときのtfの最大値として更新していく。そのまま配列を用意するとMLEするっぽいので、dp[2][ts]にして逐次更新していく。

10/7

桁DPをする。MとDは別々に考えてよく、文字列をSとした時のdp[idx][sum][small]=idx文字目まで見たときの和がsumで、この時点でSより小さいことが決まっているか(small)という状況での組み合わせの数というDPをMとDに関してする。そして、求めたいものはxもyも各桁の和がiとなるようなx月y日の個数なので、単純に掛け算してしまえば求まる(submission)。

imulan.hatenablog.jp

  • SRM 651 Div1 Easy - RobotOnMoon (この回はunratedだったらしく、問題が公開されていなかった)

問題概要としては、2次元グリッド上にいくつかのマスに障害物があってそのマスには移動できない。あるマスにロボットがいて、上下左右に移動命令を出せる。ただし、命令が正しく送れない可能性もありうるので、その時は動かない。そして、フィールドの外に出るとロボットが壊れてしまうので、どのように命令を受理してもフィールド外に出ないような命令列の中で最長のものを求めよ。無限に長い命令列をつくることができる時は、-1を答えよという問題。

これは、1つの方向に移動して障害物にぶつかることができるならその方向に移動し続ければいいので-1を出す。どの方向にも無いときには、障害物に引っ掛けられない可能性が出てくるので命令列の長さは有限になる。そして最大値は(左右の幅-1)+(上下の幅-1)になる。

10/8

(なにもしてない)

10/9

リアクティブ問題。自分がロウソクの長さを聞くクエリを投げてもとの長さをあてたい。長いか短いかを教えてくれるので、二分探索でできそうというのは想像はつくが、あまり短いとすぐ0になってしまいそれ以降ずっと0を返すのでもとの長さがわからなくなる。そこで、短いところは愚直に処理し、ある程度の長さ以上(90以上とした)の範囲に対して二分探索をするということをした。その際にも区間を更新するときにロウソクが少しづつ短くなることに注意しながら更新する必要がある(submission)。

10/10

code festival 2016 qual Bに参加

ABの2完。Cは思いつけず、Dはあと一歩詰められなかった。Cもあるけど、予選Aで通れていて本当によかった...

前から順番に客を見ていって買えるだけ買わせるということをするために、i番目の客を見ているときに1~i-1番目の客の中での所持金の最大値が分かるようにしたいなと思ったのでsegtreeを使って管理した(実は要らないが)。そして、できるだけ多くのものを買わせるときにその最大値+1円で商品を買わせていけば良いのだけど、最後の1個だけはあとのことを考えるとできるだけその客の所持金は減らしておいたほうが良いので、1になるように値段を付けて買わせるのが最適な方法になる(submission)。

10/11

区間の左上の座標と右上の座標を保持しながら得られる最大の個数を求めるDPをする。ただ、そのままだと座標が大きすぎて間に合わないので、マシンが少ないことを利用して座標圧縮を行う。マシンのある列と、それ以外を区別して、個数を保存して圧縮する。それが自分の提出のmake_field()という部分で行われている。これは、x座標、y座標ともに区間の開始位置(マシンのある行・列とその1つ先)を記録してソートしたものを保管してグリッド状にしてそのマスには何個の金塊があるかという情報を入れて圧縮する。また、setを使ってマシンのある位置も圧縮した後の座標に移していく。このように圧縮ができてしまえば、DPパートは区間をながめてそのなかにあるマシンを稼働させて左上、左下、右上、右下の4箇所に分割した再帰を呼ぶだけでできる(submission)。

10/12

10/13

最小全域木を構築するだけ。 The input includes several cases. 問題はよく読もうな。

最小全域木

クラスカル法の要領でコストが小さい辺からマージしていき、全ての頂点がつながるまでやってその瞬間のコストを答えればよい。

10/14

(なにもしてない)

10/15

10/16

ICPC Asia Regional Online Open Contestに参加

チームで参加した。自分はそもそも寝坊し、申し訳なかったが、DとGを実装した。来年こそ現地に行きたいという気持ち。