資格ブログ

資格試験に対する進捗を記録していきます

AtCoder対策(随時更新)


dp けんちょん様(最初はinfが入っている,minを二回やるイメージ,漸化式かメモ化か,部分構造最適性の利用,表は比較して勝った方で更新)​→https://qiita.com/drken/items/dc53c683d6de8aeacf5a
全探索→http://drken1215.hatenablog.com/entry/2019/02/24/224100
けんちょん様全探索→http://drken1215.hatenablog.com/entry/2019/02/24/224100
3進数→https://betrue12.hateblo.jp/entry/2018/12/02/224027
正方形の座標→https://atcoder.jp/contests/abc108/tasks/abc108_b
制限付きソート けんちょん様(reverse,erase,push_back,auto,size,resize,煩わしい初期値の調整)→http://drken1215.hatenablog.com/entry/2019/03/24/091900
メモリの新規割り当て→https://atcoder.jp/contests/nikkei2019-qual/submissions/4097661
待ち行列http://drken1215.hatenablog.com/entry/2019/03/26/115300
-2進数(reverse,2進数を文字列として出力)→http://drken1215.hatenablog.com/entry/2018/08/13/123600



■全探索
ダイス&コイン(12f, double)→https://img.atcoder.jp/abc126/editorial.pdf
deque→https://atcoder.jp/contests/abc128/submissions/5637635
kadomatsu→http://drken1215.hatenablog.com/entry/2019/02/24/224100
N以下の753数→http://drken1215.hatenablog.com/entry/2019/04/03/125400



■二部最大マッチング
二部最大マッチング→https://atcoder.jp/contests/arc092/submissions/2217043
https://www.hamayanhamayan.com/entry/2018/03/18/085108
別解→https://scrapbox.io/ganariya/AtCoderBeginnerContest091_C%E5%95%8F%E9%A1%8C400%E7%82%B9%E3%80%8C2D_Plane_2N_Points%E3%80%8D



ボトルネック
ボトルネック けんちょん様→http://drken1215.hatenablog.com/entry/2019/04/07/003700



■両方が別方向にベストを尽くす
ABS(発想が全て)→https://img.atcoder.jp/arc085/editorial.pdf
高橋happiness→https://ami-atcoder.hatenablog.com/entry/2019/03/20/161427



区間
区間の数ミスター様→https://misteer.hatenablog.com/entry/ARC099#C---Minimization-
重複する区間の数(けんちょん様作問・解説)→https://img.atcoder.jp/cpsco2019-s3/editorial.pdf
限られた区間幅の最小値で全て同じになるまで→https://atcoder.jp/contests/arc099/submissions/2718861
花に水やり(達磨落とし的に解く)→http://drken1215.hatenablog.com/entry/2019/03/03/150200
全ての数列が1になるまで→
http://drken1215.hatenablog.com/entry/2018/06/24/003500

ある区間の和がMの倍数(109連想配列、Mで割った余りが同じ=差がMの倍数)→http://drken1215.hatenablog.com/entry/2018/08/13/125300
複数の点を選んで全てのポイントを訪れる最小ステップ数→http://drken1215.hatenablog.com/entry/2019/02/03/224100



■累積和
境の累積和 (配列の初期化も)けんちょん様→http://drken1215.hatenablog.com/entry/2019/04/21/000500
ある区間にACが含まれる数 けんちょん様(Aの右にCが来ると問題文を言い換える)→https://qiita.com/drken/items/56a6b68edef8fc605821#
マスを使った累積和→https://atcoder.jp/contests/abc089/tasks/abc089_d
累積和 マクロ使いまくり→https://atcoder.jp/contests/arc093/submissions/2255349



■累積gcd
けんちょん様(一つ削除可能という発想転換、一つを決め累積gcd)→http://drken1215.hatenablog.com/entry/2019/04/27/224100_1



■数直線上
直線上の移動(区間の補集合) けんちょん様→http://drken1215.hatenablog.com/entry/2019/02/03/224100
エレベーター 2パターンしかない→https://atcoder.jp/contests/agc015/submissions/1310029
二人が目的の地点に辿り着けるか→https://atcoder.jp/contests/agc034/submissions/5756327



■二次元座標
2点間の重複しない経路4本→https://atcoder.jp/contests/abc051/submissions/5537501
ベクトルが同じものが最大になるp,q→http://drken1215.hatenablog.com/entry/2019/06/16/011300
(setのペア、ペアの数を数える、1以上ならカウントアップ)https://atcoder.jp/contests/diverta2019-2/submissions/5920210
長方形の2分割(double)→https://twitter.com/eulerimg/status/1140258615430770688?s=21



演算子の選択
演算子の選択→https://img.atcoder.jp/abc079/editorial.pdf
+と*の数式の合計を0にする→https://atcoder.jp/contests/abc033/submissions/5538583



■組み合わせ
犬猿の仲直り(100000007,swap)→https://img.atcoder.jp/arc076/editorial.pdf
https://atcoder.jp/contests/abc065/submissions/1374279
a>b>c スヌケフェスティバル(ローヤーアッパーバウンド、真ん中を固定)→https://img.atcoder.jp/arc084/editorial.pdf
https://atcoder.jp/contests/abc077/submissions/1737302
名前がマーチの組み合わせ→https://atcoder.jp/contests/abc089/submissions/2154799



■文字列
沢山の文字列の扱い けんちょん様→http://drken1215.hatenablog.com/entry/2019/05/12/002400
怪文書 文字列の置き換え replace→https://atcoder.jp/contests/abc076/submissions/1717586
dream,dreamer,erase,eraserで構成されているか否か(substring, continue)→https://atcoder.jp/contests/abc049/submissions/1017629
ストリングから数値への変換 753→https://atcoder.jp/contests/abc114/submissions/3702215
スペース高橋君(getline,文字数の指定無し)→https://atcoder.jp/contests/arc045/submissions/4648978
ストリングから数字に変換し、最少辞書順を抽出→https://atcoder.jp/contests/abc071/submissions/1522092



■最小公倍数・ユーグリッド・共約数
最小公倍数→https://img.atcoder.jp/abc070/editorial.pdf
数直線上のユークリッドhttps://img.atcoder.jp/abc109/editorial.pdf
素因数分解とかまとめ 猫様→https://qiita.com/ct158603292321/items/4e64249abfc151d8e82b
モンスターバトル→http://drken1215.hatenablog.com/entry/2019/02/16/224200
k番目の共約数→https://img.atcoder.jp/abc120/editorial.pdf
A以上B以下のCでもBでも割り切れない数→https://atcoder.jp/contests/abc131/submissions/6096306



■Greedy
最小必要ケース 初期値をNとする→https://img.atcoder.jp/ddcc2017-qual/editorial.pdf
お年玉→https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2018/0107_abc085
カードの書き換え(pair,vp.back(),vp.empty(),vp.pop_back())→https://atcoder.jp/contests/abc127/submissions/5593239
10の倍数は0点→https://img.atcoder.jp/arc075/editorial.pdf



■数列
数回ある区間を反転させて1をできるだけ並べる→https://yudegaki.hatenablog.com/entry/2019/04/14/011133
けんちょん様バージョン→http://drken1215.hatenablog.com/entry/2019/04/14/222900
数列のある二箇所に-1を掛ける→https://img.atcoder.jp/abc125/editorial.pdf
good sequense(map)→https://atcoder.jp/contests/abc082/submissions/1872852
vvv(最小の書き換え数、偶数目と奇数目の場合分け、拡張for文、ソートrbegin rend、二次元配列とペア・マップ)→https://betrue12.hateblo.jp/entry/2018/09/30/125042
同じ要素数の数え上げ→https://atcoder.jp/contests/abc072/submissions/1558381
ある数列を別の数列の要素の数倍にする
モンスターが全滅するまで攻撃(にぶたん)→https://tmasaaa.github.io/kaito_procon/procon/201810050944.html
数を書き換えてK種類以下にする→https://atcoder.jp/contests/arc086/submissions/1857536



■キュー
<>問題→https://atcoder.jp/contests/abc120/tasks/abc120_c
プライオリティキュー→http://drken1215.hatenablog.com/entry/2019/04/07/001000



■BFS
bfs 最短経路以外は黒→https://atcoder.jp/contests/abc088/submissions/5437847
同時多発bfsロボット様→http://robonchu.hatenablog.com/entry/2019/05/05/110928
bfs(全ての近接をキューへ入れる、マスのゴールへの最短距離)→http://chiwawa-star.hatenablog.com/entry/2016/08/21/024834
​マスの白黒部分を数える(キューが空になるまで)→https://atcoder.jp/contests/aising2019/submissions/3985323
けんちょん様白黒bfs→http://drken1215.hatenablog.com/entry/2019/01/13/035500
マス(不必要部分は黒で塗る)→https://atcoder.jp/contests/abc088/submissions/2109378
マス(旅行できるか)→https://atcoder.jp/contests/abc086/submissions/2001726
マス(指定された絵が描けるか)→https://acchann.hatenablog.com/entry/2019/02/19/024728
線対称なマス→https://img.atcoder.jp/abc088/editorial.pdf
マス(条件付き探索)けんちょん様→https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e
自分より大きな値にのみ移動できる(vector<tuple<int, int, int>>, 1000000007, tie(ignore, y, x))→https://atcoder.jp/contests/abc037/submissions/719163
最短距離(black += g[i][j] == '#';, emplace)→https://atcoder.jp/contests/abc088/submissions/2109378



■マス
マス 9個内の黒の数の数え上げ(set, setはソートする必要なし, ans[cnt]++)
四方に発光する光の最大面積→http://drken1215.hatenablog.com/entry/2019/06/10/143300



■bit全探索
bit全探索 けんちょん様→http://drken1215.hatenablog.com/entry/2018/08/05/224100
スイッチと電球(defin push_back pb、 XOR、マクロ全般確認要)→https://atcoder.jp/contests/abc128/submissions/5636049



■tree
setの典型→https://atcoder.jp/contests/abc073/submissions/5365185
ベルマンフォード・ワーシャルフロイド→http://dai1741.github.io/maximum-algo-2012/docs/shortest-path/
ダイクストラ法ミスティ様→https://misteer.hatenablog.com/entry/Dijkstra_1
友達の友達→https://qiita.com/nomikura/items/cf0ed4832854573323d7



■2つ以上のソート
ペアのソート けんちょん様→http://drken1215.hatenablog.com/entry/2019/05/15/012700
3つのソート(文字列ソート込み)→https://atcoder.jp/contests/abc128/submissions/5643717



■dp
カードのdp→http://arc060.contest.atcoder.jp/data/arc/060/editorial.pdf
3次元dp→https://qiita.com/nomikura/items/98e53c1eb0be7af15847
we love AGC アルメリア様(文字を数字へ置き換え、NGパターンの全列挙)→https://betrue12.hateblo.jp/entry/2019/03/24/224052
dpの典型(壊れた階段上り)→https://atcoder.jp/contests/abc129/submissions/5871263



■XOR
XOR(XORの引き算、実験大切、累積和)→http://drken1215.hatenablog.com/entry/2019/03/09/224100



■問題文を言い換える
投げ刀(順番を変えても問題無し)→https://img.atcoder.jp/abc122/editorial.pdf
2で割るのと3倍(3倍しても2で割れる数は変わらない)→http://drken1215.hatenablog.com/entry/2018/06/16/231700
カンガルーが家に帰る(n*(n+1)/2>=X 厳密にどれを割り当てるまで考える必要なし) https://atcoder.jp/contests/abc056/submissions/1167080
2で割りまくって良い→https://atcoder.jp/contests/abc019/submissions/5538871
変なジャンケン(実験大事)→http://arc062.contest.atcoder.jp/data/arc/062/editorial.pdf
偶数番目時数番目の2パターン→https://img.atcoder.jp/arc072/editorial.pdf
マスの圧縮→https://img.atcoder.jp/arc101/editorial.pdf
★直線上の正負の最短移動距離(両端に到達すれば良い、昇順に並んだ制約)→https://img.atcoder.jp/arc101/editorial.pdf
https://tqk.hatenablog.jp/entry/ABC107-1
.の人は一個前も.(8方向探索)→https://atcoder.jp/contests/abc039/submissions/me



■テクニック
set,autoを使う理由→https://qiita.com/tell0120xxx/items/84b8750ba87cd2ab2633
setとmapの違い→https://codezine.jp/article/detail/6186
nposの使い方 →https://qiita.com/yakigac/items/8797cc256d6dcbd5e36a
findの使い方→https://www.sejuku.net/blog/49318
memset→http://techtipshoge.blogspot.com/2010/07/memsetmemcpy.html?m=1
emplace_backとpush_back→https://qiita.com/brackss1/items/e92da6458172397f7225
write and erase(set)→https://atcoder.jp/contests/abc073/submissions/1576894
pair→http://stlalv.la.coocan.jp/pair.html
auto→https://cpprefjp.github.io/lang/cpp11/auto.html
set→http://vivi.dyndns.org/tech/cpp/set.html
vectorのソート→http://7ujm.net/stl/sort.html
ユニーク→https://qiita.com/ysk24ok/items/
ローヤーバウンド、アッパーバウンド→https://qiita.com/ganariya/items/33f1326154b85db465c3
for文→#define rep(i, n) for (int i = 0; i < (int)(n); i++)http://vivi.dyndns.org/tech/cpp/range-for.html
標準出力→cout<<ans<<endl; ​
アキュムレート→http://kowaimononantenai.blogspot.com/2013/11/stdaccumulatevectorstdaccumulate3.html?m=1
三角形可能判定→ if( accumulate(L.begin(), L.begin() + L.size() - 1, 0) > L.back() ){
rbegin→https://marycore.jp/prog/cpp/reverse-iterator-rbegin-rend/
listとvectorの違い→http://vivi.dyndns.org/tech/cpp/list.html
map→http://vivi.dyndns.org/tech/cpp/map.html
front→https://cpprefjp.github.io/reference/vector/vector/front.html
bitset→https://cpprefjp.github.io/reference/bitset/bitset.html
1000000007の余り→https://qiita.com/drken/items/3b4fdf0a78e7a138cd9a
breakとcontinueの違い →http://pprog.blog.jp/archives/4042403.html
vectorの任意の場所をerase→http://vivi.dyndns.org/tech/cpp/vector.html#pop_back
拡張for文→https://qiita.com/su_/items/9543a60937d527698b40
rbegin,rendを使った降順ソート→https://sscrisk.hatenablog.com/entry/20110212/1297493654
C++演算子http://www.c-lang.org/operator.html
3つのソート→http://dai1741.github.io/maximum-algo-2012/docs/cpp-sort/
文字列入力は速度の観点からscanfを推奨→http://abc037.contest.atcoder.jp/data/abc/037/editorial.pdf
emplace_back/emplace→https://marycore.jp/prog/cpp/emplace-functions/
素因数分解https://www.mk-mode.com/blog/2012/08/08/08002014/#
0LL→long long型の0
gcd→https://qiita.com/EqualL2/items/6e3de4d1d09e2e5f3611
三項演算子https://mementoo.info/archives/785



■その他
環境構築→https://qiita.com/AokabiC/items/e9312856f588dd9303ed
ruby,pythonを使えた方が良い理由→https://www.slideshare.net/mobile/chokudai/arc045
アルゴリズムの擬人化 ちょくだい様→https://chokudai/codefestival-gijinka
アルゴリズムとは? けんちょん様→https://qiita.com/drken/items/f909b79ee03e679c7142
蟻本初級 けんちょん様→https://qiita.com/drken/items/e77685614f3c6bf86f44
bit dp入門(文字列として受け取らないといけない)→https://pekempey.hatenablog.com/entry/2015/12/09/000603



■未理解
FT machine→https://img.atcoder.jp/abc082/editorial.pdf
決まった頂点を通る木→https://img.atcoder.jp/abc070/editorial.pdf
https://qiita.com/ryoooooory/items/3b506cc4cb560965f183
双方向に移動可能なら道
decrease→https://atcoder.jp/contests/abc068/tasks/arc079_b
トランプの挿入けんちょん様(最長増加部分列)→http://drken1215.hatenablog.com/entry/2019/04/17/231900
別解説→https://blog.kotet.jp/2017/08/abc-006-d/