Rたん🎀

GitHubに置いたコードは下記リンクからたどってください。アイコンは @lilyringo33 さんに描いて頂きました。アルゴ🩵

[Rたん🎀 @cppfriendsbot]

小さい方から10万番目の素数は130万くらいなので、素数の密度が薄まることを考えるとさすがに20万番目の素数は300万以下である(正しくは2750159)、をARC 197-Cでやったのですよね。PBDS実装しか知らなかったのでTLEしたのですが、ARCでも実装方法を知らずにACできないことってあるのですよ。

[Supreme @mathematics0314]

@FN2pQnHwaH91514 嘘解法
100以下の素数は25個であることが知られている
ここで、1000個以下の素数は、素数の密度が薄まることを考えるとさすがに250個以下である

[いぷしろん @epsilon0924]

JOI一次予選ですが,TeXで全完しました!
おそらくTeXerは僕だけだと思われますが他にいたら教えて欲しいです！

[Rたん🎀 @cppfriendsbot]

久しぶりのAWCです。E問題はPBDSでmultisetを作ったらeraseの挙動がおかしく、s.erase(s.find_by_order(s.order_of_key(p))) でACしました。Fenwick treeを二分探索すべきでした。昔ARCで同じことをやって、解法が見えた問題をTLEで落とした反省はどこに行ったのでしょうか。
#AWC0187

[Rたん🎀 @cppfriendsbot]

おはようございます。
次回のARCも++のようです。私が青コーダーになる日は一か月後どころか永遠に来そうもないので、ARCにratedで参加することはしばらくなさそうです。

[株式会社 ALGO ARTIS（アルゴ・アーティス） @algo_artis]

【15歳の挑戦を受け止めた夏🌻】
インターン募集のないALGO ARTISに届いた、香川高専1年生からの一通の問い合わせ。
その熱意に応え、初の高専生インターンが実現しました！
約1か月半の研究で得た成果と、お互いに受けた刺激とは？
小山さんとプリンシパルアルゴリズムエンジニア 松尾のインタビューを公開👇
https://t.co/k9xywCGm3d
#高専 #競プロ #ALGOARTIS

[Rたん🎀 @cppfriendsbot]

F問題の公式解説1は実装できましたが、E問題の公式解説2は答えが合いません。今日はここまでにしましょう。

[Rたん🎀 @cppfriendsbot]

ABC 481-E は、角度を std::float128_t で持てば、角度 [r, r+π) を単に二分探索してACします。どの相異なる2個の星についても、それらと原点が一直線上に並ぶことはない、という制約を見落としていました。外積を述語とするソートは要らないのですか。
https://t.co/oazF7MJIY7

[Rたん🎀 @cppfriendsbot]

誕生日にバナナタルトを食べてから、お酒を飲まずに午後9時からアウェーで一人で戦った、というのが如何にも私らしいです。今日はのんびりと過ごしましょう。コンテスト中に「なんでWAなんだよー」と画面を見つめている自画像?でも描きますかね。

[Rたん🎀 @cppfriendsbot]

ABC481 の振り返りをGitHub に載せました。使用したライブラリもこのリポジトリにあります。F問題は、公式解説1の方法をコンテスト中に目論んで失敗し、翌朝公式解説2の方法で解きました。問題文を読んで解けそうな予感はありましたが、30分ではどうにもなりませんでした。
https://t.co/oXai3NIVwU

[Rたん🎀 @cppfriendsbot]

おはようございます。
昨日のF問題を解けました。Trieという言葉が見えましたが、そういうことです。コンテスト中はダイクストラ法にBFSを組み込めず、今朝実装したらACしました。実装力が無さすぎ、E問題に時間を掛け過ぎで青diffは獲れませんでした。思いつくこととやり遂げることは異なります。

[Rたん🎀 @cppfriendsbot]

E問題は点を二周するのに気付くのが遅いです。これでF問題の時間が無くなり、boost::multiprecision::cpp_int でダイクストラ法したらMLEになりました。パスグラフを考えたらそれはそうです。まだ解説は見ないで明日考えましょう。反省はあれど、世界の風に吹かれる充実した誕生日でした。

[Rたん🎀 @cppfriendsbot]

D問題まで14:10、E問題は偏角ソート後に原点からみて点対称の位置をどう求めるか分からず、atan2をstd::float128_tで求めて8 WAsしました。やっぱりダメかと思い直し、点を二周してstd::partition_pointで二分探索、述語を外積が正の範囲にしたらACでした。
#AtCoder #ABC481

[Rたん🎀 @cppfriendsbot]

誕生日🎂に勝ちました。これが現役プログラマの生き様ですよ。
zettsutさんのSMBCプログラミングコンテスト #2（AtCoder Beginner Contest 481）での成績：1443位
パフォーマンス：1428相当
レーティング：1263→1280 (+17) :)
#AtCoder #ABC481 https://t.co/Yr7QiPP1qd

[Rたん🎀 @cppfriendsbot]

@kaede20203 ありがとうございます

[Rたん🎀 @cppfriendsbot]

今日は誕生日です。10月24日、2^10 はプログラミングの申し子ですね。かつてはプログラマ35歳定年説と言われましたが、0x35歳までプログラマをやっていたら、Claude Code と上流設計からコーディングまで熱いセッションを繰り広げられる時代になりました。長く続けるといいことがあります。

[Rたん🎀 @cppfriendsbot]

あまり年齢を強調するのもどうかとは思いましたが、AtCoderのプロフィールには生年が書いてあります。それとGitHubアカウントに書いてある本名が珍しすぎて、USPTOで特許検索するとプログラマになった時期もこれまでの勤務先も隠し切れません。ご縁がありましたらよろしくお願いします。

[Rたん🎀 @cppfriendsbot]

公式解説2の|A|=3を解析解ではなく二分探索で求め、|A|>3を公式解説1で求めたような解法になりました。|A|=3のときも実装をまとめられるはずですが、上手くいきませんでした。__int128を使ってオーバーフロー対策はしたはずなのですが。平方分割で挑んだのが回り道です。

[Rたん🎀 @cppfriendsbot]

昨日のE問題をようやく解けました。|A|を基準に数えるのと、W=A_2-A_1を基準に数えるのを場合分けして時間を溶かしました。正しくは、|A|>3ならWと|A|を固定して二分探索でA_1の最大値を求め、|A|=3ならA_1を固定して二分探索でWの最大値を求めます。コンテスト中なら全然間に合っていません。

[Rたん🎀 @cppfriendsbot]

昨日のABCは出られなかったので先ほど解きました。C問題は動的いもす法をそのまま実装したらTLEが返り、お湯が出ない時間帯を一括処理したらAC、D問題は累積和を二分探索、E問題はチラ見しただけで考察していないのでヒントを観ないように生活します。次回ABCは誕生日、0x35歳でも水パフォを出すぞい。