adventar.org並列二分探索、名前からして難しそうな感じがしていたが、特に難しいわけではなかった。 並列二分探索 個人的には並列という名前は正しくない気がします。普通の二分探索は次の通り。 let mut ng = 0; let mut ok = m; for _ in 0..30 { let med…

--------------------------------------------------------------------------------------------------------- --------------------------------------------------------------------------------------------------------- ---------------------------…

問題 E - Combination Lock 解法 方針としては、 区間を整理しやすいように文字列の長さを偶数にする。 区間の整理をめっちゃ頑張る 端から区間を見ていけば良いだけの状態になったら imos 法で順番に処理していき、ダメだったら NO 文字列の長さを偶数にす…

adventar.org はじめに AtCoder Problems というサービスを作っています。最近作り直しています。http://beta.kenkoooo.com/atcoder/これは AtCoder の提出を全部クロールして、一覧で見れるようにしたものです。最近は機能が増えすぎていますが・・・ソース…

adventar.org フィボナッチヒープとは この記事ではヒープは最小値を求めるものとします。フィボナッチヒープとは、フィボナッチ数の性質をうまく使ってならし計算量で高い性能を持ったヒープです。 ヒープ フィボナッチヒープ 二分ヒープ 最小値の削除 なら…

adventar.org 豆知識 この記事のタイトルでググると、まともな記事が出てきます。 退職しました 20 ヶ月ほど勤務したリクルートコミュニケーションズ (RCO) を退職しました。RCO ではウェブ広告リアルタイム配信チームで、主に高速化を頑張りました。かなり…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2829 解法 JAG の wiki に分かりやすい解説があります。2017/Practice/模擬国内予選/講評 - ACM-ICPC Japanese Alumni Group場合分けとしては以下の 3 つです 長さ 3 以上の閉路が存在する場…

問題 Picnic | Aizu Online Judge 解法 ワーシャルフロイド→巡回セールスマン→半分全列挙→個数制約付きナップサック コード import java.util import scala.io.StdIn import scala.util.Try object Main extends App { val INF: Long = 1e15.toLong val (n, …

問題 http://codeforces.com/contest/843/problem/D 解法 最初にダイクストラで距離を求めておき、各クエリごとにダイクストラで追加で増えた分の距離を計算して加算していく。各クエリごとに距離は 1 しか増えないので、キューを距離の数だけ用意すれば、ク…

問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day2&pid=G 解法 ワーシャルフロイドと巡回セールスマン問題の bit DP で、ある町の部分集合を回って戻ってくるのにかかるコストを前計算しておく。さらに、町の集合を の 2 つに…

問題 AIZU ONLINE JUDGE 解法 2次元のBITを貼る。 コード import java.util.Scanner import scala.collection.mutable.ArrayBuffer object Main extends App { val in = new Scanner(System.in) val H = in.nextInt() val W = in.nextInt() val T = in.nextI…

問題 Matryoshka Doll | Aizu Online Judge 解法 取り込まれた人形のコストを 0 として、取り込まれていない人形のコストはそのまま結果に加えるように、最小費用流のグラフを作る。 コード import java.util.Scanner import scala.collection.mutable impor…

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_d 解法 解説動画の通りにやった。最初に a 入っている時の t 秒後の砂の量は以下のように書ける。この をシミュレーションしていけば良い。 コード use std::io; use std::str; use std::usize; …

問題 https://beta.atcoder.jp/contests/arc082/tasks/arc082_c 解法 解説の通りにやった。 の意味するところを考える。これは凸包が S となるような部分集合の数である。よって求める答えは各凸包について部分集合の数を数えていけば良いが、それは難しいの…

Rust の練習 問題 http://arc080.contest.atcoder.jp/tasks/arc080_c 解法 逆から考えて、最後に先頭に追加される 2 つの数を考える。これらを前から順番に とすると、i は偶数、j は奇数であり、かつ、 が成り立つことがわかる。よって、この条件を満たす i…

復習 問題 https://csacademy.com/contest/round-34/task/point-in-kgon/ コード import java.util.Scanner; public class Main { private static final int MOD = (int) (1e9 + 7); public static void main(String[] args) { Scanner in = new Scanner(Sys…

復習 問題 CS Academy コード import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.Scanner; public class Main { private static final int MAX = 2500; private static long count(ArrayList<Integer> list, Fen</integer>…

問題 https://csacademy.com/contest/archive/task/point-in-kgon/ 解法 これを見ました。 http://kmjp.hatenablog.jp/entry/2017/06/23/0930 コード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.uti…

問題 https://csacademy.com/contest/round-36/task/bbox-count/ コード import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Collections; import java.util.NoSuchElemen…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1163GCD + 二部マッチング import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util…

問題 https://csacademy.com/contest/round-14/task/subarrays-xor-sum/ 解法 eha くんに解説をしてもらってようやく理解した。各ビットごとに独立なので、ビットごとに分ける。0と1のみの数列の長さ k 以下の数列の xor の合計値をとりたい。 i 番目の数を…

無意味にハマった。 Jenkins 側の設定 とりあえず Pipeline を使っているものとする。「ビルドのパラメータ化」にチェックを入れておくと、外部からのパラメータを受け取れるようになる。例えばパラメータ "branch" を定義していると、Pipeline Script の Gr…

非常に当たり前だが、以下のコードでは "closed" が出力されることはない。 package sandbox; import java.io.Closeable; import java.io.IOException; public class Sandbox { public static void main(String[] args) throws Exception { String a = get()…

問題 http://agc013.contest.atcoder.jp/tasks/agc013_c 解法 解説の通りにやった。Rustでは map を使って for を消せることを学んだ。 コード use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use st…

問題 https://csacademy.com/contest/round-29/task/root-change/ツリーの各頂点 i について、 i を根とした時に切断してもツリーの高さが変化しない辺の数を出力してください。 解法 editorial のコード通りです。いわゆる全方位木dpと呼ばれる手法です。 …

Rust でやってみました。標準入出力は他の人のを拝借してきたけど、 println マクロは出力ごとに flush しているようなので注意が必要そう。もっときれいに書けるようになりたい。 A - Grouping http://abc062.contest.atcoder.jp/tasks/abc062_a fn next() …

問題 D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoderRust で Dinitz を実装した コード use std::fmt::Debug; use std::io; use std::io::{Read, Stdin}; use std::str; use std::str::FromStr; use std::usize; use std::cmp; use std::collections…

問題 http://codeforces.com/contest/804/problem/Cn 頂点のツリー T と m 種類のアイスクリームがあります。T の各頂点はアイスクリームの集合をもっています。あるアイスクリーム i をもつ頂点同士は、連結なサブグラフになっています。m 頂点の無向重みな…

自分用メモ。使っている GPU は NVIDIA Tesla K80 を 1 枚。 # CUDAやドライバ諸々入れてもらう sudo curl -O http://developer.download.nvidia.com/compute/cuda/repos/ubuntu1604/x86_64/cuda-repo-ubuntu1604_8.0.61-1_amd64.deb sudo dpkg -i ./cuda-re…

解法 操作Aと操作Bは完全に対称な操作であることが分かる。操作Aをしまくって1箇所に集め、操作Bをしまくって復元すれば良い。 コード import java.util.ArrayList; import java.util.Collections; public class ReverseMancala { private int N; private Ar…