012BFSはqueueを3個持つ

012BFSとは?となったキッカケ https://twitter.com/chokudai/status/1754369800862900253 chokudaiさん「01BFS知ってるなら、012BFSは発想できるでしょ」 私「???」 理由は、01BFSをdequeで実装するものだと思っていたため。一方でchokudaiさんはqueue 2…

AHC 至高のアルゴリズム リンク集

AHC015 https://speakerdeck.com/thunderc/toyota-ahc-zhi-gao-noarugorizumujie-shuo-hui-ahc015 AHC026 https://speakerdeck.com/bowwowforeach/toyotazi-dong-che-puroguramingukontesuto2023-number-6-atcoder-heuristic-contest-026-zhi-gao-noarugoriz…

AHC029(RECRUIT 日本橋ハーフマラソン 2024冬)で38位。賞品を頂いた

40位までならパーカー確定。pretestで41位だったかな、手元で100ケース回して良いコードを提出していたので何人かはsystem testで抜けると思っていた コンテスト終了が2023-12-26(火) 21:00 ちょうど1ヶ月経たないくらいで賞品が届いた。早くていいね。あり…

AHC017復習 ダイクストラ内の最短路木の差分更新

問題 提出 ダイクストラ内の最短路木の差分更新 初期解 サンプル点 登り成功回数 / 登り挑戦回数 のサンプル 追記:さらに延長戦 問題 A - Road Repair 道路工事 https://atcoder.jp/contests/ahc017/tasks/ahc017_a 提出 https://atcoder.jp/contests/ahc01…

abc334 C - Socks 2 累積和を使わない解法

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

二分探索の上限をinfにするのは危険 D - Jumping Takahashi 2

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

long doubleのsqrtはdouble版より10倍遅い

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

MEXをset<int>から二分探索しようとして失敗した E - Mex and Update

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

ダイクストラ 復元 注意点 prev

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

(自分用メモ) 論理式の式変形 (和をXOR, ANDで書き直す)

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

C - Remembering the Days next_permutation解法

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…

abc309_c "C - Medicine" 二分探索解法

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); …

ABC307 Cなのに水色diffとなってしまった問題「Ideal Sheet」を解いてみた

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

H - 桁差の和 (第13回 アルゴリズム実技検定) 別解(ソート・二分探索・累積和)

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

シャッフルの平均移動距離はN/3

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

E - KarutaをTrie木で解いてみた

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

CodinGame Winter Challenge 2023 (2hアルゴコンテスト) 問題メモ

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

AHC018(水路掘り) 参加記 173位/1086 解法と細かいテク

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

ABC278 E - Grid Filling ~Aの値域を気にせず(?)mapで解く解法~

問題 https://atcoder.jp/contests/abc278/tasks/abc278_e 提出 https://atcoder.jp/contests/abc278/submissions/36654013 (AC 600ms) 方法 種類数はmap.sizeで求める 除去範囲を1ずつスライドさせてmapを更新する。この更新は差分のみ行い高速化する 計算…

はじめての「ビームサーチ」に最適なシンプルな問題

鉄則本のビームサーチ用問題 追記:毎ターン得点が決まるからといってビームサーチとは限らない 現状:ビームサーチの使い所が分からない! 2024/01/09 追記:ビームサーチは多様性が大事 追記:ビームサーチで状態のコピーが重いなら1手でやることを大きく…

はじめての「焼きなまし」に最適なシンプルな問題

これ https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_at 鉄則本を手に入れたのでやってみた 自分流にアレンジを加えつつ1から書いたことで、ハマりはしたものの理解が深まった 提出 https://atcoder.jp/contests/tessoku-book/submissions/35…

第九回 アルゴリズム実技検定 G - 連結 ~UF解法~

https://atcoder.jp/contests/past202112-open/tasks/past202112_g AC https://atcoder.jp/contests/past202112-open/submissions/32875853 N=100なので隣接行列で持つ Yes, No判定の時は毎回UF(Union Find)を構築して連結判定する その計算量は? 隣接行列…

E - Addition and Multiplication 2 ~DP解法~

Quiz https://atcoder.jp/contests/abc257/tasks/abc257_e AC https://atcoder.jp/contests/abc257/submissions/32759201 500ms 計算量O(100N) 解説 dp[i] : i円使ったときの最大値(値は分布で持つ) iが小さい順に確定していく。配るDP 分布の比較用関数を…

ABC233 C - Product ~map解法~

問題 https://atcoder.jp/contests/abc233/tasks/abc233_c AC https://atcoder.jp/contests/abc233/submissions/32504623 解説にmap解法がなかったので書いておく code int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N,X; cin>>N>>X; m…

タイマーで時間いっぱい回す

サンプル https://atcoder.jp/contests/ahc006/submissions/27258298 hitonanodeさんのコードを参考に制限時間ギリギリまで回す

進度を見える化すると捗る。AtCoder Problems等の紹介

Atcoder Problems https://kenkoooo.com/atcoder/#/table/ 解いた問題は緑色になる。難易度も色で分かる Codeforces Problems https://cf.kira924age.com/#/table/ yukicoder problems https://iilj.github.io/yukicoder-problems/#/table/

競プロで私が入れているユーザスクリプト tampermonkey

Chromeのアドオン整理中にtampermonkeyを消してしまい「何を入れてたっけ?」となったので整理しておく。入れすぎないようにはしている。 AtCoder ac-predictor 順位からのパフォがわかる Time Limit Emphasizer 実行時間制限が2secじゃないときに強調 AtCod…

(deprecated) AHCレーティングを確認するサイト

AHC(ヒューリスティック)もよく参加しています 最近は開催頻度も多い 最適化なのでアルゴより業務に近い印象。コード量も多くなるので、整理や命名も大事 レートを確認するサイト こちら https://iilj.github.io/AtCoderMarathonRatingHistory/#/rating/pe…

青になったときのスクリーンショット