こちらの記事で「ちゃんと考察してから解きましょうね」（超意訳）と書いてあり、最近はその練習をしています。 初心者が陥りがちな嘘貪欲やコーナーケースやその他諸々に関して - えびちゃんの日記 記事で例題として載っている問題について、コードを書いた…

二分探索の問題を解いていたら、凸グラフの頂点を求めたくなって、ついでに三分探索の練習したのでメモ。問題は以下。 B - 花束 三分探索詳しい説明は以下のサイトを参考に（というかほぼそのまま実装）した。 三分探索を救いたい - Qiita 二分探索と三分探…

以下の記事を見ながら練習したことのメモ。 rsk0315.hatenablog.com 現状、以下の記事内の 何も考えずに AC するまで [i] [i+1] [i-1] などを適当に書き換えるような癖はつけない方がいいと思います。 みたいなことが度々あるので、少しずつ書き改めていく。…

2022 後半は、前半よりも競プロの時間を取れない（取らないと決めた）ので、どのように精進しようか迷っている。 以下はその思考メモ。 やっぱり水色になりたい 水色になるためには、以下のようなことが必要そう（体感） 2 回に 1 回くらい 5 完できる 安定…

年初に「今年の前半は競プロをがんばる！」と決めて半年間取り組んだので、その振り返りです。取り組んだこととその感想が主な内容です。 自分の備忘録目的で殴り書きした感じなので、あまりまとまりがない上に、箇条書きですがご了承ください m(_ _)m 結論…

はじめてヒューリスティックコンテストに参加したので、忘れないうちに感想とやったことをまとめたいと思います。 参加時の状態はこんな感じです。 AtCoder アルゴ緑(919) ヒューリスティックコンテスト参加経験なし ヒューリスティックコンテストの事前予習…

今日参加したあさかつ で解いた問題が貰うDPを利用した勉強になる問題だったので、そのメモ （最後にお世話になった参考記事、動画のリンクを載せてあるので、そちらを先に見てもらった方が分かりやすいかもです。） 問題 atcoder.jp 考察（間に合わずTLEす…

二項係数nCr、1<=r<=n の範囲を事前計算してテーブル作れば、前計算O(n)、以後O(1)だし割と困らない？？— なかしー (@nakashiii2020) 2022年5月23日 ということで、以下の4つをO(n)で前計算して、O(1)で呼び出せるようにする 階乗 順列 nPr 組み合わせ nCr …

01-BFSと枝刈りBFSを忘れかけていたので、見返す時用の雑なメモ 01-BFSで解ける問題は、枝刈りBFSでも解ける問題が多いっぽい？ 問題 E - Bishop 2 枝刈りBFS 基本は通常のBFS 「明らかに探索しなくていいいパターン」が出現したら、その頂点以降の探索を打…

直線上の点を数え上げる問題。本番で AC できなかったので解法をメモ 問題 AtCoder Beginner Contest 248 E - K-colinear Line 勉強になったこと 1 次直線をどうやって少数使わずに表現するか（同じ直線かどうかをどう判定するか） 直線上に点があるかの判定…

本番ではACできず、解説見たら区間数え上げの典型(？)としてとても勉強になったのでメモ 基本的には以下の2つの解説を（おおよそ）そのまま実装していく E - Max Min 解説 by Nyaan E - Max Min 解説 by carrot46 勉強になったこと しゃくとり法の応用 区間…

部分文字列の抜き出しの仕方が分からなくて困った時に見返すようでメモ。 この解説動画がめちゃくちゃ分かりやすい www.youtube.com 問題はこちら atcoder.jp コード #include <bits/stdc++.h> using namespace std; // 変数宣言------------------ string s; // メイン----</bits/stdc++.h>…

競プロ用に約数、素数関連のよく使う処理をテンプレ化したので、そのメモ ※追加後にいくつかバグが見つかっています。ご利用の際は自己責任でお願いしますm( )m // 約数列挙 vector<ll> get_divs(ll n) { vector<ll> res; for (ll i = 1; i * i <= n; i++) { if (n %</ll></ll>…

mod割り算まわりの便利ツールを用意したのでメモ これでmodに怯えずに戦える（かも） modの演算の詳しい説明はけんちょんさんの以下の記事がとても分かりやすいです qiita.com 便利ツール // x!(mod mod) ll mod_fact(ll x, ll mod) { ll ans = 1; for (int …

グラフの問題を練習してて、よくあるHW盤面の問題をグラフ構築してから実装してみたのでそのメモ 問題 これを解いていく。HW盤面の迷路の最も基本的な形。 atcoder.jp ※以下の2パターンの実装、書いた時期が違うので書き方の癖が違って読みにくいです、、 HW…

2022年の目標のひとつとして、「半年で競プロを700時間勉強する」というのを決めた。 なぜ、そんな目標にしたのかを忘れないうちにメモ なぜ競プロ？ 一応仕事はwebエンジニアなので、以下の条件を満たすものを目標にしたいと思っていた。 webエンジニアの仕…

問題（ざっくり） 1〜Nまで番号のついた牛がいる 牛は番号順に並んでいる 仲良しの牛a, bは距離d1以内に並べる 中が悪い牛c, dは距離d2以上離して並べる 1番目の牛とN番目の牛の距離の最大値を求めよ。 そのような並び方が存在しない場合は-1, いくらでも離…

蟻本でプリム法とクラスカル法を勉強したのでメモ。 クラスカル法の方がかなりスッキリ書ける。 （注）2ケースくらいでしかテストしていないので、バグらせていたらごめんなさい 問題（ざっくり） N人の女とM人の男を全員徴兵する際の最小コストを求めよ。 …

蟻本のプログラムを写経しながら、分かりにくかったところをコードにコメントしたのでそのメモ。 辺の表現や変数名なども自分の分かりやすいものに変えてある。 ダイクストラの気持ち 「最短距離を一つずつ確定させていくアルゴリズム」になっている。負の重…

蟻本を進めていて、p85のUnion Findを使った例題が理解できず苦労してます。 図を書いたら少しだけ理解が進んだので、メモしておきます。（勉強中のため、間違っている部分があったらごめんなさい！） なお本記事はUnion Find自体の解説はなくて、Union Find…