ICPC2023 Asia Yokohama Regional参加記

yumaくん、なにわづさんとチーム「Red Phobia」で参加して、8完12位でした。

Day 1

ライブラリはhttps://tko919.github.io/library/を印刷して持っていきました。

リハーサルでエディタや印刷の確認をした後にFFTの写経の練習をしていました。
しかしUS配列に一度も触ったことがなく記号のタイプミスを多発してしまったので、来年までの課題ですね…

KUB1sharpやコーチのsuibakaさんと一緒に中華街に行きましたが、入って3秒ではぐれてしまい電話で救出してもらいました。

Day 2

コンテスト

なにわづさんにセッティングをしてもらったあと僕がAを書いて通しました。
yumaくんのBが若干燃えてるっぽく、なにわづさんが援護に回っているうちに後半の問題に目を通します。
先になにわづさんのFが通り、PCを奪って僕がDを書きます。BNFを誤読して1ペナを食らいながらAC。
程なくしてBの修正が終わりACします。自分も嘘解法のhackに協力した方が良かったかもしれません…

僕が自信を持ってEに枝刈りO(M2^N)を投げると宣言し一発で通ります。このときは驚きの方が大きかったです。
ここでGのDP遷移を眺めていると状態数が少ないことに気付き、floor,ceil周りでバグらせながらもACします。畳み込みをずっと疑ってしまい出遅れてしまいました。

2人がKを解けたと主張したのでPCを渡し、インタラクティブ用のbashファイルの使い方を指南して無事に通ります。
Iの図を書きながら考えていると、OUPC2020-Iに類題があることを思い出します。しかし、無証明でサンプルだけ合う主張を書いてしまい余分に3ペナを貰ってしまいます。

しばらく手詰まりますが、Hでyumaくんが「これ燃やす埋めるじゃない？」と呟きフローの確信を得ます。しかしmincutへの帰着をずっとLuzhiled's memoに頼っていたためグラフの構成が上手くいきません。
すると、なにわづさんからIのhackケースをもらい修正に成功します。結局Hのサンプルは通らずコンテストが終了しました。

懇親会

Celeste勢の人々が集まっていて、早くmodをやれとの厳しい指摘(？)が入りました。キーボードが届いたら再開しようかな。
Library Checkerでお世話になっているyosupoさんはずっと会ってみたい方だったので、お話できて嬉しかったです。

感想

嘘解法の修正などチーム戦らしいムーブが出来た一方、初動のスピードや地力不足に課題が残る結果になりました。
Playoffではもっと個の力をつけて挑みたいです。まずはratedに出続けるところから…

宣伝

紹介スライドに載せた曲と、もう一つ迷った曲を貼っておきます。
open.spotify.com
open.spotify.com

ICPC2021 国内予選 参加記

ヒトデマンさん、なにわづさんと一緒にチーム "KUSunoki" で参加しました

1時間前に空き教室に入って準備　初動どうしようかなーとか話し合ってた
模擬国内では黄色チーム×2に倒されたのでどっちかは抜かないとなー、と思ってたら橙×3のチームが直前で発覚する　おわりです

本番の動き

初めにヒトデマンさんがA、僕となにわづさんでBを見る
なにわづさんに連結判定やるだけと言われたのでUFを貼ってAC
Cが構文解析と聞いて見るが読解が難しい　読み終わっても解法が思いつかず焦る
少ししてから2人の書いたAのシミュが通るが、3人ともCDで詰まる
順位表からCが沼だと分かったのでDを見ると、2分くらいで解法が思い浮かんだのでそのまま実装して通る
そのままEを読んで、嘘解法を生んでしまいデバッグに苦しむ　自前のテストケースでバグが取れるも勿論WA
仕方ないのでCに戻るとRerooting解が生えていたが、実装に苦戦している様子　確かに抽象化が使えないので悩む...
ここで構文木が二分木っぽいことから、DFSベースのメモ化DPを思いつく　Euler tourを一部バグらせるもACが出て大喜びする
ここで全体21位とかだったのでなんとかEも通したいねという話になるが、30分前になって教室を追い出される（カス）
広場のベンチで震えながらEを書き直すもここでタイムアップ

結果・感想

UTが上位に大量発生しており全体23位で通過しました　いえーい
院生軍団にリベンジするという目標も達成できたのでかなり満足度は高いですが、Eで嘘に嵌り結局間に合わなかったのは反省点です（もし2チームのどちらかが通してたら落ちていたので）
帰りに夕飯を奢ってもらいました（京大ICPCの民俗文化？）

来年はちゃんと8時まで利用できる部屋を確保して参加します。

入試体験記

先日受験がようやく終了したので、振り返りをここに残しておきたいと思います

特色入試

準備を始めたのはちょうどJOIの柿蝉が終わったくらい　必要な書類の作成を適宜進めていった
学びの報告書については先輩から助言をいただきながら、いい感じの実績や興味のある分野についての話をつらつら書いていった感じ　これは他の人の体験記も参考にするといいかも
過去問だけではなんか心許なかったので、10月の始めに杉浦解析をAmazonでポチり雑に読み進める

そんなこんなで書類審査は無事通り11月の中旬に数学試験を受けた
京都の晩秋はとても冷え込んでおり、集合場所で震えながら † Fleet † を投稿　来年とか受ける人は、面接以外は私服の方がいいと思います
枕詞の「解答は日本語で記述してください」でツボってしまった

試験

まずは全体をばーっと眺める
[1]簡単め　「全点対の距離が同じ」から条件が絞れる
[2](1)は取らないとダメ　(2)も市松模様典型でいけそう
[3]謎　発想一発ゲーの香りがする
[4](3)(4)で結構差がつきそう
というか一問も解析が無いんだけど　3000円を貢いだ意味は一体....

とりあえず[1]の解答を書き始めるが、何を思ったのか記述の途中で「各頂点対{v_i,v_j}は全て等距離だから、{v_i}が作り得る立体は正四面体だけ！ｗ」という嘘考察をする





IQ3か？？？？？？？？？？？？？

v_iは球面上にあるってだけなんだから当然平面図形(正三角形)も取ります　なんで特色受けたんですか？？？？？？？？？？

その後も[3]で1時間沼って結局撤退するという最悪ムーブをかましてしまう　僕は天才以外お断りパズルコンテストをやりに来たんじゃないんだが

[4]は計算をバグらせながらも(3)まで書き進めていると、突然何か違和感を覚える　最終問題がこんな簡単なわけ無くないか...?
問題文を読み返します
「{a_i} を 0以上の整数からなる数列」


。。。



「0以上の整数」



。。。



はい　えー、此方a_iを実数に誤読しておりました　時計を見ると12:57　いい天気ですね


試験がある意味終わってピロティで佇んでいると、そこにはネッコアラと だまさんの姿が
ネッコアラに調子を尋ねてみると「手が疲れました」と返ってきた　許せねえ
面接のこととか雑談を聞きながら現地解散した　帰路に就く途中で学食を食べてこなかったことをちょっと後悔する
実際のところ自分はまだ[1]の致命的ミスに気づいてなかったので、半々くらいで通るんじゃないかなーとか楽観視していた



殺伐としたTLに突如不合格の文字が！



　　＿人人 人人＿
　　＞ 突然の死 ＜
　　￣Y^Y^Y^Y￣　



面接の予定がなくなったので、深夜までアマプラでかぐや様の続きを観た　面白い

共通テスト

12月の模試で7割切りという驚異的な数字を叩き出し、さすがに焦り始める
面談で「とにかく地理が弱すぎる」と言われたので、センター過去問10年分くらいを印刷してもらった
しかし、当方は怠惰の権化なので、YouTubeで超新塾のネタを見ながら解くという荒業をやっていた
また、文系科目の過去問も特に手を付けることはなく本番を迎えてしまった結果...


言うまでもない、惨憺たるものだった　クラスで前の席のやつをチラ見すると普通に750とか取ってるので完全に終わったと思った

二次試験

共通利用の判定はもちろんD,Eのオンパレードだったので鞍替えしようとするが、FF人(FFんちゅ)の皆さまに励ましていただき何とか踏みとどまった　あの時はありがとうございました

だが、やはり私は 怠惰の権化 なので、冠模試を受けることもなく、しょうもないツイートをしてはふぁぼりつを稼ぐツイ廃の日々を過ごしていた


英語と国語が絶望的に出来なかったので25ヵ年を借り、ディスコースマーカーや重要単語をTwitterの下書きにした　これが高3Twitter耐久プレイヤーの裏技や
まあ理系で稼げば問題ないやろ！ｗ　くらいのモチベーションで本番に向かう

1日目

古典の単語帳を流し見しながら京大に到着　タテカンや例の像を写真に収め会場 in

国語

先に[3]の記述を適当に埋めて、[1][2]にじっくり時間を割く算段
下書き欄が無限にあるのでありがたく使わせてもらい10分前に全部書き終わる
誤字脱字を見直して終わり　まあ平均あったら十分かな


昼休みも無限にあるのでTwitter開いたり昼寝して時間を潰す


ふと周りを見渡すと参考書開いてる人しか見当たらない　こわすぎ

数学

問題を開くと自明が3問くらいある　終わった......
[5](2)のオイラー線が見えず詰まるが30分前くらいに自称全完
計算ミスとかも特に見当たらなかったので、シャーペンを置く音で周りの受験生を牽制する


一日目が終わってからTwitterを開くとどうやら[6](2)が難しかったらしい
そんなに厳しかったか...?　と思い再度問題文を読むと誤読していることが発覚する
お前は特色から何を学んだんや

2日目

魚民なので、mellow → ストラクチャー → 朝の歌を聴きながら京阪電車で移動

英語

前から順に解くことにした　[1]はそこまで苦労するパートはなかったのでセーフ
だが[2]の内容理解を怠ってしまいどん詰まりする　とりあえず(1)(2)は逐語訳で耐え
(3)の文法をパースしようとする　出来ません
副詞節を括ってもう一度試す　出来ません
SVの組を変えてみる　出来ません
さすがにキレたので単語だけから適当に推理して書く　もちろん文脈フル無視しているので自分でも意味が分からない(最悪)
[3]を適宜埋めていく　「円熟味が増す」に詰まり、近そうな単語を検索する

そういえばmellowって「円熟した」って意味じゃね？(正解)　みんなもサカナクション、聴こう
[3]の残りと[4]を雑に埋めたらちょうど試験が終わりそうになっていた


また昼休みがクソ長いのでArcaeaを立ち上げるが、当然滑り止めは持ってきてないので親指プレイ　調子に乗ってFracture Ray[FTR]をやったらハード落ちした
物化で稼がないとお話にならないので真剣モードになる

物理

[1]はやるだけなので完答した...　つもりだったが、漸化式自体をミスってて後半が全部落ちてる　真剣モード #とは
[2][3]も後半で失速し、捨てた問題も多かったのでかなり失敗気味

化学

[1]はそこまで詰まるポイントはなかった
問題は[2]で、全く誘導に乗れずかなり時間を浪費してしまった　せめて前半の答えだけでも書いておくべきだったと後悔
[3][4]の有機はご丁寧な説明が記載されていたので解きやすかった　が、またしても誤読し途中から点数が消し飛んでいる　そんなんだから春合宿とか行けないんだよな


帰りに、弊校の近くから移転したラーメン屋に立ち寄った　僕はこのラーメンと再会するためにKU志望にしたと言っても、過言ではある

合格発表前

つ　ら　い
めちゃくちゃつらい　噂には聞いてたけど想像以上につらい
精神的に厳しすぎて逆にどうでも良くなってきた
特に物化でバチバチにやらかしてしまったので、何とか数学でボーダー耐えてくれーーーという気持ちだった

ついに発表の瞬間、震えた手でページにアクセス





........できない　サーバーが重すぎる(それはそう)

F5攻撃でなんとかこじ開け、Ctrl+Fで自分の受験番号を入れる(せっかち)











あった。

信じられなかった　嬉しいより先に「なんで？！」っていう驚きの方がやってきた
こんな興奮したのは、マリオメーカー初代でメニークルシミマス（鬼畜コース）を15時間でクリアした時以来だと思う

かくして、僕の大学受験が幕を閉じたわけである

総括

誤読しすぎだろ

開示は5月らしいので詳細は分からないが、数学で[5](2)のオイラー線に気づいてなかったら、古典で仮定・確定条件の区別をミスっていたら、2日目の朝にサカナクションを聴いていなかったら、僕は多分落ちていたかもしれない
そういった意味でも入試はめちゃくちゃ恐ろしい世界だし、一度きりかもしれない受験勉強でもう少し努力すればよかったなと悔やんでいる
だから今後、次期怠惰の権化を生まないためにも、僕を反面教師にして精進してほしいなと思っています　実際、僕はこのポエムを錬成するのに一週間以上かかっています(申し訳ありませんでした)


最後に一つ、
問題文は998244353回読もう


以上です　ありがとうございました



（追記）
開示結果来ました　介錯してくれる人を募集してます

Convex Layers

はじめに

この記事は https://codeforces.com/blog/entry/75929 の雑な意訳です
詳細な証明が欲しい方はそちらを見ることをお勧めします

Convex Layers とは

相異なる点の集合が与えられ、「凸包を取っては含まれる集合を削除すること」を繰り返すとき、各点が何回目の操作で削除されるかを求める問題
(参考:https://en.wikipedia.org/wiki/Convex_layers )

f:id:tk0_math:20210120202916p:plain

機能

一点削除:O( \log ^2 N)
左側凸包:O(k \log ^2 N) (k : 凸包に用いられる点の個数)

このデータ構造を左側と右側で2つ持って、各階層で管理すれば計算量O(N \log ^2 N)でConvex Layersが解けます

左側凸包

次の分割統治を考えることで高速に構築することができます

  1. y座標でソートして、集合を半分に分割する
  2. 2つの集合に対して再帰的に凸包を作る
  3. 凸包同士をつなげる「橋」を見つける (これは二分探索で O( \log N)で可能)
  4. 橋に被覆された凸包を無視する

凸包を動的に管理するために、分割統治をSegment Treeの形に置き換えます
各ノードには点集合の範囲と、子同士の凸包をつなぐ橋の端点のみを保持することにします

橋の見つけ方

始めに、pを集合の下半分、qを上半分を表すノードに初期化します
p,qどちらもセグ木の「葉」に到達するまで下の探索を繰り返します

pの橋を\{ a,b \}、qの橋を\{ c,d \}として、以下の6通りに場合分けします
(i) a \neq b かつ a,b,cが反時計回りに位置する
pを、pの上半分の子に更新する

(ii) c \neq d かつ b,c,dが反時計回りに位置する
qを、qの下半分の子に更新する

(iii) a = b
qを、qの上半分の子に更新する

(iv) c = d
pを、pの下半分の子に更新する

(v) ab と cd の交点が上半分に属する
qを、qの下半分の子に更新する

(vi) ab と cd の交点が下半分に属する
pを、pの上半分の子に更新する

f:id:tk0_math:20210120212848p:plain

それぞれのケースについて、使わない集合が橋に用いられないことは容易に確認できます
1回の更新でp,qのいずれかが葉に近づくので、橋の探索はO(\log N)で終わります

各ノードについて橋の端点が分かれば、凸包は先ほどの分割統治と同様の再帰を行うことで、O(k \log ^2 N)が達成できます

一点削除

実はそこまで難しくなく、対応するノードを存在しなかったことにして、根まで遡りながらノードを更新していけばよいです

実装例

https://judge.yosupo.jp/submission/36284

なぜJMO-yoは閲覧・入力以外のPC使用が厳禁なのか

※注意　この記事は競技数学のプログラミング使用を推奨するものではありません　予めご了承ください

今回は競プロの威力を体感するために、JMO2021-yoをC++パンチしていきたいと思います
問題はここ:https://www.imojp.org/archive/mo2021/jmo2021/problems/jmo31yq.html

1.

さすがにやるだけです

int main(){
   int res=0;
   rep(n,1,90){
      int m=90-n;
      if(gcd(n,m)==1)chmax(res,n*m);
   }
   cout<<res<<'\n'; // 2021
   return 0;
}

2.

幾何ライブラリを使って、1辺の長さをにぶたんします
参考記事:https://tk0-math.hatenablog.com/entry/2020/12/27/180738

int main(){
   vector<P> vs(10);
   double lb=0,rb=1;
   rep(_,0,60){
      double mid=(lb+rb)/2.;
      vs[0]=P(mid,0);
      rep(i,0,9)vs[i+1]=rot(vs[i],2*M_PI/10.);
      double S=Area(vs);
      if(S>1.)rb=mid;
      else lb=mid;
   }
   double res=Area({vs[0],vs[1],vs[2]});
   res+=Area({vs[2],vs[3],vs[4],vs[7]});
   printf("%.12f\n",res); // 0.400000000000 -> 2/5
   return 0;
}

3.

ABではなくDPの長さを探索します　tangentとIntersectionを駆使すると
Aが求められるのでどちらの象限に属すかで判定問題を解けばよいです

int main(){
   double lb=0,rb=20;
   P b(-7,0),d(2,0),c(7,0),a,f,e;
   rep(_,0,60){
      double mid=(lb+rb)/2.;
      P p(2,mid);
      Circle C1(p,5),C2(p,2);
      auto vs=tangent(b,C1);
      f=vs[0];
      if(f.X>vs[1].X)f=vs[1];
      vs=tangent(c,C2);
      e=vs[0];
      if(e.X<vs[1].X)e=vs[1];
      a=Intersection(Line(b,f),Line(c,e));
      if(a.X<0)lb=mid;
      else rb=mid;
   }
   double res=abs(a-b);
   printf("%.12f\n",res);
   // 10.583005244258 -> 4sqrt(7)
   return 0;
}

4.

答えが指数オーダーでつらいので、小さい数で実験してエスパーする方針にします
今回は運よくヒットしましたが、もし当たらなければ「差分を取る」「初項を削る」なども有効だと思います

void dodo(double& a,double& b,double& c){
   double na=(b+c)/2.;
   double nb=(a+c)/2.;
   double nc=(a+b)/2.;
   swap(a,na);
   swap(b,nb);
   swap(c,nc);
}

int main(){
   rep(n,1,8){
      int res=inf;
      rep(a,1,201)rep(b,1,201)rep(c,1,201){
         if(a==b or b==c or c==a)continue;
         if(a+b+c>res)continue;
         double x=a,y=b,z=c;
         rep(_,0,n)dodo(x,y,z);
         int ex=round(x),ey=round(y),ez=round(z);
         if(abs(x-ex)<eps and abs(y-ey)<eps and abs(z-ez)<eps){
            chmin(res,a+b+c);
         }
      }
      cout<<n<<':'<<res<<'\n';
      //9,15,27,51,99,...
      //https://oeis.org/A060013 -> 3*2^n+3
   }
   return 0;
}

5.

あり得る状態数は高々2^16なのでbitDPをすることができます
実装は死ぬほど長くなったので省略(outputはちゃんと379になりました)　多分頭を使った方が早いです

6.

適当にN<=10^7まで探索すると新たなf(N)が出現するNはごく少ないことが分かります
1足してOEISに投げると https://oeis.org/A002110 であることがわかり、後は10^10の制約に合わせればよいです

int main(){
   set<int> fs;
   rep(n,1,10000001){
      for(int m=1;;m++){
         if(gcd(n,m)==1 and gcd(n+1,m+1)==1){
            if(!fs.count(m))cout<<n<<'\n';
            //1,2,5,29,209,...
            fs.insert(m);
            break;
         }
      }
   }
   return 0;
}

7.

実は垂心は初めて実装しました　各角度のtanと頂点座標で出来るんですねーーー

int main(){
   P b(-5,0),p(0,0),q,c,a;
   double lb=0,rb=10;
   rep(_,0,60){
      double mid=(lb+rb)/2.;
      q=P(mid,0);
      c=P(mid+6,0);
      Circle C1(b,10),C2(c,11);
      auto as=Intersection(C1,C2);
      a=as[0];
      P h1=orthocenter(a,b,q),h2=orthocenter(a,p,c);
      if(h1.Y<h2.Y)rb=mid;
      else lb=mid;
   }
   printf("%.12f\n",lb+11);
   // 15.198684153571 -> sqrt(231)
   return 0;
}

8.

https://hos-lyric.hatenablog.com/entry/2018/12/28/025852
これがかなりヒントになります
累乗の部分はおおよそ周期 \phi(m)に入っています　 \log_2(m) 以下の整数が例外ですが、これは高々5程度でテトレーションに勝てるわけがないので無視してOKです

using P=pair<int,int>; //a*19^b
P rec(int d,int m,int n){ //a_1^a_2^...^a_n mod m == d
   if(m==1){
      return {1,n};    
   }
   if(n==16){
      auto [td,tm]=crt({d,1},{m,17});
      d=td; m=tm;
   }
   P res={0,20};
   int pre=5,nm=phi(m);
   rep(a,2,21)for(int x=pre;x<pre+nm;x++){
      if(mpow(a,x,m)==d%m){
         P add=rec(x,nm,n-1);
         if(add.first==0)continue;
         if(res.second==20){
            res=add;
            continue;
         }
         if(abs(res.second-add.second)>5)assert(0);
         if(res.second<add.second){
            rep(_,0,add.second-res.second)add.first*=19;
         }
         else{
            rep(_,0,res.second-add.second)res.first*=19;
            res.second=add.second;
         }
         res.first+=add.first;
      }
   }
   return res;
}

int main(){
   auto res=rec(1,17,17);
   cout<<res.first<<' '<<res.second<<'\n';
   // 2042 14
   return 0;
}

9.

愚直DFSを書いてOEISに投げると https://oeis.org/A183632 が出てくる
あとは書いてある通りにやるだけ

ll mod(ll a,ll m){return (a%m+m)%m;}
ll mpow(ll a,ll t,ll m){
   ll res=1;
   while(t){
      if(t&1)res=mod(res*a,m);
      a=mod(a*a,m); t>>=1;
   } return res;
}

int main(){
   const int n=2020;
   const int m=100;
   vector<int> a(n+10);
   a[0]=mod(2+mpow(2,n+2,m)+mpow(3,n+1,m),m);
   a[1]=mod(3*(4+mpow(2,n+2,m)+mpow(3,n,m)),m);
   a[2]=mod(50+7*mpow(2,n+2,m)+mpow(3,n+1,m),m);
   rep(i,3,n+5){
      a[i]=mod(6*a[i-1]-11*a[i-2]+6*a[i-3],m);
   }
   cout<<a[n-1]<<'\n';
   // 3
   return 0;
}

10.

幾何をC++で殴る記事はここでもまとめています（まとまってない）
https://tk0-math.hatenablog.com/entry/2020/12/27/180738?_ga=2.5473715.1249954011.1615963450-720260241.1585136235

∠BACとADの長さを固定すると図が一意に定まるので、評価関数を∠BDP,∠BPC,∠PECの各差の二乗和として山登り法をします

int main(){
   P a(0,0),b(9,0),c,d,e,p;
   auto rec=[&](auto self,double Ld,double Rd,double lb,double rb,int lvl)->void{
      if(lvl==30)return;
      double rgd=Rd-Ld,rgb=rb-lb;
      double best=inf,D,B;
      rep(i,0,501)rep(j,0,501){
         double ds=Ld+rgd*i*.002;
         double bs=lb+rgb*j*.002;
         c=P(11*cos(ds),11*sin(ds));
         d=P(bs,0);
         double acb=arg(a,c,b);
         P tmp(bs+(9-bs)*cos(acb),(9-bs)*-sin(acb));
         e=Intersection(Line(a,c),Line(d,tmp));
         if(ccw(a,e,c)!=-2)continue;
         auto ps=Intersection(Circle(d,1),Circle(e,3));
         if(ps.empty())continue;
         if(ps.size()==2 and isIntersect(Segment(a,ps[1]),Segment(d,e)))p=ps[1];
         else p=ps[0];
         double A[3]={arg(b,d,p),arg(b,p,c),arg(p,e,c)},score=0;
         rep(k,0,3)score+=(A[k]-A[(k+1)%3])*(A[k]-A[(k+1)%3]);
         if(chmin(best,score)){
            D=ds; B=bs;
         }
      }
      self(self,D-rgd*.2,D+rgd*.2,B-rgb*.2,B+rgb*.2,lvl+1);
   };
   rec(rec,0,M_PI,0,9,0);

   double res=abs(b-p)/abs(c-p);
   printf("%.12f\n",res);
   // 0.522232967868 -> sqrt(33)/11
   return 0;
}

11,12.

TODO

総括

一応7完は出来ました　モチベが上がったら後半もやります
共通テスト前なのでかなり雑です　何か誤字脱字あったら @tk0_math までどうぞ

(2021/3/19 追記)8~10を追加しました

幾何ライブラリでOMCをシバく

ごめんなさい
幾何ライブラリはここ(いろいろな記事を参照して作りました)
https://github.com/tko919/library/blob/master/math/geometry.cpp

ex1:OMC012-E

Link:http://onlinemathcontest.com/contests/omc012/tasks/omc012_e
ABを決め打ちでにぶたんし、DGの距離によって解の区間を絞ります
何言ってるか分かりづらいと思うのでコード(テンプレート等は省略)

int main(){
   P b(0,0),e(3,0),f(8,0),c(12,0);
   double lb=6,rb=100;
   rep(_,0,60){
      double mid=(lb+rb)/2.;
      P a(6,sqrt(mid*mid-6*6));
      Circle C=Circumcircle(a,e,f);
      auto ad=Intersection(C,Line(a,b));
      auto ag=Intersection(C,Line(a,c));
      P d,g;
      if(abs(ad[0]-a)<eps)d=ad[1];
      else d=ad[0];
      if(abs(ag[0]-a)<eps)g=ag[1];
      else g=ag[0];
      if(norm(d-g)>39)rb=mid;
      else lb=mid;
   }
   printf("%.12f\n",lb);
   return 0;
}

実行すると"7.855844048496"と出力されました
これをWolframAlphaに投げると...

f:id:tk0_math:20201227165145p:plain


f:id:tk0_math:20201227165208p:plain
✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌


もう一問やります

ex2:OMC013-F

Link:http://onlinemathcontest.com/contests/omc013/tasks/omc013_f
∠BCAは逆回りなことに注意して書きます

int main(){
   P d(0,0),e(1,0),c(9,0);
   double lb=4.5,rb=100;
   rep(_,0,60){
      double mid=(lb+rb)/2.;
      P b(4.5,-sqrt(mid*mid-4.5*4.5));
      Line l(b,(c-b)*P(0,1)+b);
      double theta=arg(c,e,b);
      Line ca(c,rot(b-c,-theta)+c);
      P a=Intersection(l,ca);
      double bac=arg(b,a,c),adc=arg(a,d,c);
      if(bac+adc>M_PI)rb=mid;
      else lb=mid;
   }
   printf("%.12f\n",lb);
   return 0;
}

総括

競プロでズルするのは楽しいか？
面積とかにも対応できるので、多分他の問題でも脳死で解けるはず
サジェストも出来ればコード上で実現したいけど、解の表現が複雑だと辛そうですね...(a+b*sqrt(c)/d とか)(いいアルゴリズムがあったら教えてください)

AtCoderで黄色になりました

先日、AtCoderで黄色を達成したので思い出をつらつらと書いていきます
f:id:tk0_math:20201014233237p:plain

2019年2月~4月(水色まで)

僕の場合はそこまで苦労しませんでした　ただ今時のABCはインフレが激しく、当時の自分では緑すらいけないのではないかと思います

4月~10月(水~青)

ここから半年ほど停滞します　新しい形態のABCになかなか慣れず周りの競プロerに差をつけられてしまったので精神的にも不安定な時期でした　まあこの辺りは他の皆さんの色変記事にあるように、地道な精進とコンテストの参加しかないのではないかと
僕は未だに試せていませんが、海外のコンテストで釣り合いをとるのも手だと思います(当時はシステムテスト方式が合わなくてすぐ辞めてしまいましたが...)

10月~2020年6月(青~1800↑)

Library Checkerとかもこの頃から埋め始めてみたりしたのですが、青色を達成しても伸び悩みは続き1800台で完全にグラフが横ばいになってしまいます
おそらくレートを意識しすぎていたことで競プロ自体を楽しめていなかったせいだと思うんですが、モチベも精進の頻度もすっかり落ちてしまいました

8月~10月(1800↑~黄)

そこで2カ月ほど競プロから離れることを決意します　その間は数学とか受験勉強を適当に進めてました　まあ学生の本業をこなしてたような感じです
で、8月下旬くらいに平凡な生活スタイルに飽きて、「久しぶりに競プロしたいなー」なんて思い始めるようになりました　そこから4,5回連続で黄prfを維持し、めでたく暖色に昇格できました(ARC104はコケましたが...)

これは競技系全般に言えると思うんですが、モチベーションが尽きてしまったときは下埋めとかブランクを空けるのも「精進」の内なんじゃないかなと思います　少なくとも僕の実体験として休止期間が実力につながったと感じているので

今度の展望

黄色という自分の中では大きな通過点を超えることができたので、競プロはまた休止して受験勉強に専念するつもりです(もちろん大学に入ったら再開したい)　ただ「競プロやりてー」ってなったらABCにも不定期で参加しようかなと思っています

拙い文章ですがお読みいただきありがとうございました



P.S.　黄色になったらやりたいことリスト(スマホのメモ帳に残ってたもの)　参考にならないと思いますが....
・ポエムと共にツイート
・AGC042のレジ
・めるアイコン
・色変記事を書く