01/18やったこと

kenkoooo.hatenablog.com AtCoder E - Snuke Line Submission #9550850 - AtCoder Regular Contest 068 F - Xor Sum 3 Submission #9550587 - AtCoder Beginner Contest 141 E - Ball Coloring Submission #9551600 - AtCoder Regular Contest 073 E - Bichr…

01/14やったこと

kenkoooo.hatenablog.com AtCoder E - Non-triangular Triplets AtCoder E - Non-triangular Triplets 何もわからないので、逆によく考えると一つしか解法が思い浮かばないので迷わず解けた。Submission #9513548 - NIKKEI Programming Contest 2019-2

01/13やったこと

kenkoooo.hatenablog.com AtCoder E - Avoiding Collision E - Black or White E - Sorted and Sorted F - Enclosed Points E - Weights on Vertices and Edges B - Removing Blocks AtCoder E - Avoiding Collision Submission #9500895 - AtCoder Regular …

第二回全国統一プログラミング王決定戦予選 E - Non-triangular Triplets

問題 E - Non-triangular Triplets 解法 とりあえず 2N ... 3N-1 は c に割り当てる。というようにできるとよい。ここで、 としたいが、これだけでN要素は作れないので、前半と後半に分けて別々に構築する。 コード fn main() { let (r, w) = (std::io::stdi…

01/12やったこと

kenkoooo.hatenablog.com AtCoder C - Nuske vs Phantom Thnook D - Friction F - Pass C - Differ by 1 Bit D - Game on Tree E - Connected? AtCoder C - Nuske vs Phantom Thnook Submission #9438810 - AtCoder Grand Contest 015 D - Friction Submissi…

01/05やったこと

kenkoooo.hatenablog.com AtCoder C - ABland Yard F - Minimum Bounding Box C - Remainder Game E - Antennas on Tree D - 桁和 / Digit Sum AtCoder C - ABland Yard atcoder.jpアイディアの正当性を示すのは非常に難しく感じる。実装はシンプル。atcoder…

01/04やったこと

kenkoooo.hatenablog.com AtCoder D - Snuke Numbers E - キャンディーとN人の子供 / Children and Candies C - ABland Yard D - K-th K C - Swaps B - Holes F - Lotus Leaves AtCoder 昨日やり残した問題もまとめて片付ける。 D - Snuke Numbers atcoder.j…

2020 年の目標

AtCoder 橙色 昨年も目指していたが、橙色はおろか黄色に戻ることすらできなかった。 転職やその他のライフイベントがあり、忙しかったという言い訳をしておく。 黄diff問題を練習するようになってからコンテストでも黄パフォがコンスタントに出せるようにな…

AGC041 C - Domino Quality

問題 atcoder.jp コンテスト中の解法 実験すると雑な全探索でn=4, 5, 6が求まる。n=7は計算が終わらなかった。これを組み合わせるとn=7以外は構築可能になる。 n=7を気合で手作りする。 コンテスト後の解法 全探索を高速化してn=7を求めたい。 縦向きのドミ…

API Gateway -> NLB -> ECS でつなぐ

Network Load Balancer を立てる Scheme => internal Listener => TLS AZ は適当に Certificate は事前に準備しておいたものを使う。 Target group => create new protocol => TCP port => 80 healthcheck protocol => HTTP path => コンテナ内のヘルスチェ…

AtCoder Problems を支える技術 (2019年版)

adventar.org AtCoder Problems とは? AtCoder Problems とは AtCoder の提出をクロールして管理しているウェブアプリです。https://kenkoooo.com/atcoder/ AtCoder Problems の主な機能 AtCoder の各問題について自分が AC したかどうかを管理 他のユーザ…

2019 JUST Programming Contest B. Memory Management System

問題 codeforces.com長さmの線分がとn個の区間があります。q個のクエリが与えられます。i番目のクエリでは整数k_iが与えられるので、線分上のn個の区間と重ならない長さk_i以上の区間で最も右にあるものを出力してください。 解法 空の集合Sを用意する。空い…

Project Euler 684 Inverse Digit Sum

問題 projecteuler.net 解法 各桁の数の和がxとなるような最小の整数 s(x) は必ず一番上の桁以外は全て9となる。 よって s(x) は以下のようになる。s(x) の和 S(x) を考える。 S(20)=1074だが、これは以下のようにして求まる。 s(1) = 1 ... s(9) = 9 s(10) …

ABC143 F - Distinct Numbers

問題 atcoder.jp 解法 K枚ずつ食べる時の最大の回数を求めるのではなく、H回食べるときの最大の1回に食べる枚数を求めることにする。 とする。H回食べると決めたとき、同じ数字を同時に食べないように選ぶ1回あたりの食べる枚数はとなる。例えば A = [1,1,1,…

AGC039 C - Division by Two with Something

問題 atcoder.jp 解法 各操作を観察すると、どちらも「最も下のビットをpopして反転して最も上にpushする」と言い換えられる。これをN回繰り返すと元の数のビットを反転させたものが得られるので、2N回繰り返すと必ず元の数が得られる。よって繰り返して元の…

AGC038 C - LCMs

問題 atcoder.jp 解法 mobile.twitter.com自分の学習のために式を書き直してみたが全く同じになってしまった……ここで とすると なので コード use mod_int::ModInt; const MOD: usize = 998244353; fn main() { let s = std::io::stdin(); let mut sc = Scan…

Project Euler 679 Freefarea

問題 projecteuler.net長さ n で A, E, F, R からなる文字列のうち、4つのキーワード FREE, FARE, AREA, REEF を各1回ずつ含むものはいくつあるか。n=30について求めよ。 解法 全ての文字列を陽に持つ必要はなく、(各キーワードを持っているかどうか, 接尾辞…

2019/09/23

atcoder.jp use std::collections::{BTreeMap, BinaryHeap, VecDeque}; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let mut graph = vec![vec![]; (1 << (n + 1)) - 1]; let mut inverse …

AGC036 B - Do Not Duplicate

問題 atcoder.jp 解法 s の先頭の数字と同じ数字が来たら s が空になることを考える。例えば a(0)=a(i), a(i+1)=a(j) のとき、s は i で空になり、jで再び空になる。鳩の巣原理より a0 が何周目で再び先頭になるかO(N)で求めることができる。a0 が先頭になっ…

ABC139 F - Engines

問題 atcoder.jp 解法 答えとなるベクトル v があったとして、それを作るには v となす角が 90° 未満のベクトル集合のみを考えれば良い。よって、最終的に使われるベクトル集合は偏角ソートしたときに連続した区間になっているはずである。Nが小さいので全て…

ABC139 E - League

問題 atcoder.jp 解法 順番を並び替えることを考える余地はなく、「今日試合ができる組は全員試合をする」を毎日繰り返す。 コード use std::cmp::max; use std::collections::VecDeque; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdi…

飲酒プログラミングコンテストに参加した

注意(2019/09/01 追記) この記事は過度な飲酒を推奨するものではありません。飲酒プログラミングコンテストでは速く飲むことを重視するあまり、過度に飲酒を行ってしまう傾向があります。開催する場合、その危険性を十分認識した上で自己責任で行ってくだ…

ABC137 D - Summer Vacation

問題 atcoder.jp 解法 どの仕事も1日で終わるので、もらえる金額が大きければ大きいほどよい。よってもらえる金額が大きい方から処理していく。もらえる金額が同じ仕事同士では、振込が早い仕事よりも遅い仕事の方が候補日が限られるので、遅い仕事から処理…

AtCoder Beginner Contest 136 F - Enclosed Points

問題 atcoder.jp 解法 各点について、自分の (左上、右上、左下、右下) にある点の数を数える。これは 座標圧縮 => Fenwick Tree で O(N logN) でできる。各点について、その点を含まない長方形の数は以下の合計である。 右下の空でない点集合の数 * 右上の…

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…