2019-11-22

チーム練(2018ジャカルタ)

チーム練

でぃぶが一瞬でIを通す。

ふぇりんがからAの概要を聞いた僕が一瞬って言う。WA

でぃぶが一瞬でLを通す。

このへんで、僕が1問読む間にチームメイトは2～3問読んでいることに気が付く。

ふぇりんが昨日K解いたって言ってたので任せる。無限時間かかってたけどAC。

僕がJを解けたと主張して、ふぇりんがDを解けたと主張したので、軽そうなJから実装に入る。サンプルが合わない。交代してDを書いてもらう。WA。WA。Aを考えていたでぃぶからコーナーケースが届いたので実装。WA。度重なるコーナーケースの列挙ののち、DがWAっている。デバッグの結果JもWA。地獄のデバッグ3並列。

落ち着いた当たりで突然DもAもJも通りだす。20分で3問通す人になってしまった。

でぃぶと僕でGの解法を出し、実装するけど一生WA～って言ってる間にふぇりんとでぃぶがHの解法を生やす。交代してもらってWA。2並列デバッグが始まる。

ここも突然通りだして、7分で2問解く人になっていた。

何故かここまでFが読まれていなかったので読んでもらうと、自明であることが分かったので実装。WA。今回は比較的すぐ通る。

Eは見えなくて、Bは解けるとしたらふぇりんなんだけど、やりたくね～って言ってたので、残りは一生Cのパズルをやっていた。

9完1434ペナ当時だと6位。

A　0と1の数が違うときは少ない方に揃えて、そうでないときは末尾の文字を無視する。

F　セグ木

G　最短経路っぽい気持ちになる。

J　LIS

全部で9回もペナルティ生やした。実装が下手すぎます。実装うまくなりて～～～～～

2019-11-19

ICPC 2019 Asia Yokohama Regional 不参加記

チーム練

国内予選(95位)落ちたので参加していませんでした。

学内1位だとしても落ちてるの、弱すぎない？(俺は橙コーダーやぞ)(当時は黄コーダー(俺は黄コーダーやぞ))

ふぇりんとオープンに出ます。

-------------コンテスト開始-----------------

・0:04 ふぇりんがAを書き始める。

・0:07 おるふぇがBを実装キューに投げる。結論から言うとここはPCを奪うべきだった。

・0:22 ふぇりんがAを通す。1完22ペナ

・0:30 おるふぇがBを通す。2完53ペナ

・0:45 Eの嘘解法で盛り上がる。

・0:49 GとHが通されているのに気づく。

・0:51 ふぇりんがHの実装を始める。

・0:58 ふぇりんのHが落ちる。

・1:06 ふぇりんがHの嘘を発見する。

・1:12 おるふぇがGを実装キューに投げる。

・1:23 おるふぇがGの実装を始める。

・1:55 ふぇりんがHの実装を始め、おるふぇが昼食で離脱する。

・2:08 ふぇりんのHが落ちる。

・2:12 おるふぇが復帰

・2:18 デバッグをし嘘を発見する。

・2:23 ふぇりんがHを通す。3完237ペナ

・2:34 おるふぇのGが落ちる。

・2:36 ふぇりんがEの解法を生やす。

・2:40 おるふぇのGが通る。4完417ペナ

・2:53 ふぇりんのEが通る。5完591ペナ

・3:05 ふぇりんがIの解法を生やすもおるふぇが理解しないので質問タイム(は？)

・3:22 ふぇりんがIの実装に入る。

・4:00ぐらいおるふぇがDの解法を生やす(←これ実装して正しい解法だったのか早く確認してください。)

--------------コンテスト終了------------------

I，1行直したら通ったけど
— フェリン (@ferin_tech15) November 17, 2019

↑これは何ですか

全体的にふぇりんが強かったね。あとはツイッターとか見て楽しそうだなあ～って言ってた。来年はアジアに行きたいなあ！！！！！！

2019-09-20

ACPC参加記(2019)

参加記

ACPC1日目

会津合宿鈍行部員なのでこれで来る。

pic.twitter.com/TTHbIbce8Y
— olphe (@_olphe) August 10, 2019

南栗橋以降は人が少なく、席が広いのでかなり快適なんですが、電子マネーが使えない場合があるので、切符を買っておくとかなり無難であるように思います。それ以外は無限に快適でした。春日部からの比較ではありますが、新幹線ルートと比較して1時間で3000円と快適さを買えます。

集合が12:30のところ、12時過ぎに会津若松駅に着く。

社会性の無さを発揮してこれらをしていた。

pic.twitter.com/DFggTyoR1f
— olphe (@_olphe) September 18, 2019

いまバスに乗りました。
— olphe (@_olphe) September 18, 2019

コンテストは、てんぷらが強くて優勝してしまった。

これはボドゲ

olphe moritaoy
もんくくい
りあん
 つぶあん
yamad pic.twitter.com/5oUBIabJ1S
— olphe (@_olphe) September 18, 2019

ホテルは東横に泊まったんですが、館内着(？)とタオルと歯ブラシと電源と朝食があるのが良くて、壁が異常に薄いのが良くなかった。

ACPC2日目

この日は集合時間に間に合った気がする。偉すぎてびっくりしてしまった。

この日のコンテストはかなりいい感じのチーム戦が出来ていて、実力以上の結果だったと思うんだけど、こたつがめに負けてしまった。オンサイト2位。

問題の懇親会なんですが、僕個人としてはちょっと飲んだ頃から未成年にかなり警戒されていてすまねぇ～って言っていた。(実は結局1問分も飲んでいないんですよね)

beet君が酔って壊れていたのがかなり面白くて、beet君が人間らしいことをしていると面白いですね。

倒れた @beet_aizu の囲み取材 pic.twitter.com/yDJ4tJcQa3
— こたつがめ (@kotatsugame_t) September 19, 2019

下は参加者から参加記での使用許可を得た写真たち。

f:id:olphe:20190920232332j:plain — 倒れてもなお酒を飲むbeet(流石に回収されてた気がする)

f:id:olphe:20190920232111j:plain — https://twitter.com/IKyopro/status/1174647251865460736

f:id:olphe:20190920232210j:plain — つぶあんくんに運搬されるbeet

ACPC3日目

今日は9時集合だったけど、社会性の無さを発揮して集合時間より遅く出発するバスに乗る。

9:10の若松駅のバスに乗ります
— olphe (@_olphe) September 19, 2019

コンテストは割と温まっていたけどbeet君が暫定1位風船を奪いに来たのでキレてしまった。いや優勝ですではないんだよな。僕らが全完したら逆転やが～って言っていたけど全完ならず。個人としてはBだけ通すマンになってしまった。オンサイト2位。

解散後はTAB君わく君と富士の湯に行った。富士グランドホテルに泊まると毎日入浴券がもらえるの良すぎませんか？次参加することがあれば富士グランドホテルに泊まります。

帰りはリバティに乗って帰りました。。安くて広くて人が居なくてそこそこ速いので大好きになってしまった。これも注意点として、切符を買うと安心です。

TAB君がsuicaで入ったのが原因で電車止まったの面白すぎる
— olphe (@_olphe) September 20, 2019

春日部までの新幹線ルートと比較して、1時間で2000円を買えます。

その他

合宿にセットを出したくなってしまった。

2019-08-22

Codeforces Round #581 (Div. 2)D-Kirk and a Binary String

Codeforces

問題概要

長さNの01からなる文字列がs与えられる。次の条件を満たすの文字列tを見つけたい。

長さがN
任意の $l , r (0 \le l \le r \lt N)$ について、 $[s_l:s_r]$ のLISと $[t_l:t_r ]$ のLISの長さが同じ
tに含まれる0の数が上二つの条件を満たす中で最大

メモ1

まず、先頭と末尾以外の文字について、文字を変更できるパターンを考える。

000->010:後ろ2文字を取ってきたときに不適
001->011:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
010->000:後ろ2文字を取ってきたときに不適
011->001:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
100->110:後ろ2文字を取ってきたときに不適
101->111:3文字を取ってきたときに不適
110->100:先頭2文字を取ってきたときに不適
111->101:先頭2文字を取ってきたときに不適

また、一気に複数文字変更することを考えたときに、0.....0、1.....1以外の塊を変更させるのは、01若しくは10の部分を取ってきたときに不適であることがわかるため、複数文字変更のパターンは0.....0->1.....1か1.....1->0.....0だが、それらは1文字変更を何回か繰り返したものとみなせるので1文字変更のみを考える。また、001->011と011->001は逆操作であり、0の数を最大化したいことを考えるとあり得る操作は011->001のみになる。

メモ2

文字列sの先頭に0を、末尾に1を付けて考えてよい。これは、新たな先頭を含んだ文字列は常にLISの長さが1長くなり、新たな末尾を含んだ文字列は常にLISの長さが1長くなるからである。これによって、もとのsのすべての要素が、前の要素も後ろの要素も持つようになり、メモ1の内容を適用できる。

メモ3

s全体で考えたときにi文字目を1->0と変更できない場合は、あるl,rを選んだ時に、

$[s_l:s_{i-1}]$ か $[s_{i+1}:s_r]$ のどちらかは空ではない
$[s_l:s_{i-1}]$ の末尾が0という条件のLISの長さ+1+ $[s_{i+1}:s_r]$ のLISの長さ
$\ne$ $[s_l:s_{i-1}]$ のLISの長さ+1+ $[s_{i+1}:s_r]$ の先頭が1という条件のLISの長さ

となるようなl,rが存在する場合である。

二つ目の条件はよく見ると左右に分割することができることが分かる。両辺が等しくないときは左側、右側のどちらかが等しくないことが必要だからである。

また、これと、1を0に変えることより左側の条件は

$[s_l:s_{i-1}]$ のLISの長さ $\gt$ $[s_l:s_{i-1}]$ の末尾が0という条件のLISの長さ

右側の条件は

$[s_{i+1}:s_r]$ のLISの長さ $\gt$ $[s_{i+1}:s_r]$ の先頭が1という条件のLISの長さ

と表せる。

メモ4

左から貪欲に変更していくことができると非常にうれしいので、貪欲で良いことを証明したい。

まず左側の条件を考える。既に左側の1を0に変更していた場合、 $[s_l:s_{i-1}]$ の末尾が0という条件のLISの長さは常に長くなるが、 $[s_l:s_{i-1}]$ のLISの長さは長くなる、変わらない、短くなるのどれもあり得るため、変更できない条件を見ると左側の変更によって、右側の変更を妨げない、もしくは促進する。

右側の条件を考えると、影響がないため、左側の変更によって、右側の変更を妨げない。

よって、左から貪欲に変更していくことが可能である。

なお、右側から変更していくと妨げる場合があるので注意である。

解法

今見ている文字の左側の0で終わる部分文字列のLISと1で終わる部分文字列のLISの長さの差、右側の0で始まる部分文字列のLISと1で始まる部分文字列のLISの長さの差が求められれば良い。文字が2種類なのですべて持っておきながらLISの長さを求めることが可能である。

実際にACした提出

https://codeforces.com/contest/1204/submission/59269885

2019-08-03

Codeforces Round #576 (Div. 1)C-Matching vs Independent Set

Codeforces

問題概要

3Ｎ頂点Ｍ辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。

・互いに辺で結ばれていないサイズＮの頂点集合

・互いに頂点を共有していないサイズＮの辺集合

解法

全ての辺を好きな順番で見ていき、これまでに辺集合に追加した辺と頂点を共有しないならその辺を辺集合に追加する。

全ての辺を見終わったときに辺集合のサイズがＮ以上ならばそれが答えで、Ｎ未満ならば、辺集合の辺の端点となっていない頂点Ｎ個が答えである。(どちらもサイズＮまで小さくする必要がある場合がある)

これは余った頂点間に辺が存在するならば、辺集合に新たに辺を追加できることから、どちらもサイズ以外の条件は満たしているし、頂点の数が3Nなので少なくともどちらかはサイズの条件も満たしているのでうまくいく。

実際にACした提出

https://codeforces.com/contest/1198/submission/58131409

2019-02-22

全国統一プログラミング王決定戦本戦-F Flights

AtCoder

問題概要

N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、 $x_i \leqq x_j , y_i \leqq y_j$ を満たすときにij間に距離 $cost_j$ の辺が貼られる。

スタートからゴールまでの距離の最小値を求めたい。距離は $dist$ で表す。

メモ

まずスタートとゴールを $(x,y)$ で比較したときに、常にスタートが小さくなるようスタートをゴールを入れ替えても一般性を失わない。

$(x,y)$ の昇順に頂点を見ていくことで、移動を「左下からの移動」「左下への移動」の2種類のみとして考えることができる。

左下からの移動

頂点iに左下にある頂点kから移動する場合

$dist_i=min(dist_k)+cost_i$ である。

これは各頂点に対して $O(N)$ であるため後に高速化することを考える。

左下への移動

頂点iから左下にある頂点kへ移動する場合、全てのkに対して

$dist_k=min(dist_k,dist_i+cost_i)$ である。

これも各頂点に対して $O(N)$ であるため後に高速化することを考える。

またこの時ゴールの右上にあるすべての頂点kも考えて、

$ans=min(dist_i,min(dist_k+cost_k))$ である。

mapを用いた高速化

$(y,x)$ をキーにして $dist$ を持つmapを用いることで、2種類の移動の際に見るべき頂点の数を1つにすることができる。これを実現するためにはmapの値が常に単調減少であるようにすれば良い。

頂点iを見ているときのことを考える。

左下からの移動

mapの値が単調減少であれば、 $(y_i,x_i)$ よりも小さい要素をキーに持つ要素の中でキーが一番大きな要素のみを見たら良い。これはlower_boundとprevを用いることなどで値の更新ができる。もしそのような要素が無ければその頂点にたどり着くことは不可能である。

但し追加の過程で単調減少でなくなる場合があるので、その場合mapから頂点iを削除するか、頂点iよりも後の要素の値が頂点iでの値よりも小さくなるまで頂点iの直後の要素を削除し続けることで単調減少を維持することができる。

左下への移動

mapの先頭から見ていって値が $dist_i+cost_i$ よりも大きい要素を $dist_i+cost_i$ に変更することで値の更新ができる。ここでも単調減少でなる場合があるので、mapの先頭の値よりも2番目の値が小さくなるまで2番目の要素を削除し続けることで単調減少を維持することができる。