裏紙

ほぼ競プロ、たまに日記

2016/2 Solved (2)

2/16

1年を1/1を基準とした日数の1次元配列に落としこむと、休日の設定が楽。振替休日の設定もwhileで1つずつ後ろをみていくだけで十分に間に合う(submission)。

辞書型で変換表を作り、順番に変換していく。変換表にない文字はただ消えて、変換後の文字が1文字でもあれば答えリストに追加(submission)。

format関数を使って少数の表示が指数表記になるのを回避する。

permutationを使って全方向を調べあげる。Pythonだとitertoolsモジュールの中にpermutationsがあり、それをforループで1つずつ取り出して判定することでその最大値を答えと出来る。

各荷物を長さ順でソートして、それぞれの辺において一番長いものを選んでいけば最小でかつ全ての荷物が入るダンボールを作れる。

シミュレーションする。その時点での既出単語リストを作っておいてin演算子で判定すると単語かぶりが簡単に見れる。

黒いチョコの部分を正負反転させることによって、長方形内の整数の和が0になる部分を探す問題に変わる。 そして、横に対して累積和を取っておく。

まず、縦を区切る区間を決める。左端と右端の決め方で、O(w^2)。次にその区間に対して、先ほどの横に対する累積和を使って行ごとの和(その行の右端までの累積和-その行の左端までの累積和=その行の区間における和)を求める。そして、それを縦に対して累積和を取って、0になるところを上端と下端をきめながら探す。見つけ次第更新していく。これがO(h^2)なので、全体としてはO((hw)^2)となる。hw \le 10000なので、これが間に合うのか疑わしかったが、普通に間に合った。計算量の見積りがよくわかんない...

2/17

imulan.hatenablog.jp

2/18

ちょうど半分が限界の数というのに気づけば、それより大きいか小さいかの判定で終わる。

どの海の部分を陸地に変えるかの全探索。つながっている判定はある陸一点からBFSで全ての陸に辿り着けるかで判定した。

Pythonだとこういう集合の問題は非常に書く量がすくなくて楽。

2/19

端の時の判定に注意して、ループを回しながら隣と異なった値かどうかを判定。

左右に動く操作の合計回数よりロボットのx座標の差が小さければ、同じx座標に到達しうる(左側にいるロボットのみが右の動作をし、右側にいるロボットのみが左の動作をするとき)。これはy座標に関しても同じことが言えるので、x座標とy座標のそれぞれで条件を満たす場合に同じ座標に到達しうる。

2/20

Educational CF #8に参加

ABCの3完。DとEは復習しよう...

単純な2重ループによる全探索。

k番目のクマを1体ずつ順番に座る場所を貪欲に選んでいく。ただ、幅dが大きいので席を1つ1つ調べていくのでは間に合わない。既に座っているクマの位置をソートして、そのi番目とi+1番目の間に座れるスペースがあり、かつそこがatLeast[k]以上ならばそこを選ぶことが出来る。atLeast[k]が座れなくても、それより右側にある最も近いスペースを選ぶことが出来ることに気をつけておかねばいけない(これでミスった)。

imulan.hatenablog.jp

2/21

CF #343 Div2に参加

ABの2完。Cは本当にしょうもないミスだった...方針合ってたしかなり速くかけただけに悲しい。

imulan.hatenablog.jp

与えられる文字列sをひとまとめにして考えると、n-m+1個の要素を並べる問題になる。そこで、dp[現在注目している位置][開き括弧-閉じ括弧の数][sを使ったか否か]=組合せ%modを使ってメモ化再帰した。どのような接頭辞配列に対しても開き括弧の数>=閉じ括弧の数でないと行けないので、文字列sを使うことが出来るのはsの先頭から最後まで一気に並べた時に開き括弧の方が多くないといけないのはもちろんだが、その途中に置いてもこのような状況が起きてはいけないので、始めにsについて接頭辞配列の開き括弧の数-閉じ括弧の数の最小値を知っておく必要がある。これはsを一度走査しながらその都度値を更新していくことで実現出来る。また、文字列を全て並べ終わる1つ手前で、まだsが使われていなかったらそこではsを使う必要があるので強制的にそこに入るようにする。(submission)

Editorialも読んだけど、 分かりにくいので上位の人のを参考にした。けど、ソートする前の配列の位置を記憶しておくのにmapを使ってたら、それがあとから上書きされてバグるみたいな自体が発生してたらしい。そしたらvectorの重複要素をuniqueとeraseを使って取り除いてからそれに対してSegtreeを使っていくって感じでやってた。(submission)ついでにこれを機にSegtreeを作った。

2/22

現在の雪球の位置と雪球の大きさを保存してスタート地点からの最短距離を保存しながらBFSした。いまいち雪球の上限は考察しきれなかったけど、BFSが間に合う範囲でこれぐらい上まで持っておけば大丈夫だろう、みたいな感じで投げてしまったけど通って良かった。BFSの中身は一時変数使ってもうちょっと見通しよくした方がよかったかな...(submission)

各ステップで成功/失敗の樹形図を書いて考察すると、i回目(i>=3)だけ失敗してそれ以外は成功し続けるときの本来の値との差がa[i-2]であることに気づく。更にこれらは線形結合的で、大きい方から貪欲に選んで本来の値の差をつめていくようにすればよい。うまくいかないのは差が詰まりきらないときなので、そのようなときは-1を出力する。(submission)

埋め込みか...なるほどとおもってしまった問題だった

やっぱ対称式作って解と係数の関係に落とし込めば楽なのか...と解説を見て思ったが、これを考えてもその式が作れなかったので気合で式変形して1つずつ変数を消して最終的にz_2だけの2次方程式に落とし込み、その方程式の判別式を使って解いた。最終的に (c_1 c_3- {c_2}^2){z_2}^2 + (c_2 c_3 - c_1 c_4)z_2 + c_2 c_4 - {c_3}^2 =0と求まり、判別式の正負を使ってz_2の解の存在範囲から判定する。また、対称性より片方にz_2を選ぶともう片方はz_1の値となるので問題はない。 c_1 c_3 - {c_2}^2 \neq 0が全てのヒントだったか...

2/23

SRM 682 Div1に参加

0完してしまった。Easyは普通に訪れた頂点保存しながらBFSすれば多分間に合うだろうと思ってやった(submission)んだけどなんかqueueを使ってた実装で本番出してたらuncaught exceptionとか1ケースだけ返ってきててたぶんqueueが原因なのかなーと思って同じことを再帰に書きなおしたら通った...悲しい...SRMは1問が重いからつらい。

もっと速い解があって、辺の数が2000以下なので、A-B-C-D-Eを探すにあたって、辺を2つ選ぶ(A-BとC-D)→BとCがつながっているかsetを使って判定→Dからつながっている辺のうちA,B,Cでもない頂点があればそれをEとする とすれば辺の数の二乗の計算量で終わる。

Editorialを見れば図が分かりやすい...朝のSRMで見たばっかりだったから、この辺に注目して考えるのはもしかして結構セオリーなのかなと思った。

2/24

True ancestorが誰になるかとかそういうことを考えなければ、numはそのまま頂点が持っている辺の数になることが分かる。そして、木を構成するということは、頂点nに対して辺がn-1本あって閉路が存在しないということになる。そして、求めるべきは木の直径の最大値であるから、その直径を構成するのは葉、つまりnum[i]=1なる頂点であることは明らか。そして、直径を最大化するには2つのnum[]=1なる点の間にnum[]>1なる点を直列に並べて、余った部分を他のnum[]=1の部分と繋いでおく形がベストなのである。まず辺の数の合計的に木を構成することができうるかを判定し、可能な場合は(全体の頂点数) - (num>1なる頂点数) +1が解となる。

imulan.hatenablog.jp

2/25

imulan.hatenablog.jp

2/26

1月1日から数えて何日目かを数え上げる関数を用意して引き算。

3つ以上の組合せは2つの組合せのどれかを接頭辞として持つので最小になり得ない。よって2つの組合せを全探索してあげればよい。

2/27

スタートから中間地点、中間地点からゴールまでをBFSして最短経路を出せば良い。

パスカルの三角形的なDP。

グラフの頂点をそれぞれ4倍と7倍にして、到達時間の最小値のそれぞれの剰余を持ちながらダイクストラする。また、一度ゴールに入ったら出ることができないのでその遷移をしないようにしておく。(submission)

MUJIN PCに参加

ABの2完。Cはもう思いつかなかったし、DはSegtree使うんだろうなーと思ったけど、2つ用意する発想はなかった...

2/28

上の桁から順に見ていって、既にその数より小さいことが確定しているかどうかを判定しながらDPを進めていく。(submission)

LとRに、それぞれどの2文字を割り当てるのかを全探索する。

TPC追いコンに参加

AとD部分点。Bは蟻本にも載っていたのでその流れで書いてみたけどTLE。行をまとめてXORで処理することでオーダーを落とせることに全くきづけなかった...

2/29

imulan.hatenablog.jp

CF 8VC Venture Cup 2016 - Final Round (Div. 2 Edition)に参加

ABの2完。