ICPC 2020 Asia Yokohama Regional Contest 参加記

ICPC 2020 Asia Yokohama Regional Contest 参加記

2021年ですけど…横浜じゃないんですけど…みたいな気持ちになりながら参加しました
嘘です。大変な中でも開催していただいてありがとうございました！

前日

なんか特にやることないな…オンサイトじゃないので特筆するべきことはなかった気がする

学生証チェックでバーチャル背景を消さないといけなかったので汚い部屋を見せることになりました
この角度で部屋を見せたこと、今まで一回もないんですけど…

プラクティスは過去問なので適当にやった、普通にD問題の解法を忘れていてやばかった、lowlinkの復習と思ってね

この後の質問タイム、必ず出席を見ていなくて質問がない人は参加しなくても良いものだと思ってしまっていました、危なかった

生活リズムを直さないと流石にまずいのと、とてつもなく眠かったので17時ぐらいに寝そうだったんだけどなんとかこらえて22時半ぐらいに寝た

当日

7時起床、偉い

朝ごはんを食べて8時半からの直前放送へ
昨日のプラクティスのときにコンテスト開始前にフォルダを準備しとかなきゃ…と思ってたんだけど忘れてることに気づいたので焦りながらやった

コンテスト

開始直後のムーブ、基本的に前3問が難易度順だったらA、B、CをそれぞれSPDさん、僕、tuteさんみたいな割り振り方をしていたんだけど 前2問しか難易度順じゃないらしいため序盤最速ムーブとしてはBをtuteさんに譲るべきだなぁというのと僕とtuteさんでBを解法絶対一瞬で出すぞ という意志を持つかで迷った

結局僕がB見なくても英語をコツコツ読むだけの人になるのでBを二人で読んだ、貪欲ということはすぐに分かったけど実装する自信がなくて任せました

BとAが通されていく間にCから読み始める

BでWAが出ていて、マジか…と思っていたら出すファイルを間違えていたらしい、ここが唯一僕がtuteさんを責められるポイントです
tuteさんの解いた問題数がやばく、このことを責めたら来年チームを組んでもらえない可能性があるため実は責めることができません

C、嫌そうな見た目をしているけど一番上の行と下の行に入口と出口があるというのが明らかに左手法意識してるのを感じはした

D、問題概要がシンプルすぎるのと典型っぽい見た目で簡単そうに見えた、節穴なので

E、見た目が嫌すぎて絶望

ここまでやった時点でtuteさんが後ろからKとJを読んでいてJが少し通されていたのと簡単だったのか書きます宣言

やべ～と思いながら僕はIが通されていたので読む

こういうDP、苦手です…と思いながらtuteさんがJを通したら渡そうという気持ちになりながらHを読み始める

H、クエリ系だしtuteさん好きそう～Iを通したら渡そうという気持ちになりました。ここでk <= 2の条件を見忘れて十数分が消えた、ア

FとGはSPDさんが読んでいて、Fは嫌な見た目をしているのとGが通されているので読むことに

G、こういうのは二分探索なんですよね～、全然単調性の欠片もありませんね…→小さい方から追加していって条件を満たしたら終了するしかないね

じゃあ後は作れる条件としてかんたんに更新していける物を見つけるだけだね→SPDさんが一晩でやってくれました

やってくれたし実装方針もくれたので実装するだけ、手柄がほしい僕は実装を奪う

あ～実家のような安心感といいながらUnionFindを両側からやってエイとかしている間にIも通されHの考察が進んでいる

Gを通した後に様子を見に行ったらほとんど考察が終わっていたらしく、kが大きいとlog必要で困るんですよね～などと言っていた
なるほど～それは困りましたね～とか言いながらCが少し通されてたので考えに行くとk <= 2なんですけど…とtuteさんに言われる
最初のは僕とはこれで相殺ということでここは一つ…

C、結局左手法の行数が小さければ全探索ができて、5行か6行ならうまくやれば…と思っていたらSPDさんが左手法を6行で実装、天才

あとは全探索を書くだけなので手柄がほしい僕は実装を奪う

実装してAC、Hがなんか少し苦しそうだったけど解法理解してないので頑張ってくれ～とtuteさんにすべてを任せる、ありがとう…

Eをいい加減考えなあかんということで考えてるとなんか角度だけでいいらしいということがわかって誤差もあるし…とPython使えるSPDさんが実装

その間Kを考察しようとしてると、targetを逆順にしてSuffix Automatonを作ってDP！みたいなことを書いて、サンプル合わなくて複数のSuffixが同じ頂点で 受理されるから駄目なことに気づいて諦め

一回サンプル確認し忘れたとかでペナルティがでたんだけど、その後考慮し忘れてたケースにSPDさんが気づいて実装しなおし

Hを実装し終わったtuteさんがKを見て、うーんこれは前から見てやればいいですねと言っていて僕は何もわからず泣きながら任せました

Eで修正したら何故かうまく行かないらしくprintデバッグを二人でしていた、なんか和が負になっていたら分岐のところで負になっているはずなのに分岐していなくて よくわからない気持ちになりながら和を少し分けるとなんかうまくいったっぽい、誤差…なんですかねぇ…

デバッグをしている間にKは通されていて、実装が、早すぎるだろ。という気持ちになっていました

EとKが4時間経過する直前に通せてしまい、DとFが残ってコツコツ考察をしていました
何もわからないということがわかった、僕が変に会話しながら考察しようとしなければもしかしたらもっと考察進んでたんちゃうかなという気持ちはあります

コンテスト終了

上位13チームぐらいのうち凍結後提出していないのがうちのチームだけで、順位これは落ちましたね…みたいな気持ちになっていた

終了後

GatherTownとやらにいって、みんなが重い重いといっている中ゲーミングPC力で圧倒的アドバンテージを手に入れて隅っこで一人ぼっちになっていた

少しpulmnと話せてやったね

夕飯を少し食べていたら解説やYes/Noの時間になった

YesNoを盛り上げるためにペナルティを犠牲にしてくれたエンタメ精神の塊チームがいたので面白かったね

結局凍結後に提出していた超えてきそうなチームは全部落としていて5位で終えることができた

なんか上位6チームは別でやります。みたいな感じになっていて、なんで上位6チームなんだ？なんかあるんじゃないのかと思っていたら特になかった

俺たちはなんの理由でコメントを言うことになったんだ…

このあとはまたGatherTownに戻って、数人の知り合いと少し喋ってそのままおなか空いたので離脱をした

リアルですら会話が苦手なのにインターネット上で会話のペースをつかめるわけがないんだよな、次のオンサイトでは対戦相手お待ちしています

互いにかろうじて見えるぐらいの位置でときどき誰とも話していないことを確認するのが最低限のルールです

まとめ

チームメイトの力を存分に発揮することができて、存分に発揮されたチームメイトの力がすごかった

表彰時のコメントで来年もチームを組んでくれという圧力を少しかけたので、チームメイト力を来年も発揮してくれ～～～～頼む～～～～

ちょっと競プロモチベが戻りました、これが大学が始まったあとも残っているかはまた別のお話

色々ありがとうございました。社会性があまりないので感謝を言う相手があまりわかっていません

とりあえず5位というすごい結果をもたらしてくれたチームメイト、ありがとう…

ICPC 2020 国内予選 参加記

ICPC 2020 国内予選 参加記

ICPC2020国内予選に参加したので参加記を書きます

去年は予選の参加記は書いてないんだけど今年はなんかみんな書いてるので書きます

チームについて

去年は同級生2人と組んでたんですが今年はレートの高い上級生二人と組みました
友情をないがしろにして勝利のみを追い求める姿勢、最終的に負けるタイプのキャラっぽい

春ぐらいで既にチーム自体は組んでたと僕は勝手に思い込んでるんですが、 片方のチームメイトがコドフォバチャを毎日やっている異常者すごい人になっていて コドフォのレートは当たり前に越されてレッドコーダーになり、予選が延期されて更にRatedが増えたことでAtCoderもすっと抜かれました、早く橙になってください

もう一人もなんか考察力があり、自分の居場所が有りません、なぜこんなことに…(精進してないからなんですが…)

アジア予選までには精進したい(これは今までに何回も言っています)

ちなみにチーム名はAntitledです
僕が考えたわけじゃないので由来とかは言わないんですがとても気に入っています(去年のチーム名も結構気に入っています)
ただ今日チーム名で検索してみたら某有名アイドルグループのライブ名とかになったことあるっぽい、同じぐらいのセンスということで…

と思ってたんですが、ちゃんと調べてみると普通にライブ名はuntitledで、単に英語に弱い方々がスペルミスをしてただけっぽい気がしている
なんやねん

模擬国内予選

とりあえずついでに模擬国内予選も書きます

確か5完ぐらいでした
全然覚えてないのでこれぐらいしか書けません

ただ模擬国内予選は結構僕が活躍できてたような気がする

国内予選前の夢

国内予選の数日前に予選に出る夢を見ました

すごい分担をしていて、なぜか参加者が全体的に強くて異常ペースでACされていっていた
うちのチームも強いんですが、僕が担当の問題を読むだけ読んで通したつもりになって最終問題の考察に移ってしまい本来よりも1完少なくなってギリギリ予選落ちしそうだった

この夢のおかげでチーム内で報告しまくろうという意志が生まれました、実行はそこまでしなかった気がするな…

当日

3時ぐらいに就寝
午前中にプログラミングの授業があるので頑張って起きて課題を解いて一瞬で睡眠した
なんとか12時半に予定通り起きれたけど実は危なかったかもしれない

リハーサルをしなきゃということで、時間を合わせようとしたんですが厳しそうということで各自でやることに

前日にTwitterでASCII Expressionが話題になっていて、こんなの人間が解く問題じゃないだろとか言ってたんですが、暇になったので解くことにした
時間も測ったところ、30分ぐらいで大体できて天才かもしれないな…となってたんですがvectorでポインタを管理してそれを参照してたせいでバグったり、それを修正したらすべてが破綻したりと苦しんでいたら2時間かかってしまった

12時半に起きて昼ごはんを食べてASCII Expressionに2時間かけてることから簡単にわかるんですが、リハーサルやってません
チームメイトに詰められたらどうしよう…とビクビクしてたけど詰められることはなかった、ありがとう…

その後は少しダラダラしていて、16時ぐらいになるとお腹が空いてきたのでコンビニでチョコやホットスナックを買ってくることにした
家を出たのが16時15分ぐらいで、家のすぐ近くにあるから大丈夫だろ！とか思ってたらQUIC PAYがなぜか使えなくて手こずったりしたおかげで家についたのが16時28分ぐらい
そして通話に29分に入って急いで準備をした

なんとか30分にはコーディングできる状態になってたのでセーフということにしてくれませんか

問題

ここで突然ですがウミガメのスープです

ウミガメのスープ「男は焦りながら電話をして、通じないことに安心した、なぜ？」

— 迷路 (@pazzle1230) 2020年11月6日

考えてみてください

解答

30分に間に合ったので意気揚々とコンテストページでリロードするとチーム情報がありませんみたいなことが言われ、問題を見ることができなかった

流石に全チームこうなってるやろｗと思いつつ、自分たちのチームだけだったら流石にハンデがやばすぎるのに加え大した措置も取られないだろうということで焦り始める

コンテストページに入れないので連絡先わからないが？？？と言ってるとチームメイトがログインページにContact Infoというのがあるのを見つけるが情報が何も見えない

そこで国内予選の情報のメールを見ると緊急時はこの電話番号に電話してくださいみたいなのが見つかるので、チームメイトで誰が電話するのか押し付けあってると自分が電話することに

なけなしの社会性と勇気を振り絞って電話を掛けると「現在電波の届かないところにあるか、通話中のためつながりません」というメッセージが流れる

おかげで他のチームも同様の現象が起こっていて電話が殺到しているのだろうとわかり安心した

---

ところでどうやってコンテストの再開のアナウンスとかされるんだ？と思いながら危うく食べる時間が無くなりそうだったコンビニで買ったチキンを食べ始めるとコンテストページがプラクティスの状態になる
ワクワクか～？と思いながらもぐもぐしていると本番が急に始まり、食べてる途中でチキンを投げ出して自分の担当であるB問題を実装した

A問題とC問題は他のチームメイトが担当で、A問題はすぐ通ったもののC問題が難しかった

とりあえず愚直が書かれていて、パソコンのスペックが不安ということで僕の手元でも実行して早い方が提出みたいになった
殆ど変わらないんだけど一応こっちが早かったのでそのまま提出AC、犯罪をしてしまいました…
貢献した気分になれるので精神的にちょっとうれしいという気持ち

DをみてASCII Expressionを解いたばっかりの僕に簡単な構文解析を出されても余裕なんですよね～と調子に乗っていると構文解析部分が全然本質ではなく、解法がわからなくてつらい気持ちになった

Eも読んで、なんかいい感じにDPすればいいんだろうけどどうすれば…となる
最初Eが木に見えていて、そのせいで(？)木DPの拡張→グリッド上のDPを無理やり合わせるみたいな方針になってしまって大反省
最大独立集合的問題だから軽いDPでは解けなさそうだと気付くべきだった

そのDP正当性わかってます？と言われながらもとりあえず実装してあわせればええやろ笑と言って結局コンテスト終了まで囚われてたのも最悪だった
チームメイトの意見はちゃんと聞こうな…

気づいたら一人のチームメイトがF解けたと思いますと言って実装に向かった、しばらくすると通っていて、チームメイトの強さを実感してしまった

更にしばらくするともう一人のチームメイトがDの解法を思いつき、天才じゃん…となっていた
理解した気持ちになったのでサイレントトイレに行って帰ってくると実装方針を話してたので、そこまでの話を余りよく聞いてなかった(トイレに行ってたので)んだけどこのままだと自分のやったことがなくなるという恐怖心から実装担当を奪い取った

無言でトイレに行って戻ってきて文脈あまり理解せず奪い取るの、最悪じゃないか？

別にそこまで実装が早い気もせず、むしろちょっとバグらせたので微妙に時間がかかった
まあペナルティなしで通せたから大丈夫ということで…

あとはEをごにょごにょ無駄な努力をするだけでコンテスト終了

感想

とりあえず実装も大事なんだけど、ちゃんと考察しないのは駄目だった

なんかチームメイトが強すぎるので精進を流石にしていきたい

国内予選10位ということで去年の半分になっていてすごい嬉しいんだけど、自分の力がゼロなので悲しくなってしまった

多分この悲しさが今の忙しさを乗り越えたときに残ってたらちゃんと精進をします

Suffix Automatonでもやもやした部分をなんか書いただけ

Suffix Automaton

Suffix Automatonを学ぼうとしてたらよくわからない部分があったので適当に書きます
https://cp-algorithms.com/string/suffix-automaton.html を見たのでだいたいそこを読めばいいと思います
これ書きながら読み直したら全部ちゃんと書いてました(ア)

既にわかっているひとは何が言いたいかわかるかも、まあわかんないよね、ぐらいの気持ちで書いています
僕は自分の知識を共有して周りを強くしようという意志が殆どなく、そもそも誰かに読んでもらう気持ちで書いてないので(ア)
ですます調とかゴッチャゴチャなのも何も気にしていないからです

一度このデータ消えたので適当になりました
消えるまでは小学生が読んでもわかるとてもわかりやすい文章でできた記事だったのに...

Suffix Automatonってなに？

文字列のsuffixを受理するほにゃららオートマトン、受理状態を気にしなければ全部分文字列に対応する状態がある
それぞれの状態(頂点)からは次の文字に応じた状態への遷移があって、なかった場合は今見てる文字列の先頭を削るsuffix linkをたどる
とりあえず、上のURLでも導入されてるendposを導入します
として、一応 みたいなのも

例

S = "abcabcab"
endpos("abcabcab") = endpos("bcabcab") = endpos("cabcab") = {7}
endpos("abcab") = endpos("bcab") = endpos("cab") = {4, 7}
endpos("ab") = endpos("b") = {1, 4, 7}

endpos("abcabc") = endpos("bcabc") = endpos("cabc") = {5}
endpos("abc") = endpos("bc") = endpos("c") = {2, 5}

これらの例で、どういうものかは分かると思います(適当)
また、定義とか、この例を見ると がわかります
ある文字列T'が現れる時、そのsuffixは必ずそこに現れるのでまず右が成り立ちます
逆に、出現位置の終端が等しいとすると後ろの方の文字が等しいことがわかり、包含関係にあるときサイズが小さい方が長いこともわかります(長い文字列のほうが短い文字列より出てきにくいからね)
どちらかがどちらかのsuffixであるとき、endposは必ず包含関係になることは少し考えると多分わかります

ここで、Suffix Automatonの状態はendposが等しい部分文字列の集合になっています suffix linkは自分のsuffixで最も長いものにつけますが、先頭一文字削ったやつとかは同じ状態に入っていることもあるので 異なる状態に入る中で最も長いものにつけます
ちなみに、同じ状態に入っている文字列集合は一番長い文字列 T と一番短い文字列を T'見つけた時、Suf(T) の中で T' よりも長い文字列全てになります。
例を見るとわかると思います

Suffix Automaton の構築

構築部分で、いくつかなんかよくわからないね(考えてないので)みたいなところがありました
まあCorrectnessってところをちゃんと読みましょうなんですけど
一応次に構築方法の手順を書きます(URLのやつをわかりにくくしただけ)
まず各状態は文字ごとの遷移先(next[c])、suffix link(link)、長さ(len)を持ちます
構築方法としては、文字列の先頭から1文字ずつ追加していく感じなので現時点での文字列全体の状態(last)も持ちます
オートマトンなので、最初は初期状態(頂点0)だけを用意しておき、初期状態のlinkは-1にしておくといいらしいです

1. curとして状態を追加し、cur.len = last.len + 1とします。また、追加する文字をcとしておきます(残りの決める必要があるものはlink)
2. p = lastとして、次の処理を繰り返します
   1. p == -1であるとき、またはp.next[c]が存在するなら繰り返しを抜けます
   2. p.next[c] = curとします
   3. p = p.linkとします
3. ここで、p == -1であれば cur.link = 0として終了します
4. q = p.next[c]とします
5. もしp.len + 1 == q.lenであればcur.link = qとして終了します
6. cloneとしてqをコピーした後、clone.len = p.len+1、cur.link = q.link = cloneとします
7. pからはじめて、p.next[c] == qである間はp.next[c] = cloneとしてlinkをたどることを繰り返します
8. 最後にlast = curとして終了です

ここで、次のいくつかがよくわからなくなりました(頭がないので)

1. なんでp.next[c] = curとしながらlinkをさかのぼっていっていいの？
2. なんでp.len + 1 == q.lenだったら放置して終了して大丈夫なの？
3. なんでcloneが必要なの？
4. なんでcloneにnextを張り替えるのはp.next[c] == qである間だけでいいの？それともある場所以降は全部qなの？

とりあえずこれらを僕が解消しようと試みるだけのアです

一応、S = "abcbcc"に対してSuffix Automatonを構築する図を貼っておきます。
suffix linkを図示するの忘れてたけど見にくくなってしまうからということで...
そもそもそこまで説明に使わないし..

1日目

2日目

3日目

4日目

5日目

6日目

オートマトンの成長観察日記です。
頂点の数字はそこに属する文字列の中で最長のものの長さを示しています。

なんでp.next[c] = curとながらlinkをさかのぼっていっていいの？

現時点の文字列がSで、そこにcを付け足してS+cのSuffix Automatonを作ろうとしていると考えます
すると、Suf(S)は初期状態になるまでlinkをたどって状態に属する部分文字列を集めると出来上がる。(Suffix Linkをたどると最長のSuffixの状態に移動するので)
なのでそれらの状態からのcによる遷移をcurに送るとcurで全てのsuffixを受け持つことになる
全てのsuffixがcurにあるので、suffix linkは頂点0に当然向かう

ここで、文字列SによるSuffix Automatonは正しく構築されていることを仮定するので2つの状態に同じ文字列が属していることはない
ちなみに、後で議論するp.len + 1とq.lenの関係について、p.len + 1 < q.lenとなる遷移はここでのみ追加される

なんでp.len + 1 == q.lenだったら放置して終了して大丈夫なの？

ここでも同様にS+cの考え方をしてみます
p.len + 1 == q.lenであるということはqが文字を追加するときにできた状態か、cloneの状態である可能性があります
したがって、pのsuffixにcを追加した文字列の状態は全てqを追加した際に解決されているのでこれ以上さかのぼる必要はありません
また、S+cのsuffixのうちpより長いものはcurに属しているのでcurからのsuffix linkはqで大丈夫です

なんでcloneが必要なの？

cloneを追加するときはp.len + 1 < q.lenであるが、これはqに属する文字列のうちp.len + 1以下のものだけがほしいのにそれより長いものも取ってしまっていることを意味している
ここで、p.len + 1 < |T| <= q.lenだけqに残し、cloneに(qに属するやつで最小の長さ) <= |T| <= p.len + 1となるものが属するようにしたい
ひとまず、qとcloneの関係だけ考えるとcloneはqのsuffixなので、suffix linkはqからcloneに向けてつなげる
cloneのsuffix linkについてはqからもともとつながっていた状態がcloneのより短いものではもっとも長いのでcloneからつなげる

結論としては、qだけだとpにcを追加するときにはqよりもたくさん登場してる状態になっているからcloneで分ける必要がある
最初追加したときには、pからのcによる遷移はqのsuffixに完全に属しているのでのでendposがいい感じになっている

例えば上の観察日記の3日目と4日目を比べると、3日目で主鎖の2と書かれているところには"ab"と"b"が属していてどちらもendpos = {1}である
ただ、4日目になると"b"のendpos = {1, 3}となり"ab"よりも多く登場するので分けなきゃいけない気持ちになる
そういうことです、多分(微妙になんかモヤモヤがあるけど多分無視できるレベルなので無視)

なんでcloneにnextを張り替えるのはp.next[c] == qである間だけでいいの？それともある場所以降は全部qなの？

ある場所以降は全部qなの？ →　そんなことはないです、多分
途中からsuffixが一致するようなものを考えるとなんか全部一緒にならないものもあると思うので(曖昧)

ただ、そうでなくても問題ないことを示せばいいので、お気持ちを書きます
p.next[c] == qであるものが集まることでqに属する文字列ができているので、これを集めてp.len + 1以下の長さのものがcloneに属し、p.len + 1よりも大きいものはqに属したままになることがほしい状態です
ここで、qに属するものより短い文字列は別の状態に属していて、それらはp.len + 1よりも小さいので今の所同時に現れているので変更する必要がありません
これで疑問は解決していますが、ほしい状態にcloneとqがなっているかを一応解決しておきます
pからp.linkをたどって得られるsuffixはp.lenよりも短いものだけなのでcloneにはp.len + 1以下でもともとqに属していたものしか属しません
他の遷移はいじっていないのでqには残りのp.len + 1よりも長いものが属したままになっています

よって大丈夫そうであることがわかります

結論

ということでSuffix Automatonの構築でモヤモヤした部分のモヤモヤを少し解消した気持ちになりました
一応これぐらいで最低限は十分かという気持ちに少しなっています

実際にどう使うか知りたいですね、僕はまだわかりません(？)
Suffix ArrayのO(N)構築に比べ実装が圧倒的に軽いのでそこは強そうだけど、使うときに頭が必要そうで怖い
Suffix Arrayは適当にLCPとかこねてればある程度は大丈夫なイメージがあるので...

Runの列挙 (Main-Lorentz algorithm)

Main-Lorentz　Algorithm

概要

文字列のrunをで列挙することができるアルゴリズム
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つあるけどまあ自明なのではい

アルゴリズムもあるっぽいけど実際に使うならで十分だから、いいよね
があれば実用上大体十分な文字列アルゴリズムって、あるじゃん(例: 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の総数はそれぞれの分割統治の深さについて個、深さが 個(修正しました 11/28 17:36)なので全部で個に収まることがわかる
なんかいい感じの論文を読むと普通に個であることが多分わかる(まあそうじゃないとアルゴリズム、ないよね)

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

ところで、それぞれの深さについてで跨ぐようなやつを求めるのはどうやるの？という気持ちになるのでそれを説明する
その要になるのが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を適用する('#'は実際には必要ない)
そして後ろ側につけたs の s[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もその後の計算もなので、分割統治のある深さについて全部足しあわせてもで収まるので大丈夫

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

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

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

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

ICPC Asia Taipei-Hsinchu Site Programming Contest参加記

ICPC Asia Taipei-Hsinchu Site Programming Contest 参加記

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

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

1日目

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

pic.twitter.com/MYIJojsQdp

— 迷路 (@pazzle1230) 2019年11月22日

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

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

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

まあまあだね pic.twitter.com/LxSNTUB2Ch

— 迷路 (@pazzle1230) 2019年11月22日

2日目

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

この環境、やばくない？ pic.twitter.com/DQ9OH5KVpU

— 迷路 (@pazzle1230) 2019年11月23日

わくわく

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

プラクティス

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

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

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

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

でーん pic.twitter.com/2Ci51RyWIR

— 迷路 (@pazzle1230) 2019年11月23日

タピオカ、喉越しさいこ〜〜！！！ pic.twitter.com/XTiTTOOXBu

— 迷路 (@pazzle1230) 2019年11月23日

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

精度かな～やっぱ！ｗと言いながら#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に上げるなどをした

やりました！！！！ pic.twitter.com/1kw6RNaWbH

— 迷路 (@pazzle1230) 2019年11月24日

ところでこういう上位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なので)

なにがあったっけ

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

これがこっからどうなるか、楽しみですね！！！ pic.twitter.com/7tskRqZthC

— 迷路 (@pazzle1230) 2019年11月16日

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

二日目

体調大回復時代になった

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

それでは… pic.twitter.com/oOLQzLdWJu

— 迷路 (@pazzle1230) 2019年11月16日

日本大通り駅で待ち合わせだったので迷いながら向かうとなんか駅がなかったので迷ってしまった
まあ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ほしいけど
最後に全提出しちゃおっかな～！ｗとか思ってたけど流石にやったら恥ずかしすぎたのでやらなくてよかった

懇親会

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

最近ワイヤレスイヤホンを買おうとしてた僕、歓喜 pic.twitter.com/d0qJFkMNBd

— 迷路 (@pazzle1230) 2019年11月17日

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

ご飯を犠牲にして手に入れた pic.twitter.com/HjAHvcP58N

— 迷路 (@pazzle1230) 2019年11月17日

流石にお腹が空いてるのでタピオカと企業賞で埋まった手で皿を持ち見渡すとそこにはほぼ何も残っていなかった
競プロ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_ptとr_ptを同じ点で始めるので最初はここで交差したことになってしまうので、適当に弾く。僕は線分の交点が一致していれば気にしないとしたが、l_ptとr_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にも適当に改変したりしなかったりして持っていきたいと思います！！！！