日本語によるプログラミングコンテスト
はじめに 実装メイン．テンプレは別記事．
桁DP drken1215.hatenablog.com サボる exactを管理するのは面倒くさいです。 定型のものは、ライブラリに放り投げてしまいましょう。 やりたいこと 制約をオートマトンにします。 結合します。 桁DPに渡します。*1 解けます。 実装 Digit DP on Automaton | gwen サンプルコード #include "gwen/template.hpp" #include "gwen/utils/timer.hpp" #include "gwen/automaton/digit_dp.hpp" #include "gwen/automaton/factory…
AHC069 (RECRUIT 日本橋ハーフマラソン 2026夏) に参加して 114位 でした。 (約1,000人中) 久々に上手くいった＆楽しくプレイできたので参加記録を書きます。今回も楽しい問題をありがとうございました！ atcoder.jp AHC069 seed=0 問題概要 池のある公園の管理人となり、 1,000グループの予約を捌く グループが来訪するたびに、受け入れる or 断る を上手く選んで収入を最大化しよう グループには「人数」「開始時刻」「退去時刻」「支払金額」の情報を持つが、事前にはわからない（インタラクティブ） 特に面白い点として、グループの支払金額は「上限」である…
https://atcoder.jp/contests/abc471/tasks/abc471_e2乗の和を取る問題ですが、和の2乗なので和に分解できます。つまり、和の和を求める問題なので、和の順序を入れ替えます。 まず、2乗の項が何回現れるか数えます。個から個を選ぶとき、が入っている組み合わせは、これを除いて個あります。も同様で個あります。 // Sum of Square of Sum #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromSt…
問題文 https://atcoder.jp/contests/abc471/tasks/abc471_e 問題概要 $n$ 項からなる数列 $\langle A_1, A_2, \dots, A_n \rangle$ がある． $A$ の異なる $k$ ($1 \leq k \leq n$) 項 $A_{ I_1 }, A_{ I_2 }, \dots, A_{ I_k }$ を選ぶ方法について，そのスコアを $\left( \sum_{ i = 1 }^k A_{ I_j } \right)^2$ で定義する．$A$ から $k$ 項を選ぶ方法 $\binom n k$ 通り全てに渡るスコ…
https://atcoder.jp/contests/abc471/tasks/abc471_d大きいほうから出すのでPriorityQueueを使えそうですが、時間ごとに増えていくのでこのままではだめです。残量から時間を引いたものは変わらないので、これを要素とします。 // Chargers #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new(); std::i…
https://atcoder.jp/contests/abc470/tasks/abc470_fAとBでつながっている文字同士は入れ替えることができます。なので、グラフにして連結成分ごとに考えればよいです。入力例1なら1と3が連結成分で、2と4と5も連結成分です。このとき後者の文字はiとiとaなので、iとiは入れ替えても同じなので、通りあることになります。一般にもこのように多項係数になります。これをすべての連結成分で掛け合わせます。 ただし、入力例2は1と2と3、4と5と6が連結成分で、その中で任意に並び替えることができますが、は偶数であることに留意しなければなりません。偶置換と奇置換という…
https://atcoder.jp/contests/abc470/tasks/abc470_e違うパスで同じ状態になりえます。例えば、1と1→2と2とその逆で同じ状態になります。だからDPを使いたくなります。状態に対してその状態になる確率を求めます。状態は、何組取れたかと残りのライフです。あと、例えば1と2をめくったとき、1と2が記憶されていることを知らなければならないので、何が記憶されているかも状態になります。しかし、2枚記憶しているときどの2枚も同じ確率で現れるので、全てまとめてあとから取れた組数×Aの平均を確率にかければよいです。だから、としてはどれを記憶しているかではなく何枚記憶し…
AHC069 にけっこうしっかりとした時間を割いて出た。せっかくなので文章を書く。 長い文章は書けないし、 AI に吐かせるにしてもその文章を読むことも大変なので、なるべく人力で手短に書く。 順位 atcoder.jp パフォーマンス 1788 、順位 201 位であり、個人的にはよい順位が出た。ローカル 100 ケースだと平均 70M くらいで、これまたキリがよい。 本番中の提出はこんなので、そこそこの幅の改善を二度起こせた。 提出時間とスコア seed0 で 59M
0.はじめまして 1.問題の概要 2.例を見る 3.最初の考察 4.公園の池と芝生の形を確認する 5.最初の提出 6.領域の割り当てを正方形に近づける 7.区画をさらに複数のグループに割り当てる 8.スコアが改善する条件を考える 9.高速化 10.いろいろなアイデアを試す 11.コストパフォーマンスでグループの受け入れ可否を変える 12.インタラクティブじゃない場合の解を出してみる（全てのMを事前に読み込む先読みあり） 13.BFSをやめる 14.2000テストケースの分析をする 15.移動のための探索を強化する 16.最小のLを満たす長方形を列挙する 17.配置できない場合のBFSに、整形を…
qiita.com
note.com
findy-code.io
qiita.com
www.slideshare.net
qiita.com
chokudai.hatenablog.com
qiita.com
qiita.com
