tookunn’s diary

主に競技プログラミング関係

メモ

最大流 蟻本読んだメモ

参考にした資料: 蟻本第2版 P188~P191 ネットワークフロー入門 http://hos.ac/slides/20150319_flow.pdf 最大流問題 始点Sから終点Tまで各辺の容量を超えることなく流すことが出来る最大の流量を求める。 定義 有向グラフ,頂点の集合,辺の集合 始点,終点 …

RUPC2016 Day1 F リレー / Relay

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=F解説見て通しました。 考察 基本的には公式解説にある通りの考え方で何となく理解しましたが,オイラーツアーを行う実装がイメージできなかったので,mayokoさんの解説…

AtCoderBeginnerContest 010 D 浮気予防

問題 abc010.contest.atcoder.jp解説見て蟻本写経して通しました。 考察 当初、複数のを含む連結成分を探して,橋を見つけてそれを消していけば良いのかなぐらいに考えてたけど、そこから何も分からなかったので解説を見て最大フローを求める問題と分かった。…

AtCoderRegularContest 065 F シャッフル / Shuffling

問題 arc065.contest.atcoder.jpさすがF問題ということで解説見て,解説放送見て,他の方の提出コードを見て,時間をかけてやっと理解(完全ではない)出来ました。復習必須に感じたのでメモとして記事にします。 考察 まず、まとめられるはまとめていく。 まとめ…

CODE FESTIVAL 2016 qual B D

問題 code-festival-2016-qualb.contest.atcoder.jp 考察 本番中は貪欲っぽいな思って、色々考察して試して時間切れを迎えた。どういう発想で解法に近づくのかを記録しておく。・問題概要から数列Aのある要素はその要素の前の要素によって操作が変わる?だか…

Sparse Tableを知ったので、忘れないように。

codeforces.com この問題の想定解法がSparse Tableを使ったもので、ちゃんと理解したいなと思ったので忘備録的な感じで書きます。 色々調べながら書いているので、間違っているところがあったら指摘して頂けるとありがたいです。 Sparse Tableとは まず、Spa…

AtCoderBeginnerContest003 D AtCoder社の冬 (メモ用)

問題 abc003.contest.atcoder.jp 考え 部分点解法はX * Y = D + Lなので、X * Yの範囲内でD個のデスクを置く組み合わせ(X * Y)C(D)と残ったX * Y - Dの範囲内でL個のラックを置く組み合わせ (X * Y - D)C(L)を掛け、それを(R - X + 1) * (C - Y + 1)回掛けつ…

AtCoderBeginnerContest030 D へんてこ辞書 (メモ用)

問題 abc030.contest.atcoder.jp 考え 単語を調べるステップ数kが(1 ≦ k ≦ 10^100000)の範囲なので、long型でも収まらない。だけど今回は公式の解説でもあるように多倍長を使わずに解ける。 参考:AtCoder Beginner Contest 030 解説 一度調べた単語をもう一…

C++ scanf() scanf_s() 自分メモ

#include <iostream> using namespace std; int main() { int N; cin >> N; } みたいな感じでcin>>を使う。 競技プログラミングなどで実行速度を速くしたい時は、cinではなくscanf()を使った方が良い。 int main() { int N; scanf("%d", &N); printf("%d\n", N); } し</iostream>…