裏紙

ほぼ競プロ、たまに日記

2018/7 solved(1)

programming solved

7/1

JAG 国内模擬 に参加

6完だった。Gも考察はできてて、サンプルも合ったんだけど、間に合わせられず...国内予選のリハーサルをできて動きを確認した(両面印刷はやめよう)。

ARC 100 に参加

久々に参加した。もっと時間作って参加したいんだけど、どうしても土日の9時はなかなか難しい...。Eが解けてから、CDに時間かかりすぎ。

7/2

7/3

7/4

左上から順に、そのマスに文字を置くか置かないかをきめていくdpをする。そのときに持つべき状態は、(今いるマス, 手前1行分の状態(置いたか置いてないか))があれば十分である。置いたか置いてないかさえわかれば、並べる順番が決まっているのでどこにどの文字が来ているかがわかり、今置こうとしている文字も何行目の何文字目なのかが分かるから、置いたときに得られる点数が計算できる。行が切り替わる瞬間に、文字をちゃんと使い切っていないと遷移してはいけないことに注意(submission)。

7/5

左右と上下を独立にしていいとこまでは分かるけど、そこから条件を満たしつつ動く組み合わせを計算するのが難しい。折り返して考えるというのは賢いと思った(submission)。

z軸方向に対してスキャンしていくときに、連結成分の個数が変わる可能性のあるイベントは、ある球が現れる/消える、球と球がくっつく/離れるのイベントのみである。このイベントの種類はO(n^2)であり、これを順番に処理しながらその都度連結成分の個数を数える。ここは単純なBFSで実装したので、O(n^2)である。よって、全体としてはO(n^4)になっている。また、球が現れ始める瞬間に既に他の球と交わるような場合もある(例えば、内包している時)ので、イベントを1つずつ処理するのはなく、かなり近い座標で起こっているイベントは一度に処理する必要がある(submission)。

削除ができるってことは相手の操作を打ち消せるな、と思うと3ターン目以降って無駄なのでは？と思うと、深さ2までの全操作を試せば良いことになる。構文解析パートは、エラーにも対処しないといけないので結構めんどいけどがんばる。あと、0が有効にならないことを考慮し忘れていてバグらせまくった(こういうのはなくそう)(submission)。

7/6

imulan.hatenablog.jp

7/7

構築ゲー。とりあえず、0101か1010を使わなきゃいけない数が多い方から先頭に、x+1個だけ並べておき、残ったものを切り替わりの数が変わらないように同じ数の隣に置いていく(submission)。

区間を全探索。累積和で高速化しておく(submission)。

倍数の関係になっているので、コインは額が大きい方から貪欲に使っていって構わない。コインはO(logA)種類しかないので、全体はO(QlogA)で処理できる(submission)。

7/8

基本的な方針としては、まず直径dになる分を作ってしまう → 端以外の頂点から次数と深さを守りつつ頂点を生やしていく ということだが、木を生やしていくので(親方向の頂点番号, つなげていい次数, 残されている深さ)をqueueに突っ込みながら新しい頂点を生やしていくと実装が楽。ただ、いろいろなコーナーに注意(d=1だとk=1でもいいけど、d>=2だとk>=2じゃないといけないとか、そもそも直径dを作るための頂点数nが少なすぎるとか)(submission)。

とりあえず、どの区間を略語にするかを全探索することにする(O(n^2)通り)。そして、dp[n][3] = 単語i以降に注目、省略をj回使用したときの長さのminを計算することにすると、遷移は2通りなので全体はO(n^3)になる。遷移の省略する方を考えるときに、O(n)かかってしまわないようにdpをする前にiをスタート地点にする今省略として注目する長さのハッシュをmapなりでとっておくと良い(submission)。

Codeforces Round #490 (Div. 3) Virtual

国内予選終わって若干燃え尽き気味だったけどとりあえず簡単目な問題でも継続しようと思ってやった。発想自体はそこまで難しいものがあるわけじゃないけど、実装はそんなに簡単なわけじゃないしいい練習になった。

7/9

7/10

dfsして全パターンを試して、条件を満たしているかをチェック(submission)。

小さい方から貪欲にM個取っていくが、a[i]とa[i+1]の間を高速に処理するようにする必要がある(submission)。

Codeforces Round #495 (Div. 2) Virtual

Dで時間を溶かした(思い思いの枝刈りをしたら通った...)。Eも思いついてたけど、重心をみつけて、そこから使う頂点を見つけて、それがパスになってるかをチェックして...を実装してたら間に合わなかった。

最大値の最小化を見た瞬間に二分探索を考えた。まず、k=1のときを考えると、このときに選ぶべき点は重心だなあと思ったので、重心からパスを伸ばしていくことを考えることにした。重心(最も遠い点までの距離が最小になる頂点)は、全方位木dpで求めることができる。この位置をスタートにして、二分探索をすると、必ず含めなければ行けない頂点が決まるので、あとはそれがパスになっているかをチェックすれば良い(submission)。

7/11

連続する1の区間で、一番長いやつを見つける。

幹線道路のペアを全探索する。

7/12

下限を全探索する。このときの下限の候補はO(n^2)通りを考えれば良い。固定した下限に対して、各区間がこれよりも大きくなるように選んだときに、最大値が最小になるような切り方をdpでO(n^2)で求めることができる。あとは、答えを逐次更新していけば良い(submission)。

一本道になるような進み方以外が最適になることはなさそうなので、一本道を作っていくことを考えると、今いる場所とそこまでの最短距離をペアにして、その一本道を作るために木をどかしきる最小コストをBFSで求められる(submission)。

7/13

Codeforces Round #496 (Div. 3) Virtual

Div.3なのに全完できなかった...

中央値がX以上になる区間がいくつあるかを求める関数をf(X)とすると、答えはf(X)-f(X+1)で求められる。この"""以上"""がミソで、このように考えることで二値化して考えることができ、E1と同じような考え方を適用できる(submission)。

7/14

7/15

求めたい答えがx以下であるかどうかをチェックする二分探索をすることにすると、数列の値をx以下かどうかで二値化でき、BITなどを使ってその区間にx以下の個数がK個以上あるかどうかがチェックできればいいことになり、高速に数えることができる(submission)。

2017 Ho Chi Minh City Regional Contest Virtual

7/16

答えを二分探索することにすると、決め打ちした値に対して、dp[i] = i番目のワードを区間の左端にすることができるかというdpを、尺取りっぽく更新していくことができるようになる。左端は、限界のライン(ワードと必要最低限のスペースで一行に収まるか)、右端は必要最低限ライン(ワードと目一杯のスペースで一行を超える事ができるか)、という2つの値を持ちながら尺取りして、dpを更新していけば良い(submission)。