perogram

「別のクラスの人と3人組を作ってきてください」

動機 codeforcesでこの問題が解けなかった https://codeforces.com/contest/1201/problem/B 内容:数列Anからどれか2つを選んで-1することを繰り返し、数列を全ゼロにできるか i != j 解答は、max x 2 > sum のときNo, それ以外でYes maxが飛び抜けちゃうと…

D - Gathering Children

Quiz https://atcoder.jp/contests/abc136/tasks/abc136_d AC Code https://atcoder.jp/contests/abc136/submissions/6718753 解法 ダブリングやDPを使わない方法です 大量に移動した後は、どこかのRLに落ちて振動します 全てのRLの位置を調べておく 各子供…

スターリング数

意味 N人をKグループに分ける方法、と理解しています AC Code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3786812#1 読んだ https://qiita.com/drken/items/f2ea4b58b0d21621bd51

トポロジカルソート

Quiz http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_4_B AC Code http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3784044#1 関数化した。Code VI topological_sort(VV& G){ ll N = G.size(); // 入次数 VI IN(N, 0); REP(i, N){ fo…

No.269 見栄っ張りの募金活動 ~分割数~

n個の互いに区別できない品物を、m個以下に分割する方法の総数をnのm分割と言い、m=nのとき特にnの分割数と言う。 Quiz https://yukicoder.me/problems/no/269 AC Code https://yukicoder.me/submissions/364228 解法 先にK円ずつ増えていく分を徴収する 残…

A - Jumping!! ~負値をmodするべからず~

Quiz https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_a AC Code https://atcoder.jp/contests/tkppc4-2/submissions/6608047 感想 1WAしてしまった yが0以上の偶数であれば、飛ぶ回数は決まる それがn回、たとえば5だとすると、xとして作れるのは-5, …

I - school competition 1

Quiz https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_i AC Code https://atcoder.jp/contests/tkppc4-1/submissions/6601047 解法 editorialの通り https://drive.google.com/file/d/1CApCqwK7Hfgu81nqysUaPxSU2INI7l6R/view ただ、配列D, Uの定義は …

G - バラバラ掛け算

Quiz https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_g AC Code https://atcoder.jp/contests/tkppc4-1/submissions/6599079 解法 例えば7なら2x2x3 = 12で最大なので「2に分解していけばいいんやろ?」と思っていたが間違い 6は、2x2x2=8とするより…

ジグザグ数 zigzag

1 2 1 2 1 => 5 となるような関数を作った。再利用することがあるかも ジグザグ数と名付けた 冗長に書いてある 使用例 (to verify) D - スキップ https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_d AC Code https://atcoder.jp/contests/tkppc4-1/subm…

D - Digits Parade ~右からDP, 左からDP~

Quiz https://atcoder.jp/contests/abc135/tasks/abc135_d 内容 解法というか、左からDP, 右からDPのどちらでも解けますというメモです 解法 文字列の左からDP AC Code https://atcoder.jp/contests/abc135/submissions/6595777 公式解説と同じで、DPの添字…

コードの背景色は黒でしょ!CSSを変更しました。

CSS generator https://kawmra.github.io/hatena-syntax-highlight-css-generator/ CSSをはてなブログの設定からCSSに追記 変更後 #include<bits/stdc++.h> using namespace std; using ll = long long; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const</b)></class></bits/stdc++.h>…

LIS完全に理解した

LIS 最長増加部分列のこと 解説 https://ikatakos.com/pot/programming_algorithm/dynamic_programming/longest_common_subsequence 問題を解いてVerify http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3776378#1 計算量 O(N logN) Note ll N; cin >…

No.852 連続部分文字列

Quiz https://yukicoder.me/problems/no/852 AC Code https://yukicoder.me/submissions/363142 参考 yukicoder 218A Rubyでホイ。FAみたいです。やったね。B 誤読とかオーバーフローしてつらい。各文字について一つも含まない区間を数え上げ。D 素数の個数…

C - 単調増加

Quiz https://atcoder.jp/contests/abc038/tasks/abc038_c AC Code https://atcoder.jp/contests/abc038/submissions/6545083 解法 単調増加が続いている長さをLとすると、そこから単調増加列は1+2+...+L個取れる

B - 超大型連休 ~2012年はうるう年~

Quiz https://atcoder.jp/contests/arc010/tasks/arc010_2 AC Code https://atcoder.jp/contests/arc010/submissions/6536656 解法 土曜・日曜に休日フラグを立てておく 祝日の場所もフラグを立てる。すでに立っていたら、以降の立っていない箇所を立てる(…

C - ダブレット ~経路復元~

Quiz https://arc011.contest.atcoder.jp/tasks/arc011_3 AC Code https://arc011.contest.atcoder.jp/submissions/6535492 解法 wordをグラフのNodeとする 編集距離が1のNode同士をつなげる bfsでfirst wordからlast wordまで到達できるか調べる 経路復元 …

C - 五目並べチェッカー ~やるだけ?~

Quiz https://atcoder.jp/contests/arc012/tasks/arc012_3 AC Code https://atcoder.jp/contests/arc012/submissions/6530124 感想 やるだけかと思っていたが想定漏れが多くて何度もWA 斜めの処理は意外とやったことがなくて練習になった テストケースをあげ…

C - 高橋君、24歳 モンモール数・Montmort Number

Quiz https://atcoder.jp/contests/arc009/tasks/arc009_3 AC Code https://atcoder.jp/contests/arc009/submissions/6521277 モンモール数を求める シグマの入った一般式は負の符号が出てくるので避け、漸化式からdp的に求めた 大きい値でWAが出たので対処…

B. WOW Factor

Quiz https://codeforces.com/contest/1178/problem/B AC Code https://codeforces.com/contest/1178/submission/57485678 解法 vvをwに変換 oを見つけるたびに、そのoの左にあるw, 右にあるwの数を求めて答えに足す

ナップサック 個数x容量の表を埋めるVer

制約 荷物数N=100 バッグの容量の最大値W=10000 Quiz https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_B AC Code https://onlinejudge.u-aizu.ac.jp/status/users/peroon/submissions/1/DPL_1_B/judge/3754207/C++14 感想 ナップサックはいろいろな亜種が…

bitsetで殴るとは

bitsetの使い方 今までは2進数表示でprintするときしか使っていなかった 以下のような使い方ができる int main(){ cin.tie(0); ios::sync_with_stdio(false); bitset<10> dp; dp[0] = 1; dp[3] = 1; cout << dp << endl; dp |= (dp<<1); cout << dp << endl;…

Visual Studio Codeにbits/stdc++.hを認識させる

前提環境 Windows Visual Studio Codeでcppコードを書く VSC内でTerminalを開くとWSLになっているように設定済み g++でコンパイル なくてもコンパイルは通る WSLではincludeパスが通っているのであろう、コンパイルは通る しかし、VSC側で #include<bits/stdc++.h> に波線表</bits/stdc++.h>…

【Win】Visual Studio Code + oj + WSLで競プロ環境構築

基本 qiita.com Windows WSL Visual Studio Code内からWSLを読んでコンパイル 追加でoj テストケースDLや実行が楽になる github.com 落とし穴 oj sで提出した後、提出後URLに自動で飛んでくれるが、設定が必要 環境変数設定 vi ~/.bashrc 下記を書く。 expor…

No.742 にゃんにゃんにゃん 猫の挨拶

Quiz https://yukicoder.me/problems/no/742 解法 転倒数 計算量 BITを使えばO(NlogN)で求まる。これが想定解であろう 計算量2 バブルソートで数えるとO(N2) 今回の成約の場合、9 * 108 なんとこれでも通ってしまった https://yukicoder.me/submissions/3592…

C. Creative Snap 〜10^9を扱うには?二分探索・再帰関数〜

Quiz https://codeforces.com/contest/1111/problem/C AC Code https://codeforces.com/contest/1111/submission/56781314 解法 考えている範囲で一気に燃やすコスト 考えている範囲を二分割して個別に燃やすコスト 上記2つのうち、安い方を選ぶように再帰…

rand(), random_shuffle()は危険だよーというお話

Article https://codeforces.com/blog/entry/61587 代わりに mt19937 shuffle を使おうとのこと random_deviceじゃだめなのか? 実装により、出力される乱数が固定される std::random_deviceに騙された。 実装によっては決定的な値しか返さないのか…https://…

1114C - Trailing Loves (or L'oeufs?) 〜階乗に含まれる素因数の数〜

Quiz https://codeforces.com/contest/1114/problem/C AC Code https://codeforces.com/contest/1114/submission/56636163 観察 n!内にbがいくつ含まれるかが答え n, b共に値域が広く、O(N)では間に合わない ルジャンドルの定理 n! に含まれる素因数 p の数 …

D. Flood Fill 〜最大回文長とLCS〜

Quiz https://codeforces.com/contest/1114/problem/D AC Code https://codeforces.com/contest/1114/submission/56634318 解説 1 2 3 4 5 を考えてみる この場合はどこから始めても、4回の塗りが必要。一般に、N-1回塗れば同色にできる 1 2 3 2 1 を考えて…

C. Candies! 〜最後の状態だけが欲しい〜

Quiz https://codeforces.com/contest/1189/problem/C AC Code https://codeforces.com/contest/1189/submission/56582743 観察 クエリ数が多いので、1クエリあたりO(1), O(logN)あたりで解かないと間に合わない 愚直にシミュレーションしたら間に合わない …

E1. Array and Segments (Easy version) (Div3)

Quiz https://codeforces.com/contest/1108/problem/E1 AC Code https://codeforces.com/contest/1108/submission/56534524 解法 制限が緩いので全探索 A[i]のそれぞれが最終的にmaxになる値だとする その時、iを含むsegmentを適用する理由はない なので、i…