行列のアフィン変換(平行移動・回転・X軸で反転(-1倍の拡大))

自分の検索用の記事です アフィン変換とは?平行移動、拡大縮小、回転、スキューができる。2次元平面を考えているなら3x3の行列で表現。ベクトルは(x,y,1) 使った問題 ABC189 E - Rotate and Flip https://atcoder.jp/contests/abc189/tasks/abc189_e AC htt…

AOJ 3117 K Average Ranges

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3117 誰も解説を書いていなかったので、方針だけ 入力Aの累積和をBとする 条件を満たすi,jの組を数えるには、座標圧縮してBITを使うなどすればいい

fake nodeと二部グラフ 2部グラフ

Quiz D The Number of Imposters https://codeforces.com/contest/1594/problem/D 感想 有向グラフの問題に見えるが、よく考えると無向グラフ imposterと言っているなら、頂点x, yは違う色 crewmateと言っているなら、頂点x, yは同じ色★ ★について、色はまだ…

RUPC2018 C-一致 mapの一致判定は速い!?

Quiz https://onlinejudge.u-aizu.ac.jp/beta/room.html#RitsCamp18Day1/problems/C AC https://onlinejudge.u-aizu.ac.jp/beta/review.html#RitsCamp18Day1/5920491 解法 左からK個を入れたmap 右からK個を入れたmap をそれぞれ作って==で比較。愚直解とし…

ACPC2021 day1, day2, day3 解説リンク

イベントページ https://connpass.com/event/224873/ day1 農工 AOJ https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC2021Day1 解説 https://hackmd.io/@olphe/rkMzuFtQF day2 会津 AOJ https://onlinejudge.u-aizu.ac.jp/services/room.html#ACPC…

2次元平面上のLIS

上記のようなやつ 問題 [ABC038-D]プレゼント https://atcoder.jp/contests/abc038/tasks/abc038_d AC https://atcoder.jp/contests/abc038/submissions/9043995 [ARC126-B]Cross-free Matching https://atcoder.jp/contests/arc126/tasks/arc126_b AC https…

典型90 073 - We Need Both a and b(★5)

https://atcoder.jp/contests/typical90/tasks/typical90_bu 難しい 木DPの状態は定義できても、遷移が難しい 公式解説をさらに解きほぐすと、下図ということなのだろう

dfs バックトラック

バックトラックについて書いてなかったのでここに例題など載せていこう dfsしながら、進めなくなったら1歩戻る 例題 典型070 - Plant Planning(★4) https://atcoder.jp/contests/typical90/tasks/typical90_br AC https://atcoder.jp/contests/typical90/s…

D-Maximum Sum of Minimum ~葉から決めていく解法~

Quiz https://atcoder.jp/contests/m-solutions2019/tasks/m_solutions2019_d AC https://atcoder.jp/contests/m-solutions2019/submissions/25535678 解説 公式解説では大きい値から辺に設定し、辺を伸ばしていくdfs 逆に、葉から小さいコストのものから設…

visual studio code (VSC) のターミナルで使うシェルを変更する

元環境 Windows 10 Ubuntu (WSL)をVSCのターミナルから開いてg++などを使っている 2021/09/03 VSCを更新し、VSC内のターミナルを開いたらいつものLinuxシェルの動きではなくなった PSと書いてあるのでPowerShellがデフォルト起動している 表示>terminal タ…

D-ABS SUM(技術室奥プログラミングコンテスト#6 Day1)

Quiz https://atcoder.jp/contests/tkppc6-1/tasks/tkppc6_1_d AC https://atcoder.jp/contests/tkppc6-1/submissions/25307869 解説 区間を累積和で書き直す 累積和を各項Biとした配列Bをソートして、i, j (i<j) の全組み合わせについてBj - Biの和を取れば答え 以下の画像はN=4の場合 int main(){ cin.tie(0); ios::sync_with_stdio(false); // input ll N; cin>>N; VI A(N); rep(i, N…</j)>

有向グラフ 閉路検出 トポロジカルソート DAG

Quiz PAST7 J-終わりなき旅 AC https://atcoder.jp/contests/past202107-open/submissions/24415719 解法 グラフをトポロジカルソートする DAGじゃない時は失敗する DAGじゃない場合は閉路がある 計算量 トポロジカルソートの分の O(N+M)

平面走査(法) (scanline algorithm?)

上記画像は https://atcoder.jp/contests/abc174/tasks/abc174_f の解説放送から 2Dにプロットしてそれぞれ処理していくのだが、処理順をx軸またはy軸の順に滑らせる BIT, segtreeがお供? 問題集 Range Set Query https://atcoder.jp/contests/abc174/tasks…

E-Throne ~合同方程式(ax≡b (mod m))とgcdの関係をつかむ動画2つ~

https://atcoder.jp/contests/abc186/tasks/abc186_e editorialを見ると、合同式の方程式を解く方法が知りたくなる。例えば ax ≡ b (mod m) これを満たすxを求めたいが、xは存在することもあるし、存在しないこともある gcd(a, m)の値が重要になる 高校の数A…

Moamen and XOR

Quiz https://codeforces.com/contest/1557/problem/C AC https://codeforces.com/contest/1557/submission/125425375 解説 ビットごとに考える nが奇数の時 等号しか作れない nが偶数の時 大なりになる列iを全探索 code void solve(){ ll n,k;cin>>n>>k; if…

始点に戻らなくていい巡回セールスマン bitDP N=17 (それって最短ハミルトン路)

Quiz E-Magical Ornament https://atcoder.jp/contests/abc190/tasks/abc190_e AC https://atcoder.jp/contests/abc190/submissions/19830501 解法 K<=17と小さいので訪れる順番を全て試すbitDPをしたい 石の数が105と多いが、注目すべき石は17個に抑えられ…

ルーカスの定理 lucas リュカ 使った記録

B-123 Triangle https://atcoder.jp/contests/agc043/tasks/agc043_b AC https://atcoder.jp/contests/agc043/submissions/24728675 その他 自分で作ったのはTLEしたりギリギリACしたり、意外とLucasの定理は時間がかかるようだった algo-logicさんのを借り…

最小費用流 負のコスト うし フロー

Quiz PAST7 M-分割 https://atcoder.jp/contests/past202107-open/tasks/past202107_m AC https://atcoder.jp/contests/past202107-open/submissions/24451393 ACL 負のコストを使うとassertでREになる うしさんライブラリ https://ei1333.github.io/luzhile…

有向グラフのオイラー路・オイラー閉路判定関数

Quiz https://yukicoder.me/problems/no/1605 AC✅ https://yukicoder.me/submissions/679290 #include <atcoder/dsu> using namespace atcoder; // 忘れがち // (有向グラフ版) // オイラー路ライブラリ // そもそも連結されているか (by BFS) // 有向グラフなら始点に</atcoder/dsu>…

Air Conditioners エアコン (左から見る&右から見る)

Quiz https://codeforces.com/contest/1547/problem/E AC https://codeforces.com/contest/1547/submission/122256788 解法 左からの累積MIN, 右からの累積MINを取ればいい 別解? 下記画像左上のように、不要なエアコンがあれば除去してしまえば、現在位置…

KickStart Round D 2021「Cutting Intervals」

Quiz https://codingcompetitions.withgoogle.com/kickstart/round/00000000004361e3/000000000082b933 (他人の)問題解説 KickStart Round D 2021.気づいたら始まっていて遅刻.そして早退.1問目,真ん中の候補は出てくる要素を足して2で割ったものだけ…

グループ化して並べる(AquaMoon and Chess)

https://codeforces.com/contest/1546/problem/D B は 11 を 2 とおいたら 0-2, 1-2 は swap できるが 0-1 は swap できない問題になって、01 文字列の隙間から 2 を置く場所を選ぶ問題になった— ふっぴー (@fuppy_kyopro) July 11, 2021 point グループ化し…

誤差に気をつける問題では値が0の確認にEPSを使用せよ ~C. Need for Pink Slips~

問題 Need for Pink Slips https://codeforces.com/contest/1543/problem/C 問題説明 カードC, M, Pが確率c, m, pで配られる それ以外のパラメータvがある Pを引いたらゲームは終わり C, Mを引いたら確率が変化する。ここではCを引いたとする c<=vならc=0と…

Plus and Multiply

Quiz https://codeforces.com/contest/1542/problem/B S={1}とする。Sの要素には「aをかける or bを足す」を無限回できて要素を増殖できる。nを作れるか判定せよ。制約は109 AC https://codeforces.com/contest/1542/submission/121451438 解説 書き下しても…

定数倍高速化メモ置き場(随時追記)

一般の場合 愚直で無理やり通すとき典型・入出力をバッファから直接読む・半分で割って定数倍 1/2 をつける・自分の解法でやばいケースを想像してそれだけ対策してみる・uint を使う・キャッシュへの載せ方を考える— のいみ (@noimi_kyopro) June 14, 2021 …

試し割りの素因数分解はlong longを使うと4倍以上遅い。intにせよ

Quiz Another Problem About Dividing Numbers https://codeforces.com/contest/1538/problem/D TLE https://codeforces.com/contest/1538/submission/119039358 AC✅ https://codeforces.com/contest/1538/submission/119077130 伝えたいこと 制約 N=104, A=…

TopCoder SRM 807 div2 に参加して青になった

SRM 807 links https://codeforces.com/blog/entry/91583 div2 only. レート1200未満のみrated 私のレートは1080の緑だった。青にしたいと思って2年ぶりに参加 4問構成 A 実装 B 平均の数式を立てる。不明な数値を「?」とすると、「?」が平均である場合を…

054 - Takahashi Number(★6)別解 setで済んだら消していく

Quiz https://atcoder.jp/contests/typical90/tasks/typical90_bb AC (7/12 20:00以降に見れます) https://atcoder.jp/contests/typical90/submissions/23306592 解法 ランクを0, 1, 2, ...の順に確定していく 確定中に参照した本はその時点で関係者全てのラ…

dequeのランダムアクセスがO(1)とは知らなかった

Quiz Deck(★2)https://atcoder.jp/contests/typical90/tasks/typical90_bi AC✅ https://atcoder.jp/contests/typical90/submissions/23305242 ランダムアクセスがO(N)である場合も解ける https://atcoder.jp/contests/typical90/submissions/23290052 注意…

整数行列の掃き出し法の問題をけんちょんさんライブラリで解いた

Quiz 057 - Flip Flap(★6) AC https://atcoder.jp/contests/typical90/submissions/23287874 掃き出し法? 適用すると、行列が上三角行列( or 行階段行列?)になる(下記画像) けんちょんさんの記事 https://www.google.com/search?q=Gauss-Jordan+%E3%8…