rust.connpass.comこれに参加して5分枠で発表した。 テーマ決め AtCoder Problems というサービスのバックエンドを Rust で書いていたので、それについて発表しようと思った。github.com技術的にはそこまで難しくなく、やっていることはドキュメントを読めば…

問題 atcoder.jp 解法 解説にあるとおり、ある数が使われた後、その数より大きい数を使ったとしても剰余には影響しないので、大きい数から順番に見ていって数列に詰めていくことを考える。i番目(0 コード const MOD: usize = 1e9 as usize + 7; fn main() { …

問題 atcoder.jp 解法 毎回 (i個目を取る時に白が無くなっている確率) + (i個目を取る時に白も黒も無くなっていない確率)/2 を出力する。 (i 個目を取る時に白が無くなっている確率) = (i-1個目を取る時に白が無くなっている確率) + (i-1個目で最後の白を取…

問題 atcoder.jp 解法 の値が大きい方から小さい方に辺を張ると考えても良いので、そう考える。 となるような i, j, k を考え、頂点kからiかjのどちらかに辺を引くことを考える。 i-j 間のコストは j-k 間のコストは i-k 間のコストは の場合、 だから だか…

問題 http://codeforces.com/contest/1131/problem/Eある文字列 S と T が与えられた時、文字列 S の長さを m として S と T の積を と定義する。文字列 p1, p2, ..., pN が与えられるので の中で同じ文字が連続して現れる回数の最大値を求めよ。 解法 pN 以…

問題 atcoder.jp 解法 頂点 v から v+1 へ、長さ 0 の辺と、長さ の辺を張る。これによって、 の長さのパスが存在することになる。次に、頂点を の順番で見ていく。頂点 0 から頂点 v へは の長さのパスが存在するので、頂点 v から頂点 n-1 へ長さ t の辺を…

当たり前っちゃ当たり前だが、 vec.sort_by_key(|&value| heavy_function(value)); みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが遅くなる。これは sort_by_cached_key でなんとかなるっぽい。sort_by_key は This sort is s…

問題 beta.atcoder.jp 解法 できるだけ、辞書準最小のリストを作ることを目指す。例えばA=[2, 2]の時は["aa","bb"]でもよいが、["aa", "ab"] が辞書準最小のリストになる。この時、一つ前の要素よりも大きい時は、一つ前の文字列の後ろに "a" を連続で追加す…

問題 beta.atcoder.jp 解法 まず先手が能動的にパスを選択することはありえない。なので、後手は先手の進行方向に障害物を置きさえすれば良い。両プレーヤーが能動的にパスを選択せずにxターンが終了した時の位置を (x, y) とする。このとき、後手は適当にパ…

問題 beta.atcoder.jp 解法 求める値は以下の式で表される。これは解説動画の変形を駆使して、以下のように変形できる。よって以下のような動的計画法で解ける。 コード use self::mod_int::ModInt; const MOD: usize = 1e9 as usize + 7; fn main() { let s…

問題 beta.atcoder.jp 解法 公式解説を見ながらやった。地点 i で給油した時、残り容量は必ず f になる。x[i] + f - t までは少なくとも t 以下にはならないので、 x[i] から x[i] + f - t までの間にある給油所は、あってもなくても良い。また、iのあと給油…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2893 解法 橋を全列挙し、それぞれについて削除したときの cost を求め、ソートすれば良い。具体的な実装としては、 橋を列挙する。 橋を含まない連結な部分グラフを潰して 1 つの頂点とし、…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2891 解法 N 頂点 N 辺のグラフ（いわゆる「なもりグラフ」）は1つだけ閉路があり、その閉路に木がいくつか連結している形になる。各クエリの頂点の両方とも閉路に含まれている場合2本切断す…

問題 beta.atcoder.jp 解法 が全て より小さくなるような x、すなわち、 となるような x の最大値を求めたい。 で x は a より大きいとすると、 を満たす x を求めれば良い。 コード /// Thank you tanakh!!! /// https://qiita.com/tanakh/items/0ba42c7ca3…

問題 beta.atcoder.jp 解法 を足したり引いたりしてを作る。 を足したり引いたりして 1 を作る。 にすることを目指すのではなく にすることを目指す。 であることは である。 なので、各 p について独立に考えればよいということになる。 コード /// Thank y…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2900 解法 と並んでいるのを としたいが、これが成り立っていないとする。 が成り立っている時、 となっているので、 を動かすことは得にならない。よって 以降について問題を解けば良い。が…

問題 C - Median Sum 解法 解説の通り。空でない部分列の数は 個存在するが、部分列の和が x となるような部分列の構成方法の数え上げは動的計画法で で求まる。だが、これでは間に合わない。中央値は配列の合計の 1/2 以上になるということに気づくと、部分…

問題 https://beta.atcoder.jp/contests/yahoo-procon2018-final/tasks/yahoo_procon2018_final_a 解法 ある整数 i について配列内の i と互いに素な整数の数を数えるのは大変そうなので、i と互いに素でない数を数えることにする。i を素因数分解し、例えば…

問題 https://beta.atcoder.jp/contests/abc107/tasks/arc101_b 解法 完全に解法の通り。 全ての連続部分列のうち、中央値が x 以上であるものがいくつあるかを考える問題になる。 数列の中央値が x 以上である。 => 数列の各要素を x 以上なら 1 そうでなけ…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3022 解法 雰囲気から、関節点を求める機運が高まるが、実際の問題はその後に最後の答えを出力するパートである。http://web-ext.u-aizu.ac.jp/circles/acpc/commentary/ACPC2017Day2/J.pdf…

問題 https://beta.atcoder.jp/contests/arc039/tasks/arc039_d 解法 橋を2回通らずに A->B->C の移動が出来るかという問題になる。まず橋を検出し、それらを取り除くと、グラフはいくつかの連結成分に分かれる。各連結成分内では頂点間を移動する経路が常に…

問題と解法 記憶力があれなので同じ問題を何度も解く。kenkoooo.hatenablog.com コード use std::cmp; use std::collections::BTreeSet; macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter…

問題 https://beta.atcoder.jp/contests/arc083/tasks/arc083_c 解法 いつもありがとうございます。頂点 v を根とする部分木で、頂点 v と同じ色の頂点の重みの合計は x[v] だが、同じ色でない頂点の重みの合計は小さければ小さいほどよい。よって、「頂点 v…

問題 https://beta.atcoder.jp/contests/bcu30/tasks/bcu30_f 解法 全く同じ問題が CodeChef で出ている。https://ei1333.hateblo.jp/entry/2017/06/04/151131 コード use std::ops::*; const MOD: usize = 1e9 as usize + 7; fn main() { let mut sc = Scan…

問題 https://beta.atcoder.jp/contests/arc081/tasks/arc081_d 解法 解説の通り。最大長方形を求めるのは AOJ で学べた。http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B コード use std::cmp; use std::collections::VecDeque; trait T…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_B 解法 各列についてヒストグラムに内接する最大長方形を求める。 コード use std::cmp; use std::collections::VecDeque; trait TopQueue<T> { fn top(&self) -> &T; } impl<T> TopQueue<T> fo</t></t></t>…

問題 https://beta.atcoder.jp/contests/arc073/tasks/arc073_c 解法 解説のとおりだが、個人的には理解が難しかった。（分かると簡単シリーズ） 最小のボールが青、最大のボールが赤のとき 最小のボールを持つ青は、残りのボールをできるだけ小さくしたい。…

問題 https://beta.atcoder.jp/contests/arc077/tasks/arc077_c 解法 x を設定することによって切り替えが高速化している区間を持っておく。 x を 1 増加させるとそれらの区間の切り替え時間はそれぞれ 1 ずつ短くなる。 コード use std::cmp; use std::coll…

問題 https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_c 解法 解説が全く理解できなかったので下記ブログを参考にした。ありがとうございます。http://fluffyowl.hatenablog.com/entry/2018/07/31/00…

問題 https://csacademy.com/contest/archive/task/growing-segment/ 解法 いつもありがとうございます。 削除しても大丈夫な辺を下から見ていく x[i] -> x[i+1] を削除するときことを考える x[i+1] は削除して問題ないので消す。 x[i+2] は消せるか？ (x[i]…