2023 年度のアジア横浜大会に Speed Star で参加してきました。自分は非早生まれの M1 の代なので、今年が参加権のある最後の大会でした。 ICPC は参加し始めて 5 年目、やはり一度は WF に出たいという気持ちが強かったので、今回の横浜にはかなり気合を入…
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 17 日目の記事です。 木クエリゴリゴリ問題です。 問題概要 頂点の木がある。頂点 の親は であり、その間の距離は である。 について、 を求めよ。 制約 解法 大体重心を求めたいという問題です。 頂点…
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 10 日目の記事です。 少し珍しいタイプの木DPの問題です。 問題概要 頂点の木がある。頂点 の親は である。各頂点 には価値 のコインが 枚ある。 あなたは木から価値の合計が最大になるよう最大 枚のコ…
この記事は帰ってきた AOJ-ICPC Advent Calendar 2022 3 日目の記事です。 ミンコフスキー和に関しての問題です。 問題概要 凸多角形 と整数 があり、 を満たしている。 凸多角形 が与えられるので、条件を満たす のうち、 の面積の和の二倍の最小値を求めて…
greed ではテストケースの情報を data という変数に格納していますが、これは C++17 から追加された std::data という関数と衝突してしまってコンパイルが通りません。 次のように変えることで衝突を防げます。 // template class ${ClassName} { public: ${…
greed ではテストケースの情報を data という変数に格納していますが、これは C++17 から追加された std::data という関数と衝突してしまってコンパイルが通りません。 次のように変えることで衝突を防げます。 // template class ${ClassName} { public: ${…
MathJax = { tex: {inlineMath: [['$', '$'], ['\(', '\)']]} }; onlinejudge.u-aizu.ac.jp $ V = \left\{ 1, \ldots, N \right\} $ とする。 $ f(S) = (S \subset V \text{に誘導される部分グラフが連結な確率})$ とおく。 実は $ 1 \in S$ しか考えなくて…
問題 atcoder.jp 概要は省略します。 求める答えを とします。 終了状態としてあり得る 個の状態を とします。 終了条件を除いて操作したとき、はじめて となるまでの回数の期待値を とします。 終了したときに となっている確率を とします。 終了するまで…
問題概要 の置換 と正整数 が与えられる。 置換 であって、 を満たすものを一つ求めよ。 制約 - 解がこちらで説明されています。segtree.hatenablog.com 置換を有向グラフとして見るといくつかのサイクルに分解できることが知られている。 置換 が誘導する有…
全体 2 位/学内 2 位でした！！ 去年落ちて悔しかったので今年は無事通過出来て良かったです。 折角なので本番中の動きについてメモっておきます。 本番前 作戦を説明。のいみが BC, jell が A, シャーペンに DEF を読んでもらうことに。 本番 ページが繋が…
-Wl,--stack=256000000 みたいなオプションをつけるのではうまくいかなかったんですが、 #pragma comment(linker, "/stack:256000000") をコードの先頭につけるとなんかうまくいきます。
https://atcoder.jp/contests/agc017/tasks/agc017_f で解きます。 左に曲がったら 0, 右に曲がったら 1 として折れ線を 2 進数に変換します。 隣りあった折れ線に対応する整数について、01 の列の累積和を取ったものが、どの index についても右の方が大き…
かなり面白かった + 解説が韓国語しかないということで簡潔に解法をメモっておきます。 概要 木 がある。 で距離 の点の組に辺を張ったグラフ が与えられる。 を 1 つ復元、またはそのような がないことを言え。 制約 かなり取っ掛かりがつきにくくて迷走し…
区間と値を管理する構造体、名付けて Interval Manager を書いてみました。 特殊なアルゴリズムは特に使っていませんが、よく出てくる操作かつバグらせやすいと思い書いてみました。 機能 の値を返す。 区間 を に更新する。 区間 を に更新する。区間と値の…
ですが、こういう時は -indexed にしないで -indexed のまま処理すると となって楽 謝辞 : 教えてもらったわけでもなんでもないですが @beet_aizu さんありがとうございます。
初めて TechFUL に参加してみたんですが、1 位でスイッチ lite がもらえることになったみたいで嬉し～なのいみです。 割と簡単(青 diff くらい？)めの問題が多かった印象ですが、この「羽根つき」の問題だけ少し難しめに感じました。解説の計算量は らしいで…
現状 目標 AtCoder 赤 どうせ色々目標を立てたところで意識しないので一本に絞ります、今年もよろしくお願いします。
div1 バチャの記録を付けます。ネタバレはなるべく無いようにします。 評価は主観ですがなるべく客観性のあるようにします。 url は standings を見てしまわないように my submission へのリンクを貼っておきます。 ★★★★☆ : 星4 として使います。 div1 #299 …
問題ページ 問題概要 「良い数列」とは次の条件を満たす正の整数列のことである。 任意の に対して、 を部分列に含む。 正整数 が与えられるので、 各 に対して、次の問題を解いてください。 すべての長さ の 「良い数列」に は何回登場するか。 制約 考察 …
そのいくつまで続くかはわかりませんが、いい感じの問題を見つけたら暇を見つけて書いていこうと思います！ 趣旨 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介 原案はそのまま、場合によっては原文が証明問題のものも使…
その2です。今回は難しめです！ その1 趣旨 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介 原案はそのまま、場合によっては原文が証明問題のものも使用していい感じの問題文に改変して紹介 といった感じで行こうと思いま…
そのいくつまで続くかはわかりませんが、いい感じの問題を見つけたら暇を見つけて書いていこうと思います！ 趣旨 各国の数オリで出た問題で競技プログラミングの問題にもなりそうな問題を集めて紹介 原案はそのまま、場合によっては原文が証明問題のものも使…
問題ページ 問題概要 N個の点 \( (x_i,y_i) \) が与えられる。四点と、それらを結んでできる四角形に内包される点の組の総数を求めよ。 ただし四点の順番は区別しない。 制約 考察 \( N ^ 2 \log N\) が間に合うので中心の点を固定したときに四点の組の数が …
