HUPC 2019 日記

1日目 https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2019Day1/problemsCinnamorollさんとasako9494さんと同じチームで出た。Cの構文解析は誰もやりたがらないので放置された。DはO(1)でできそう感を感じつつ制約がO(N)を許容しているのでO(N)で通し…

HUPC 2019 Day1 F: グリッドの番号 (Grid Number)

問題 https://onlinejudge.u-aizu.ac.jp/beta/room.html#HUPC2019Day1/problems/F 解法 1から2nまでの数を順番にグリッドに詰めていく。このとき、各状態からの遷移は上段に詰めるか下段に詰めるかの2通りの遷移がある。各状態を、「下段より右側に出ている…

ICFP Contest 2019 振り返りメモ

osak.hatenablog.jp シミュレーターを作ってました。が、そこそこバグらせて結構迷惑をかけてしまいました…… 雑感 入出力を処理する実装がAI側とシミュレーター側にそれぞれ存在していて、片方で直したバグがもう片方(主に僕の方ですが…)で直っていなかっ…

今日復習した問題

B - Splatter Painting クエリを逆順にやればいいというのは「Pruned Landmark Labeling で見た!」という気持ちでやった。 use std::collections::VecDeque; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usiz…

AGC 014 C - Closed Rooms

問題 atcoder.jp 解法 もし、魔法の操作の順序が入れ替わっていて、魔法が「Kこの部屋を選んで解放し、その後、K回移動する」という操作だったら、移動しながら部屋を開けていけば良いので、非常に単純なBFSになる。ここに落とし込むために、操作を以下のよ…

AtCoder Beginner Contest 132 F - Small Products

問題 atcoder.jp 解法 ナイーブなDPを考えると、遷移する先が区間に分けられ、しかもその区間の数は であることに気づく。DPの際に区間ごとにまとめて遷移させれば良い。 コード use mod_int::ModInt; use std::collections::BTreeSet; const MOD: usize = 1…

AtCoder Beginner Contest 132 E - Hopscotch Addict

問題 atcoder.jp 解法 ステップが3の倍数でないとゴールできない幅優先探索なので、頂点を3倍に増やせば良い。 コード use std::collections::VecDeque; const INF: u64 = std::u64::MAX / 2; fn main() { let s = std::io::stdin(); let mut sc = Scanner {…

AtCoder Beginner Contest 132 D - Blue and Red Balls

問題 atcoder.jp 解法 K個の青いボールをi個の区間に分け、かつ、全ての区間が1個以上ボールを含むような青いボールの分け方は である。同様に考えて赤いボールの分け方を求め、この2つの積が答えになる。 const MOD: usize = 1e9 as usize + 7; fn main() {…

今日解いた問題

atcoder.jpバグらせずに実装するのが地味に大変な問題だと思う。 use std::cmp; use std::collections::BTreeMap; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let h: usize = sc.read(); let w: usize = sc.read(); …

今日解いた問題

atcoder.jpatcoder.jp

VSCode で Rust で競技プログラミングをするときの設定

拡張機能と RLS を入れる task の登録 { // See https://go.microsoft.com/fwlink/?LinkId=733558 // for the documentation about the tasks.json format "version": "2.0.0", "tasks": [ { "label": "cargo run", "type": "shell", "command": "RUST_BACKT…

今日解いた問題

問題 atcoder.jpT経過後の蟻の位置は分かるので、蟻0がどの位置に対応するかを考える。これは座標0を通過した蟻の数で分かる。 コード fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let l: …

Google Code Jam 2019 Round 1B - Fair Fight

問題 codingcompetitions.withgoogle.com数列 が与えられる。 となるような (l, r) の組の数を求めよ。 解法 となるような (l, r) の組の数を求めて全体から引くことにする。 と は c と d を入れ替えることで独立に同じように求めることができる。各 i につ…

Google Code Jam 2019 Round 1B - Draupnir

問題 codingcompetitions.withgoogle.com要素数 6 の数列 がある。クエリとして D を出力すると、 が与えられる。クエリを 2 回投げた後に を出力せよ。 解法 は入力を 64bit 整数に収めるためのものではなく、解法の重要なポイントになる。D=200 で得られる…

Rust LT #4 で LT をした

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

AtCoder Jobs で転職した

prd-xxx.hateblo.jpこの記事を読んで思い出しましたが、僕も2ヶ月ほど前に AtCoder Jobs を利用して転職したので、その時のことを書きます。この転職に満足しているので、他の人が AtCoder Jobs を使う際の参考になれば幸いです。 AtCoder Jobs を使う前 前…

今日解いた問題

E - Prefix-free Game atcoder.jp実験によって grundy 数を求めるのはよく見る気がする。 use std::collections::{BTreeMap, BTreeSet}; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let l…

エクサウィザーズ 2019 D - Modulo Operations

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

エクサウィザーズ 2019 E - Black or White

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

フルマラソンを走った時のメモ

初めてフルマラソンを走った。それなりに準備していったが、思ったとおりには走れなかった。今後も続けていきたい感じはするので、メモを残しておく。準備として、本番前の2ヶ月は毎週1回20km走った。近所を走るのは苦手なので、毎回わざわざ水戸まで行って…

キーエンス プログラミング コンテスト 2019: E - Connecting Cities

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

Codeforces Round #541 (Div. 2) E. String Multiplication

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

AtCoder Regular Contest 102 D - All Your Paths are Different Lengths

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

「第3回 RCO日本橋ハーフマラソン 予選」の復習

atcoder.jpこのコンテストに出たのですが、散々な結果だった。ただ、終わった後に流れてきた解法を見ると結構シンプルなものが多かったので、復習した。 A - ツーリストXの旅行計画 A - ツーリストXの旅行計画 分散が出てきてややこしい気持ちになるが、平均…

Rust の Vec の sort_by_key は気をつけて使おう

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

AtCoder Problems を色々いじった

この記事は AtCoder関連サービス Advent Calendar 2018 - Adventar の一部です。毎年なぜか12月になるとウェブアプリを触りたくなる。 kimiyuki さんが DB に index を張ってくれた なぜか今まで index を張っていなかったのが無事張られた。これによって、…

AGC 029 C - Lexicographic constraints

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

AGC 029 D - Grid game

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

AtCoder Regular Contest 059 E - キャンディーとN人の子供 / Children and Candies

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

CODE FESTIVAL 2018 qual A D - 通勤

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