問題 https://atcoder.jp/contests/abc334/tasks/abc334_c C問題にしては難しい！ Kが偶数の時は自明なので省略します Kが奇数の時、i=0, 2, 4, 6, ... を除外した時の奇妙さをそれぞれ求めてminを取りたい。そのまま実装するとO(N2) まず、i=0を除外した時…

問題 https://atcoder.jp/contests/abc257/tasks/abc257_d 方針 Sを二分探索する。始点は全探索し、そこから全ての点を訪問できるかBFSで判定する 落とし穴があった。提出したWAのコードはこちら https://atcoder.jp/contests/abc257/submissions/48522778 i…

https://atcoder.jp/contests/abc330/tasks/abc330_c この問題を解いていて、誤差が怖いのでlong doubleを使った floatやdoubleを使っても通るか確認したところ通ったが、実行時間に差があった 実行時間 long double 122ms float 12ms double 8ms int main()…

問題 https://atcoder.jp/contests/abc330/tasks/abc330_e 考察 (WA) 1個以上存在する値をsetで管理して、そこからMEXを高速に求めればいいな set内はソートされているのだから二分探索できるだろう ということで下記のようなsetを入力としてMEXを返す関数を…

AHC020でダイクストラ復元が必要だったのでprev配列を用意したがバグらせたのでメモ ちゃんと動いた提出 https://atcoder.jp/contests/ahc020/submissions/47615048 struct Node{ ll distance; ll index; ll prev=-1; }; // ダイクストラアルゴリズム内部 { …

上記画像の式変形が成り立つ https://atcoder.jp/contests/abc238/tasks/abc238_d この問題の解説にもある 和は繰り上がりがあるが、XOR, ANDで書き直せればビットごとに解けることも AC https://atcoder.jp/contests/abc238/submissions/45114951

https://atcoder.jp/contests/abc317/tasks/abc317_c AC https://atcoder.jp/contests/abc317/submissions/45031177 「C問題でDFS !?」という意見もあったようですが、next_permutationで巡る順番を全探索すれば簡単です 注意点として、全ての点を通る必要は…

頂点数は17以下を想定 隣接行列を与えるとパスを返す関数 // ハミルトンパスが存在するなら返す // （無いなら空の配列を返す） // 入力 G : 隣接行列 (adjacency matrix) // 参考にした : by tatyam // atcoder.jp/contests/abc190/submissions/19761405 VI…

https://atcoder.jp/contests/abc309/tasks/abc309_c AC https://atcoder.jp/contests/abc309/submissions/43400326 解説と違う解法なので書いておく int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N,K; cin>>N>>K; VI A(N); VI B(N); …

問題 https://atcoder.jp/contests/abc307/tasks/abc307_c 考察として AとBのずらす位置を全探索すればいい 実装の工夫として 全部透明な行、列を削る関数があると楽 画像の上に画像を貼り付ける関数があると楽 AC https://atcoder.jp/contests/abc307/submi…

問題 https://atcoder.jp/contests/past202212-open/tasks/past202212_h 公式解説と違う解法なので書いておく Aはソートしてもいい Aiより数字が大きい箇所と小さい箇所、それは二分探索で分かる 範囲で和を求める箇所は累積和を使う 提出 https://atcoder.j…

N/3 配列の要素数Nが大きいとき、おおよそN/3と言われている link 証明を書いている人もいた link が、N→∞の箇所が私には分からなかった 実際に計算してみる 結論としては、N/3 - 1/(3*N) となった★ 和の公式など使う 1+2+...+n = ～ 12 + 22 + ... + n2 = …

解説放送でも解の1つとして挙げられていた Trie木は使ったことがないので使ってみよう アルゴロジックさんのTrie木を参考に拡張した 親側に辿る変数追加など 提出AC https://atcoder.jp/contests/abc287/submissions/39835331 初めはTLEした Trie::Node変数…

URL https://www.codingame.com/contests/winter-challenge-2023 contest is over じゃあないんだよ。もっと情報を出しなさい 追記：問題は公開された。解説は見当たらず https://www.codingame.com/work/campaigns-demo/672599/questions/ 感想 提出前のサ…

in/0002.txt 試し掘りした箇所 (BFS + Grid) 問題 提出 私の環境 大まかな解法 細かい事 テク.cpp テク.py テスト並列化 テク.sh テク.その他 コンテスト後 in/0002.txt 試し掘りした箇所 (BFS + Grid) 問題 A - Excavation https://atcoder.jp/contests/ahc…