迷いませんか?

継続しないを座右の銘に

Runの列挙 (Main-Lorentz algorithm)

Main-Lorentz Algorithm

概要

文字列のrunを O(N log N)で列挙することができるアルゴリズム
runは文字列内に現れる部分文字列の繰り返しのことで、特に長さが極大で周期が最小のものを指すっぽい
情報としては区間と周期を持ち、実際に使うときは(l, r, period)としてs[l, r)の周期がperiodみたいに持つ
注意するべきなのは、繰り返しはピッタリである必要はなくて(r - l) % period != 0でもよい
ただしr - l >= 2*periodであるもののみを考える

"mississippi"

  • 区間: [1, 8), period: 3

    • 長さ3の"iss"が7/3周期分ある
    • s[0] != s[0+period(= 3)] かつ s[8] != s[8-period(= 5)]だからこれ以上伸ばせなくて長さが極大である
  • あとは周期1で2周期分のやつが3つあるけどまあ自明なのではい

 O(N)アルゴリズムもあるっぽいけど実際に使うなら O(N log N)で十分だから、いいよね
 O(N log N)があれば実用上大体十分な文字列アルゴリズムって、あるじゃん(例: Suffix Array)

イデア

基本的には分割統治がメインアイデアになっていて、それぞれの深さについて左側と右側の境界をまたぐようなrunだけ考える

"abcbcd"

  • "abc | bcd" みたいに左右で分ける
    • " ab [c] | bcd " みたいに "c" が周期になり、またぐやつを探す
    • " a [bc] | bcd " みたいに "bc" が周期になり、またぐやつを探す
      • " a [bc | bc] d" がまたいでいて周期が2以上あるのでrun
    • " [abc] | bcd " みたいに "abc" が周期になり、またぐやつを探す

このように、中心をまたぐrunを境界の左側の部分文字列が周期になるようなものだけを探すを繰り返す
そして見つけていくときにそれが極大であることを確認し、その区間のrunの周期で現時点で最小なら更新する
極大であることの確認は、上の"mississippi"の例の極大の確認の仕方をやればよい
すると極大かつ周期が最小のものだけが見つかる
例では左側しか見てないが、実際には右側の部分文字列が周期となるものも考える必要があって文字列をreverseしてよしなにやると楽

ある文字列について、runの総数はそれぞれの分割統治の深さについて O(N)個、深さが  O(log N)個(修正しました 11/28 17:36)なので全部で O(N log N)個に収まることがわかる
なんかいい感じの論文を読むと普通に O(N)個であることが多分わかる(まあそうじゃないと O(N)アルゴリズム、ないよね)

中心をまたぐrunの見つけ方

ところで、それぞれの深さについて O(N)で跨ぐようなやつを求めるのはどうやるの?という気持ちになるのでそれを説明する
その要になるのがZ algorithmで、うまく使うとうまくいける

Z algorithmって、なに?

それぞれのsuffixがもとの文字列とprefixが何文字一致しているか
文字列sについて、Z algorithmで求められるものを z[i] とする
すると、 s[i, i+z[i]) == s[0, z[i]) && s[i+z[i]] != s[z[i]] が成り立つ

s = "a b c b c d"(空白は無視)
z = {6,0,0,0,0,0}

わからせる気のない例

これを周期を求めるのにうまく使いたくて、繰り返し、文字列、アルゴリズムみたいなことを考えると(K)MPが思いつくけどなんかZ algorithmでもよい
結果だけ言うと、 s[0, i+z[i]] が周期 i の繰り返しになっている(ただし最小とはいっていない)
ただ、周期 i が最小じゃないとき、 最小となるべき j < i を見るとき既に考えているはずなので大丈夫

Z algorithmを使って、どうなるの?

s[i, m) を周期とするrunを探そうとしているときs[0, i) のSuffixと s[m, |s|)のprefixにいくつ繰り返しがあるかを知りたい
s[0, i)のsuffixについては、 s[0, m) をreverseしたものに対してZ algorithmを適用する
そうすると、s[i-1]に対応する位置の値を見ることで周期を m-iとする繰り返しがどこまで続いているかがさっきのやつからわかる

s[m, |s|)のprefixについては、 t = s[m, |s|) + '#' + sを考えてZ algorithmを適用する('#'は実際には必要ない)
そして後ろ側につけたss[i] に対応する場所の値をみることで周期を m-i とする繰り返しの長さがわかる

例(とても見にくい)

s = "missis | sippi"

rev("missis") = "s i s s i m"
z1 = {6, 0, 1, 2, 0, 0}

"sippi" + '#' + s = "s i p p i # m i s s i s s i p p i"
z2 = "17, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 1, 5, 0, 0, 0, 0"

  • この時、"sis"を周期とするものが最適なのでそのときどうなるかを見てみる
    • 左側について、z1[3]を見ると2なので、周期3で長さが5であることがわかる
      • 左側は周期とする部分文字列自体があるのでその分の長さである3を加える
    • 右側について、z2[9]を見ると2なので、周期3で長さが2であることがわかる
      • z2[9]は#の右側で"sis"の先頭に対応している
    • よって左側と右側を合わせることで周期3で長さが7であるものが見つかった

これを左側の全部のsuffixについて行えばよい
最初に行うZ algorithmもその後の計算も O(N)なので、分割統治のある深さについて全部足しあわせても O(|S|)で収まるので大丈夫

ここまでを実装すると、できる
添字がごちゃごちゃして辛くなったので頑張ってください

https://judge.yosupo.jp/problem/runenumerate
ここでverifyとACコードの確認ができる

例題

計算量は明らかに駄目なんだけどなんか十分な速さで通ったし他の解法よりは速いので...

ICPC Asia Hua-Lian Regional 2017 L - Finding the Bases

ある文字列Sが与えられる。
その文字列の部分文字列がある文字列Tをいくつかつなげたものになっている時、その部分を圧縮してTにすることができる
既に圧縮した部分文字列を含む部分文字列をもう一度圧縮することはできない
最適に圧縮した時長さを最小で何にできるか

|S| <= 10000
T <= 10

通している人の多くはKMPでループを見つけてやるみたいな  O(N^2 * T) 解法で、めっちゃギリギリなんだけどすこしうまくやって早くすることでなんとか通る
runの列挙を用いて通すには、(l, r, period)をまずl <= i < r && r-i >= periodとなるiについて(i, r, period)をrunに追加する
そしたら単純にDPをすることができるので通る
最初のrun列挙に O(N log N)、runの数は O(N)に抑えられるので展開すると  O(N^2) になる
DPの遷移はそれぞれのrunについてdp[i + l + k*period] = dp[i] + 1 みたいにkをループで回す必要があり、すべてのrunについて考えると  O(N^3)
余裕でこう考えると間に合わなくなってしまうんだけど、まあrun同士の被りとかがうまいことになって減るので早くなる
ただし、最悪ケースでは  O(N^2) ぐらいは必要になるけどテストケースの弱さとか色々期待すると通る

はてなブログtex記法わからなすぎる、どうすればいいんや
熨斗さん、ありがて~

うまくrunを解析すると場合分けすることで十分速い計算量で通すことができるらしい
ブログは...でるんでしょうか...

ICPC Asia Taipei-Hsinchu Site Programming Contest参加記

ICPC Asia Taipei-Hsinchu Site Programming Contest 参加記

海外遠征、大学から少しでも金が出るんだったら行きたいという気持ちになり、なんかいい感じのやつがあって出たので行きました
台北を選んだのはちょうど大学の文化祭があって前の火曜から次の月曜まで休みになるので公欠取れなくても大丈夫だったからです

チームメイトに台湾に数回いったことがある人がいたので安心して行くことができた

1日目

流石に前泊的な感じのことをしないと体力が死ぬので金曜日に台湾につく
すぐにホテルにいって荷物を預け、台湾といえばという気持ちでかき氷を食べに行く

めっちゃ美味しいんだけど冷たすぎる、ところで台湾は暑すぎる
口の中が甘くなったのでしょっぱいものをということで屋台ではないけど通りで小麦粉を焼いたものに色々挟むみたいなやつを売ってる店があったので適当に買って食べたらお腹いっぱいになって破滅する

他のRegionalに行った人がマッサージを受けていて羨ましすぎたので台湾マッサージを受けに行く
最高にリラックスできたのでめっちゃいい気持ちになる

お腹があまり空かなかったのでそのままホテルに帰って寝る

2日目

適当に起きて、プラクティスに向かう
チームの席は長机を互い違いに二列に並べたものが五列ある感じで、席に座って斜め前に2つ自分の方を向く机があることになるが普通に机の上が見えて、なにこれは...となってしまう

わくわく

オープニングセレモニーとか色々ある
横浜では指示や挨拶はすべて英語で日本語は一切使用されなかったが、中国語を普通に使っていて交互に使われたりすると耳が慣れなくて元々英語のリスニングが苦手なのに一切聞き取れなくなってしまった
ちゃんと聞き取れてないのでわからないがコンテストの本質に関わる、注意事項やコンテストの開始時間以外についての指示は中国語のみで行われていたものもあったと思う
この時点で少しワクワクコンテストの雰囲気が強くなり始める

ラクティス

とりあえずCLionのセットアップとCapsLockをCtrlにするやつをやろうとするが、CapsLockを間違えて押したあとにCapsLockをCtrlに変えてしまい直せなくなってしまう
めっちゃ焦りながらキーボード設定からUSを消して入れ直すをしてI got Kotonakiをする

  • A, Bがやるだけなので、やる
  • Cが貪欲とDPが同じ解にならない最小の金額を求めろってやつで、見たこと、あるな(解けない)をする
  • Dが簡単だったはずなのでそのままやる
  • Cが普通にDPで最小を求めて貪欲と比較すればいいことに気づきできる

上位チームが早すぎて早すぎるでしょ...という気持ちになる

なんか弁当を配られるが台湾の料理を満喫することが目標なのでそれを手にしたまま牛肉麵を食べに行く
肉の硬さに恐ろしくばらつきがあってびっくりしたけどおいしかった、麺が腹にたまる
帰りはタピオカを買って帰る

DDCC予選にでてレートを少しだけ上げる
簡単めのインタラクティブは、たのしいという気持ちになるけどなんか3Nは間に合うという気持ちになる時間でペナルティと時間を無駄にしてしまった
Dは編集距離3(変数名を間違えていた)で通らず、最後まで気づけなかったのでアになってしまった
多分通ったと信じている

もらった弁当を少し食べてみると味が濃かったり色々であまり美味しくなくて悲しくなった

3日目

朝、早起きをして会場に向かう
Cloakに荷物を預けて席につくが9時半近くになってきても周りの席が全然埋まっていないため予知能力が働きコドフォることがわかる
15分コドフォる

なんとか始まる

コンテスト

とりあえずセットアップをしたあと、A問題の概要を聞いてとりあえずDFSをうまく実装すれば行けるな...ということを察して他のを読んでもらう間に書いておこうとする
そしたらその前にCとDが通っていて、他のチームの英語を読む速度に一同驚愕...
上位チームが解いている問題を追っていく感じになってC、Dを通す
H、J、Kが通っているのでとりあえず読んでもらう

JとKはやるだけを感じたので実装を始め、Hが詰めれる自信0になったのでチームメイトに任せる
Kは隣り合ってる必要がないことに気づき適当にpriority_queueとかで実装してAC
Jはstringでやれば、いけるやろ!と思って実装したらTLEになってしまったのでbitsetで実装して1ペナでAC😢

天才チームメイトによりHの式が出てくるのでそれをそのまま書いたら通る、チームメイトが天才過ぎて怖い

Aを1位チームが通したので頑張ってペアプロっぽく実装を始める
メモ化しながらDFSをしていくんですが、こういう同じ盤面が現れうるメモ化DFSの実装は毎回バグらせていて無限にバグらせる
なんとか盤面とかかっている手数の両方をキーにしてメモすることでなんかうまくいくのでAC(無限時間かかった)

M、H、Lあたりを通しているチームがいて、Mは明らかに天才数学ゲーなのでひとまず捨てることを決意する
Hはチームメイトが少し詰めてくれたので更にちょっと式変形して実装して投げてWAになる
構築は、無理
解法自体間違ってるが実装も無限に間違えていたのでそれを少しずつ直しながら投げて無駄なペナルティを積み重ねる
解法を考え直している間にLのために凸包あたりの幾何を写経してもらう

Eが1つ目の要素を-1にしてやるとうまく大体作れることがわかり天才になった気分、そして作問者天才か?台北、すげ~~~~!!!!という気持ちでACする

Lの写経が終わるので凸法を求め、凸包の頂点数が2以下の場合は0、三角形の場合は場合分けし、あとは四角形の対角線となる凸包の頂点対をしゃくとりで求め対角線の両側として凸包上から三角形を最大化するやつを取り出す感じで実装する
3e8みたいな出力にはするなというのを見つけ、まあfixedとsetprecision(10)みたいなことをすればそうならないんですよねという気持ちでそれを書く
結構しゃくとりをバグらせてしまうがサンプルが合うのでとりあえず投げる

WA

泣きながら少し修正して投げるを2回やる

WA x 2

精度かな~やっぱ!wと言いながら#define double long doubleをして投げる

WA

裏の一番上を見ると、余計な0を表示するなと言われているのでfixed setprecision(10)を削除して、2倍して丸めて2で割って出力をして投げる

WA

三角形の面積の2倍が整数だけで計算できることに気づくがそれを実装する時間がないので7完で終わり

終了後

右前のチームの人に、A問題どうやって解きましたか?と英語で聞かれたので圧倒的コミュニケーションスキルと英語力で対応する

僕「あ、えっと...DFS ...」
その人「It takes too much time ?(みたいな感じ)」
僕「え...memorization...? DFS with memorization ...」
その人「(聞き取れない)」
僕「(コードを見せながら) like this ... key is a condition ? state ? and turn ... ?」
その人「I can't read your code ...」
僕「ア...ア...」
その人「Ah... Sorry ...(去っていく)]

自分、英語の勉強いいですか?
これで周りの人とコミュニケーションをとる勇気が0になるので会津の人とすこし話し、8完していることを知って悲しくなる

その後、出力形式とか大丈夫ですか?って言われて、まあ両方対策したつもりなんで大丈夫だと思うんですけどね~~と言う
手元で適当に一辺1e9の正方形で試すと1e18って出力されてなるほどね、となる
fixed setprecision(10)を消した時点で指数表記になっていた。終わり

実際このコードをもう一回なげて試すことはできなかったので本質があっていたかはわからないのでア

表彰式っぽいのが始まると、中国語しか喋らず突然1位から表彰しはじめてyesnoないの?そもそも英語は?となるが国内予選の話っぽいことに気づく

yesnoが始まる前に海外最優秀チームの表彰をしたけどこれは流石にAsiaのことじゃないですか?ネタバレでは???

yesnoが始まり、凍結時点で13位だったんですが下のチームがLを投げまくっていて終わり...という気持ちで眺める

案の定抜かれまくり、悲しくなる

横浜では4完内1位で20位だったと思うんですが、7完内2位で20位になりました
世界一Asiaで20位を取るのが上手です、よろしくおねがいします

yesnoの途中で60位ぐらいから上位10チームがゴールド、そこから20チームぐらいがシルバー、残りがブロンズみたいな感じで表彰がありめっちゃ時間がかかる
20位なのでシルバーだったんですが、もらえる盾が明らかに金色なのでSilverという文字を隠してTwitterに上げるなどをした

ところでこういう上位3チームじゃなくてN割に金銀銅賞を上げる形式紛らわしいし他の界隈には馴染みがなさそうでめっちゃ本来よりすごいと見られてそうで怖すぎる

懇親会が始まり、弁当のことで少し怖くなりながら行くととても美味しそうなので嬉しくなりながらすこし食べる

実は小籠包が食べたかったので懇親会はそのまますぐに抜け出して食べに行く
少し(デザートは一つを除き全種類)食べたのでお腹が少し苦しかったけどとても美味しかった

ちょっと遅くなったけどunratedなのでABCに出てAの提出から大体30分弱で全完する
帰りながら問題は読んでいました...

チームメイトはratedなのに30分遅れ参加していてすごい

寝る

4日目

帰りの便が15時半なので適当にお土産を買う場所を案内してもらいながら色々買っていく
明らかに買いすぎたんですが、コンテスト参加費が一人3000元なはずはないけど念の為とおもいそれだけ引き出してたのでまだまだお金が余ってしまった

空港でタピオカを飲み、終了

おわり

海外遠征、とても楽しいのでやるべきなんだよな、お金が出るなら(来年は国内予選でいい結果出して補助がほしい)
台湾は結構日本語通じたり、そもそもジェスチャーで結構なんとかなったりするので結構よかった
料理も美味しく、最高
問題のセットも、国内予選通過チームが多いからか簡単枠も多くたくさん通せて楽しいしよかった!
E、F、Iは既出で、E、Fに関してはサンプルケースすら丸パクリだったらしい、ワクワクすぎる
来年台湾に行く人はたくさん練習とかバチャをしてこの問題バチャでやったことある!状態にするのがいいと思います(?)

ICPC 2019 Asia Yokohama Regional参加記

ICPC 2019 Asia Yokohama Regional Contest 参加記

大学生にもなったので、二大高校生の時から参加したかったコンテストであるところのICPCアジア地区予選に参加してきました
ちなみにもう一つはCODE FESTIVALです。ICPCにもコドフェスパーカーの人が結構いましたね、コドフェスさん・・・?

一日目

会場に行った
なんかpractice前の色々が長いなぁという気持ちになった

practice

A

やるだけ(だった気がする)

B

最初連続しない部分列だと勘違いしていて、解けねぇ!って言っていた、解けるらしい、どうやるの

C

最近のチーム練や学内練習で出てきたので余裕なんですよねと言いながら実装する
なんかバグってFA取れなくてとても悲しくなる

D

チーム練で解いたので解けるんですよねって言ってたらREした
最短路の復元ができていなかった、最短路復元が苦手すぎる

チームイントロダクション

英語が喋れず聞き取れずなので厳しい
みんな面白すぎるんですよね、すごい
チームのスライドに載ってた3つは僕がいらすとやで探してきた賢そうなものです(Les sagesなので)

なにがあったっけ

多分帰った
なんか異常に眠かったり頭いたいなぁと思っていたら熱があったのですぐ寝た

ツイッターでなにもアクションを起こさなかったけど実は結構起きて風呂にも入っちゃった

二日目

体調大回復時代になった

朝ごはん食べたかったので関内に朝からやってるモスがあるのを見つけて食べる

日本大通り駅で待ち合わせだったので迷いながら向かうとなんか駅がなかったので迷ってしまった
まあRegistrationに間に合ったのでセーフ

英語が聞き取れないので30分までまだ数分あるのに急にカウントダウンが始まってなにこれは...みたいな気持ちになる
なんかカウントが終わると周りが封筒開け始めたのでコンテスタントの民度さん!?と思ったらなんか開始時刻早めてたらしい
コドフォの逆はわくわくじゃないと思いましたか?当然わくわくだと僕は思うんですけど(謎理論)

本番

  • 適当にセットアップをしてる間にAが解けてたので少し確認して書いてもらう
  • AC
  • Bを読んで、貪欲で....ええんか?となりながらチームメイトに聞いたら大丈夫と言われたので信じて実装して投げる
  • AC、すごい
  • 残りを分担しながら読んでいく
  • ここらへんでHが解かれまくってるので考える
  • 括弧列、平衡二分木に乗った気がするな~覚えてね~!とか言ってたけどよく考えたら末尾しか操作しないのでなんかうまくいきそう
  • 適当にセグ木を写経して二分探索onセグ木を二乗かけて書いて投げる
  • AC
  • Iが橋とか色々あれだなぁと思ったのでそこらへんの写経をしてもらう
  • Eが通されまくってるので問題概要をチームメイトから聞く
  • めっちゃ難しそうだし色々ガバガバだったので自分で読み直したら全然違うのでキレてしまう
  • それでもちょっと難しいけどどれとどれは同じ側にあってどれとどれは違う方にないといけないかがわかるのでUFで頑張る
  • 適当にDPをすれば良さそうとなって写経が続いてたので少し詰めようとする
  • ここは完全に僕のミスで、写経よりほぼ詰まってる状態ならそっちを実装するべきだった、ペナルティよくわからん
  • 実装は簡単だったので投げる
  • AC
  • Gが通りまくってるので読む
  • これはAhoCorasickですね、間違いない...
  • 違くない?
  • 普通にとreverseした単語で、どういう文字列が余ってるのを作るのに何文字必要かを計算したい気持ちになる
  • まあ想定解と違うんですけど多分うまく実装したら通る予定だった
  • めっちゃ実装がごちゃって通らないので人生が終了する
  • Lowlinkと二辺連結成分分解の写経が終わるのでIを実装しようとする
  • どうやって実装すればいいか、わかりませんが....
  • おわり

実装力が、なさすぎるだろ
ICPCは考察力より実装力がまず大事ということがわかり始める
AOJ-ICPCを、やっていきたい...

閉会式

英語が聞き取れず、5時間コンで疲れてるのでめっちゃ眠いけど耐える
Yes/No、楽しすぎないか?普段のコンテストからYes/Noほしいけど
最後に全提出しちゃおっかな~!wとか思ってたけど流石にやったら恥ずかしすぎたのでやらなくてよかった

懇親会

企業賞のいろいろが始まるけど、20位にくれそうなのがなさそうだったので数独をやりに行く
とても難しいけどすこしずつチームメイトのを写して頑張る
なんか突然チーム名が呼ばれるのでびっくりしながら前に行って企業賞を受け取る
NTT Communications様、ありがとうございます!何よりも欲しかったワイヤレスイヤホン!太っ腹!
G通せなくてよかった~!(?)

数独を引き続き解いてるとなんかご飯が解禁されるけど解けないので解き続ける
解き終わったらブースに持っていくとタピオカがもらえてJKになって優勝してしまった

流石にお腹が空いてるのでタピオカと企業賞で埋まった手で皿を持ち見渡すとそこにはほぼ何も残っていなかった
競プロer、食が細いイメージがあるけどそんなことは全然ないんだよな、油断していた

コミュニケーション能力に満ちあふれているので他の参加者と積極的に交流をした
多分僕と話してない参加者はいないと思います
そして参加者は多分慶應以外は全部で4人ぐらいだと思います
悲しいね😢

適当に企業ブース巡りをしてるとみんなが数独と謎の紙でなにかをしていたのでGoogleのブースに向かうともうないですと言われてしまう
みんなはサンプルから問題をエスパーしてるけど僕は無からすべてをエスパーしました、なにもわかりませんでした

流石に疲れたので帰宅をする

おわり

チーム練で去年一昨年のをやったら15位ぐらいにはなってたのでそれぐらい取りたかったけど無理だった
謎枠、あるのかわからないけどあったらめっちゃ悔しくなってしまうのでやめてくれ、台北にも行くのでそっちで15位以内取れたらあってくれ
台湾の過去問、何も見ていない(ア)けど頑張っていきたい

いろいろな方々!ありがとうございました!!!

光の反射 - DISCO presents ディスカバリーチャンネルコンテスト2019 本戦

光の反射 - DISCO presents ディスカバリーチャンネルコンテスト2019 本戦

今年のはじめぐらいにあったオンサイトコンテスト、700点埋めをしてたら避けていた幾何に引っかかったのでやることにした
本番ではDでめっちゃ詰まって時間を溶かしたものの解けなかったので許せねぇ

他人の幾何ライブラリの使い方(beetさん)という気持ちで書いていく

問題概要

平面上に単位円(部屋と呼ぶ)とその中にもう一つの円(柱と呼ぶ)がある。2つの円の間の点が与えられるので、その点から出発して柱に当たらないような直線を引くことができる。このとき、t (0 <= t <= K) に対して次の質問に答えなさい。

  • 直線を単位円内でt回自由に曲げられるとき、直線が到達可能な単位円の円周上の長さを求めよ

問題文
普通にわかりにくくなったので読んで、問題文書く人すごい

解法

正直なところ解法考察パートは100点!みたいな気持ちになる。毎回曲げる場所は円周上にしたくて、曲げる角度は柱への接線にしたいことがわかるため
つまり、実装としては出発地点から柱に向かって右回りと左回りそれぞれ接線上を直進させ続けて円との交点を見つけ、右回りと左周りのたどり着ける限界の点の間の円周はどれぐらいの長さがあるかを知りたい
このとき、途中で右回りと左回りの直線が交差したらそれ以降の答えは1であることもすぐわかる

知りたいこと

  • 円周上での限界点間の距離
  • 接線
  • 接線を引いたときの円との交点
  • 途中で交差するかどうか

実装だるそう...という気持ちになるのでこちらを取り出します
https://github.com/beet-aizu/library/blob/master/geometry/geometry.cpp

いつもありがとう、beetさん
beet libraryなので僕は略してbeelって呼んでます
これをまずファイルにコピペしてスタートです。

円周上の限界点間の距離

単位円なので距離は弧度法においての角度になります   右回りでの限界点をr_pt, 左回りでの限界点をl_ptとすると、r_ptから時計回り側のl_ptとの間の角度が答えだとわかる
ここはbeetさんライブラリを使わずにatan2とかいう便利なやつを使う
d1 = atan2(r_pt)と、d2 = atan2(l_pt)をして、d1 > d2であってほしいのでそうでないときはd1 += 2*M_PIをしてd1 - d2で大丈夫

接線

ここから先はl_ptとr_ptそれぞれで処理をする
r_ptだけで書くがl_ptでは逆にして書けばいい

接線は、適当に図を書いてゴニョゴニョすると三角比とか数学でわかりそうだな~という気持ちになるが、頭を動かすのをやめてbeetさんライブラリを覗く
なんかtangent(Circle c, Point p)みたいなのが見つかるのでこれを使います
接点を返してくれるが、2つあるのでどちらを選ぶべきかというと今は右回りを考えているので柱に向かって右側のを選ぶ。これは今いる場所から柱の中心を見て時計回りの方だと考えることができるのでそういうやつがないかライブラリの中を見ます
ccw(Point p0, Point p1, Point p2)というのが見つかる。これはp0から見てp2がp1のどっち側にあるかを返してくれる。返り値は#defineされた定数が返ってくるが今回はこれがCCW_CLOCKWISEとなっている方を選ぶ

auto p = tangent(pillar, r_pt); // pillarは柱
if (ccw(r_pt, pillar.c, p[0]) == CCW_CLOCKWISE)
  return p[0];
else
  return p[1];

こんな感じにすればほしい接点が手に入るはず

接線を引いたときの円との交点

r_ptと接点がわかってるのでこの2つを結ぶ直線と円との交点がほしくなる。
僕は図を書かないとどうやったら求められるかわからないんですが、beetさんライブラリを見るとgetCrossPointCL(Circle c, Line l)みたいなほしいやつそのままの名前のやつがあるのでこれを使う
これも、円の内側から直線を引くと交点が2つできるんですがr_pt → 接点の方向にある点がほしい
これはr_ptから見たベクトルの内積が正だったらいいので、dot(Vector v1, Vector v2)を見つけてこれを使います
beetさんライブラリではVectorはPointの別名になっていて、Pointは引き算が実装されています

// Point tan_pt ← 接点
auto p = getCrossPointCL(C, Line(r_pt, tan_pt)); // Cは単位円
if (dot(tan_pt - r_pt, p[0] - r_pt))
  return p[0];
else
  return p[1];

これで限界点がわかりました

途中で交差するかどうか

r_ptから次のr_ptまでの線分と、l_ptから次のl_ptまで線分が交差しているかを判定する
次のr_ptとかは接線を引いたときの円との交点がそれに当たる
線分の交差判定、確かめんどくさいんだよな~という気持ちになりながらbeetさんライブラリを見るとintersectSS(Segment s1, Segment s2)みたいなほしいやつがあるのでこれを使う
ただ、最初はl_ptr_ptを同じ点で始めるので最初はここで交差したことになってしまうので、適当に弾く。僕は線分の交点が一致していれば気にしないとしたが、l_ptr_ptが一致してれば気にしないようにすれば楽そう
Segmentは端点2つで作れます

// Point new_l_pt, new_r_pt ← 次の限界点的なの  
Segment s1(l_pt, new_l_pt), s2(r_pt, new_r_pt);
if (l_pt != r_pt && intersectSS(s1, s2))
  return true;
else
  return false;

適当にフラグを持っておいて、交差したら立ててそれ以降1を出力し続ければいい

これで解けたのでbeetさんありがとうという気持ちになることができる
最初普通に実装方針に迷ってたんですが、どっちが右側かを判定する方法がわからなかっただけで時計回りとかで行けると気づけば終わりだった

僕の提出

ICPCにも適当に改変したりしなかったりして持っていきたいと思います!!!!

会津大学競技プログラミング合宿2019 参加記

会津大学競技プログラミング合宿2019

大学生になり、開催日が夏休みに含まれるようになったので念願のACPCに参加してきました
JAG合宿から一日あいてすぐなので疲労がやばいと思っていたけど思ってたより疲れてなくて自分の体力を褒めてあげたい

Day0

普通に寝落ちしてしまった、眠いから寝る

Day1

寝落ちしてしまったので荷造りを一瞬で終わらせる、ホテルはタオルが用意されてるから神なんだよな

通勤ラッシュの中、クソデカスーツケースを持って東京に向かって新幹線に乗る、新幹線は快適
郡山についたら軽く朝ごはん的なものを食べた

なんちゃらかんちゃら線に乗るんですが、1号車に乗ろうとしたら変なところに乗っていた、謎の力が働いてしまった...

会津若松に着くまでの間に唯一の夏休みの宿題が、夏休みが始まって1ヶ月以上でようやく終わった、長く苦しい戦いだった
まずワシントンホテルにスーツケースを預けに行った、天才なので
そしてplatypusさんが高速バスで来るのでそれを待ってから歩いて会津大学に向かった. 過去のPCKで忘れ物をして会津大学ワシントンホテル会津大学を徒歩で移動した経歴を 持っているので余裕やろと思っていたら最初の方向を間違えていたため知らない道を歩いていくことになった、Google Mapありがとう、世界一好きなサービスです!

自己紹介フェーズをなんとか無難に終わらせ、Fixstarsさんの会社紹介聞いた、労働してーなー!俺も

チーム分けは事前にコミュニケーションをして根回しができないので†ランダム†で、よこさんとshotさんと組んだ

コンテスト

まずCを読んで、SCC貼るだけやんけ!コピペして終わりや!と思ったけどとりあえずAを実装してもらう
Aが通るのでCを書いて提出してPresentationErrorになってキレる

DとEを読む
Dはシミュレーションすればいいかなと思ってshotさんに書いてもらったら詰まってたので僕が書くことにした。僕は無限にバグらせた。
もう一回最初から書き直すことであとはコーナーケースだけというところになったのでソート順を変えて頑張った

EはDPっぽいんですがなんか無理だなぁとなってしまいボーッとしていた、するとshotさんがR+Tで降順ソートすれば勝ちと言っていたので実装する
添字がアで無限にバグらせました

終わり

バグらせるのやめてぇ

ほか

喜多方ラーメンを食べにいく
こういうPCKのときはできなかったことをして会津を満喫していきたい

ラーメンを食べたらホテルに戻り、コドフォに向けて英気を養う

つもりだったんですがいつの間にか寝ていて起きたら1時半だった
風呂に入ってTwitterをして寝る

Day2

ホテルについてきたこだわりの朝食を食べる
ヨーグルトが激おいしすぎてやばい、これが会津のべこの牛乳か...

楽をしたすぎるのでバスを使って会津大学に向かう

  • PASMOって...使えますか?と聞いてしまう
  • 整理券式なのに気づかず先にお金を払おうと値段がどこに書いてるか見つけようとしてしまう
  • お釣りは出ませんと書いていて、両替の場所があるのに570円を払ってしまう

すいませんでした!!!!

チームはplatypusさんとwk1080idさんと組む
この日は5時間セットだしランダムで事故るのは厳しいのでは?と思って組んでしまった

コンテスト

Bを考察,実装する
Cをplatypusさんから受け取って実装する
Mをplatypusさんが書いた式をそのまま写す
Iを実装して、答えが全然合わないのでキレて最後の答えを出すとき1点取得をしまくることにすると合う、時間をめっちゃ潰したけど原因はセグ木のバグだった
セグ木...信じてたのに... Gの実験コードを適当に書いて規則性を見つけようとするが、普通にplatypusさんが解くまで実験コードすらバグっていた
Hみたいなのは包除なんですよ!wと言いながらなかなか立てられない式を適当に実装してみると答えが合うので提出したらAC
Lはどう見てもSCCで、マンハッタン距離なので8通りをsetで用意して候補はbeginかendなんだよな〜!マージテク!wとか言ってたが SCCの結果を木だと勘違いしていてだめだった、結局8通りの最小値しか見なくていいことがわかってただのDAG上DPになるけどバグって通せなかった

実装下手すぎないか?競プロやめたい

ほか

懇親会があるので大学から歩いて会場に向かう
未成年なので成人している人たちがどうなるか見るのを楽しみにしていた
中華料理うまいなぁ、辛いなあと思いながら適当に食べまくり、コーラを飲みまくったらお腹が一杯になった
やっぱみんなどんどん声が大きくなったり酔っぱらってるような行動になっていて面白かった

beetさんが気づいたら倒れていたのがとても面白かった、ACPC懇親会の醍醐味らしいので来年も楽しみにしていきたい

部屋に戻ってダラダラFを通したら気づくと寝ていた

Day3

もういちどこだわりの朝食を食べる
やっぱヨーグルトがうまいんだよな〜!

この日はチームはランダムで出た

コンテスト

四人チームになったので、A,B,C,Dをまず割り振って僕はDから読んだ
ただの桁DPだったのでAとCが通されてから実装してAC
Bが明らかに見た目ヤバそうで自分では実装したくないな...となっていたのでありがとうという気持ち

Eを読み、更新なければO(N)で解けるな〜累積させて〜クエリを〜とか考えて永遠に詰まっていた
僕はDUSTをといたことありますが...
結局『maximum sum of subarray update』とかで検索するとただのセグ木の問題ですみたいなことが書いてたのでわかって通す
これわからないの真面目に辛くなってしまったな
Fは一瞬うまくオートマトンとかをつくって受理されるか〜みたいな問題が存在するのかな...とか思ったけどDPをやれば良いことがわかり、実装を始める
いつものようにSA-ISとLCPを取り出し、使い方を忘れている中考察を詰めなかったので[tex: O(N log2 N)]を実装してTLEになり、assertを消して通そうとして通らず泣いていた
結局にぶたんが一つでいいことがわかったので実装バグらせて1WAだしたりREをだしながら O(N log N)で通す
解説に前計算すれば早くなるって書いていて、確かにO(N)じゃ〜ん!となってしまった

Gは明らかにすこしめんどくさい全方位木DPなんですが、全方位木DPを思考停止で書けないので残り時間的に不可能だなぁとなってしまった
おしまい

実装力の無さを無限に感じてしまうな...

ほか

忙しい大学生なので予定が詰まっていたため早めに帰る必要があったので解説を聞かずに誰とも挨拶をしないで帰る

前もってバスを調べていたので余裕なんですよねとか思いながらバスを待っていたら10分経ってもこなくて、バス停にいたもう一人の人がタクシーを呼んでいなくなってしまい 電車の時間的にもやばくなってしまったのでタクシーを呼ぶ決意をしてタクシーを呼んだ

ゆるせない

なんとか電車に間に合ったのでそのまま帰宅する

お疲れさまでした!2泊3日のACPC楽しかったです!JAG合宿からそのままということで体力的にきついものがありましたがゆっくり休みたいと思います!

友達との旅行に、家に30分ぐらい滞在してすぐに出発した
体力終了

Japan Alumni Group Summer Camp 2019 参加記

Japan Alumni Group Summer Camp 2019 参加記

JAG 夏合宿にチームメイトがだれも参加しないという異常事態のなか参加しました
僕が春合宿とかPCKでよく話していた人が誰もいない気持ちになって不安がやばかったんですが、 なんとか他の人とコミュニケーションを積極的には取らないことで乗り切りました、乗り切れてません

Day1

お昼を早めに食べてから会場に向かう

チームメイトがいないのでぐっちょっぱーで分かれるやつをして、olpheさんとferinさんのチームに入らせてもらうことになった

コンテスト

BとJを実装しました、チーム戦難しすぎるなぁという気持ちになった
実装のバグや勘違いをolpheさんに直してもらったりとかした

前にUKUNICHIA、右にSeica on the World、左を忘れてしまったけどそれぞれ数個風船を得ていて囲まれてしまったという気持ちになった

夕ご飯

写真を取り忘れたんですが、ビビンバの具が異常に少なくてかなしくなった

ほか

風呂が異常混雑していてやばいんですが、やばい
100円を忘れずにうまくロッカーから取り出してカフェオレを飲んで勝ち

ボードゲームをしたかったんですが、なんか埋まっていたので悲しくなりながら部屋に戻り、気づいたときにはコドフォにレジってAを提出してしまっていたので部屋で黙々とコドフォをした
5時間セットが久しぶりすぎて疲れてたので実装が全然うまくできなかった、疲れてなければもっと順位高くてレートも上がったんだろうな〜!

Day2

朝ごはんを8時ぐらいに食べに行くことで混雑を回避できて常勝w

チームは、余った人で組んで2人チームで参加することになった

コンテスト

虐殺セットに虐殺されてしまった〜!
DとEを担当しました、やるだけをやるだけの人生、つらいもの

懇親会

天才なので空いてるうちにと思ってすぐに風呂に入りに行った

懇親会素晴らしいね
3000円のディナー、豪華絢爛

ほか

ABCがありましたね、僕はボードゲームをしたいので出ません
と宣言して結局出ました、ベッドに寝っ転がりながら出たら眠気にやられて死亡してしまった
ボードゲーム、一回もできませんでしたが僕は何をしにJAG合宿に参加したのでしょうか

なんかルームメイトはまだ起きてそうだったけど眠くなりすぎてしまったので寝た

Day3

部屋を片付けて、荷物を持っていきながら朝食を食べれば効率的やん!って言いながらやったらまずシーツの回収が行われていなかったので優しい方のお世話になってなんとかした
当然8時に行くと空いてたので8時半に行けばとても空いていて快適朝食エクスペリエンスが得られるんですが、普通に少し混んでいるのに加え米がなくなっていた

チームは、tubuannさんがWriter側にいることで枠が空いたUKUNICHIAに入る感じになった
これでTTPCでtubuannさんと組んだので現UKUNICHIAの全員と組んだことあることになるね、やったぜ

コンテスト

A、Eをやって、Bを考察した
Bみたいなの、自分で実装したら絶対バグらせるのでbeetさんに実装してもらう贅沢をしてしまった
Eもデバッグしてもらったしすごいね

ほか

帰宅した
家に帰って22時ぐらいに眠くなって寝てしまい、更に6時ぐらいに起きたのでJAGの生活リズム改善能力に恐れをなしてしまったけど来年からも夏休み最後に生活リズムを直すために行きたい
これだけでも参加した価値あったね

ICPC 2019 国内予選参加記

ICPC 2019 国内予選

大学生になったのでICPCの国内予選に出ました
チーム名は『Lesages』で33位でした。順位表

ABCDの4完で、僕はABCDを担当しました(仕方ないね)

国内予選まで

大学生、自由になって時間がありあまり、遊びまくれると思っていたら授業が難しいしテスト多いし全然何もできないなとなり 競プロもそこで時間を割いてまでやるか?という感じでモチベーションが消えてしまう
週末のABCぐらいは頑張って出ようとしてたが週明けというのは課題か小テストがあるものでそれを言い訳に出ないことが多々あった
実装力や考察力が恐ろしく下がったので継続って重要だなとおもいました

チームでの練習は色々とグダグダで、毎週木曜に大学?サークル?で競プロの集まりがありそこで1時間4問ぐらいの軽いバチャをするんですが最初の方は普通にバラバラで解いてたし、最後までいい練習場所を見つけられなかった

普通にチーム練をしたのは一回だけで、カラオケで去年の国内予選をしたが僕がA,B,Cを解いてしまっていたという失敗がありそこらへんは全部任せたが普通にチームメイトが通せて安心した
僕はDが解けてFは解法わかったがカラオケで延長失敗して追い出されて途中終了したので家で実装した(いい練習場所をください)

模擬国内予選

模擬国内予選にもカラオケから出て、このときは延長に成功して途中で追い出されはしなかった
結果としてはABCDの4完で全体27位、現役20位だったのでまあいいでしょうとなる。順位表
Cみたいな適当に詰める必要がある問題をチームメイトに投げるのが楽で良いなという気持ちになった

ただ、序盤の問題も早く解かないとICPCルールのペナルティがきついので最初の動きとかどうするべきかわからず、これは結局本番でもわからなかった(僕がタイピング一番早いので僕が全部実装することになったんですが)

ライブラリも印刷する
お守りとして某チームのライブラリも当然印刷し、beetさんとかうしさんのところから適当に拝借したやつと自分のを適当に混ぜたやつも前回の記事のやつでプリントした
大学さん、印刷代無料にしてくれ
ライブラリは目次が必要だなと思いました(はい)

前日

前日も木曜日なので大学の練習があり、ここでも1時間バチャをしたが普通に学内の他のチームに負けて険しい気持ちになる。構文解析無理ですが...
†ホスト校†なのでまあ本当に事故らなければ通るでしょ...となんとか気持ちを落ち着けて寝ようとするが寝られない、現実は非情である。次の日はテストがあるのだ。
試験勉強のためRedBull駆動で4時就寝6時半起床をする。

当日

眠い モンスターをとりあえず一気飲みする
電子的準備がどこから入るかわからず全ウインドウを閉じる人になった
なんか普通にコンテストのページぐらいは開いててもよかったのかな?わからず

国内予選

  • Aを読んでやるだけなので実装する、普通に時間かかってしまう
  • Bの問題概要を聞いて実装する。去年とは打って変わった楽さ、軽くバグらせ時間がかかってしまう
  • Dを軽く読むが普通にわからない
  • Cの問題概要と軽い考察を聞いて確かに、となったので実装する。バグらせて時間がかかってしまう
  • Dを考える、何回押すかは決まってるからDP行けるなとなるがWA
  • チームメイトがF, G, Hを適当に読んで考察をしている
  • 僕は順当にEとFの考察をしていてほしかったですが...(このブログを見ていたらある程度難易度順に解く意識を身につけてほしい、難しくても点数は変わらないので)
  • Gがわかったらしく僕はDで詰まってるので実装してもらう
  • 普通に学内2位で焦る
  • Gの解法、基本的なことはあってそうだったが微妙にダメそうだったので指摘したらDのだめそうなところを逆に教えてもらったので実装する
  • スパゲティになったがなんとか実装する
  • 通る
  • 学内1位なので†ホスト校†であることを考えると勝ち
  • Eを読むと苦行をすれば通りそうな雰囲気を感じる
  • 時間がもうないので終了

予選通ったっぽいので競プロモチベ回復した!!!
Asia Yokohama Regionalに向けて頑張っていきたい

Codeforces Round #573

f:id:pazzle1230:20190713022627p:plain
こどふぉ順位表

競プロつまんないな、やめるか