2020 年の目標
AtCoder 橙色
- 昨年も目指していたが、橙色はおろか黄色に戻ることすらできなかった。
- 転職やその他のライフイベントがあり、忙しかったという言い訳をしておく。
- 黄diff問題を練習するようになってからコンテストでも黄パフォがコンスタントに出せるようになったので、この練習をちゃんと続ければ行ける気がする。
やること
- 平日4問ずつ問題を解く
英語
- 英語が公用語の会社で働き始めて3年目になり、さすがに苦手意識は無くなってきたが、特に得意になったという気もしない。
- 仕事の文脈では普通にコミュニケーションは取れるが、いまだにコストを感じる。
- 例えば、他の人に実装してほしいものがある時に、それを英語で説明するよりも自分で実装してしまった方が速いという場面が割とある。これではチームで働く意味がない。
やること
BBC Learning English - News Reportを1日1話ずつやる。
中国語
やること
「口を鍛える中国語作文」を1日1ページずつやる。
AGC041 C - Domino Quality
問題
コンテスト中の解法
- 実験すると雑な全探索でn=4, 5, 6が求まる。n=7は計算が終わらなかった。これを組み合わせるとn=7以外は構築可能になる。
- n=7を気合で手作りする。
コンテスト後の解法
全探索を高速化してn=7を求めたい。
- 縦向きのドミノと横向きのドミノが同数であることが分かる。
- 縦向きのドミノの個数をx、横向きのものをyとすると、各ドミノの行へのクオリティの寄与の合計は2x+y、各ドミノの列へのクオリティの寄与の合計はx+2yなので、x+2y=2x+yよりx=yである。
- n=7のとき縦横各7枚ずつのドミノが必要になる。
- まず縦に7枚置き、次に空いているところに横に7枚置く全探索で十分高速にn=7が求まる。
コード
use std::collections::BTreeSet; const S4: [[char; 4]; 4] = [ ['a', 'b', 'e', 'e'], ['a', 'b', 'f', 'f'], ['g', 'g', 'c', 'd'], ['h', 'h', 'c', 'd'], ]; const S5: [[char; 5]; 5] = [ ['a', 'c', 'd', '.', '.'], ['a', 'c', 'd', '.', '.'], ['b', 'f', 'f', 'g', 'g'], ['b', '.', 'e', 'h', 'h'], ['i', 'i', 'e', 'j', 'j'], ]; const S6: [[char; 6]; 6] = [ ['a', 'd', 'g', 'g', '.', '.'], ['a', 'd', 'h', 'h', '.', '.'], ['b', 'e', 'i', 'i', '.', '.'], ['b', 'e', '.', '.', 'j', 'j'], ['c', 'f', '.', '.', 'k', 'k'], ['c', 'f', '.', '.', 'l', 'l'], ]; const S7: [[char; 7]; 7] = [ ['a', 'd', 'f', '.', '.', '.', '.'], ['a', 'd', 'f', '.', '.', '.', '.'], ['b', 'e', 'g', '.', '.', '.', '.'], ['b', 'e', 'g', '.', '.', '.', '.'], ['c', '.', '.', 'h', 'h', 'i', 'i'], ['c', '.', '.', 'j', 'j', 'k', 'k'], ['.', 'l', 'l', 'm', 'm', 'n', 'n'], ]; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock()); let n: usize = sc.read(); if n == 2 { println!("-1"); return; } else if n == 3 { sc.write("aa.\n"); sc.write("..b\n"); sc.write("..b\n"); return; } let mut ans = vec![vec!['.'; n]; n]; let m = n / 4; for k in 0..m { for i in 0..4 { for j in 0..4 { ans[k * 4 + i][k * 4 + j] = S4[i][j]; } } } match n % 4 { 0 => {} 1 => { assert!(n >= 5); for i in 0..5 { for j in 0..5 { ans[n - 5 + i][n - 5 + j] = S5[i][j]; } } } 2 => { assert!(n >= 6); for i in 0..6 { for j in 0..6 { ans[n - 6 + i][n - 6 + j] = S6[i][j]; } } } 3 => { assert!(n >= 7); for i in 0..7 { for j in 0..7 { ans[n - 7 + i][n - 7 + j] = S7[i][j]; } } } _ => unreachable!(), } for i in 0..n { for j in 0..n { sc.write(format!("{}", ans[i][j])); } sc.write("\n"); } } fn naive(n: usize) -> Vec<Vec<char>> { let mut map = vec![vec!['.'; n]; n]; if put(0, 0, &mut map, true) { map } else { unreachable!(); } } fn put(depth: usize, pos: usize, map: &mut Vec<Vec<char>>, first: bool) -> bool { let n = map.len(); if depth == n { if first { rotate(map); if put(0, 0, map, false) { return true; } rotate(map); return false; } else { return is_valid(map); } } for pos in pos..(n * n) { let i = pos / n; let j = pos % n; if j + 1 < n && map[i][j] == '.' && map[i][j + 1] == '.' { let c = (depth as u8 + 'a' as u8 + if first { 0 } else { n as u8 }) as char; map[i][j] = c; map[i][j + 1] = c; if put(depth + 1, pos + 1, map, first) { return true; } map[i][j] = '.'; map[i][j + 1] = '.'; } } false } fn rotate(map: &mut Vec<Vec<char>>) { let n = map.len(); let clone = map.clone(); for i in 0..n { for j in 0..n { map[i][j] = clone[j][i]; } } } fn is_valid(map: &Vec<Vec<char>>) -> bool { let n = map.len(); for row in 0..n { let mut set = BTreeSet::new(); for col in 0..n { if map[row][col] == '.' { continue; } set.insert(map[row][col]); } if set.len() != 3 { return false; } } for col in 0..n { let mut set = BTreeSet::new(); for row in 0..n { if map[row][col] == '.' { continue; } set.insert(map[row][col]); } if set.len() != 3 { return false; } } true } pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>); impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) { use std::io::Write; self.1.write(s.as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
API Gateway -> NLB -> ECS でつなぐ
Network Load Balancer を立てる
ECS コンテナを NLB の配下に入れる
- Create service でサービスを立ち上げる際に、NLB を指定する。
NLB からコンテナインスタンスへ穴あけする。
先程設定した AZ の IP をセキュリティグループで許可する。
AtCoder Problems を支える技術 (2019年版)
AtCoder Problems とは？
AtCoder Problems とは AtCoder の提出をクロールして管理しているウェブアプリです。
AtCoder Problems の主な機能
- AtCoder の各問題について自分が AC したかどうかを管理
- 問題の検索
- AC/非ACで絞り込み
- AtCoder公式の点数で絞り込み
- 独自に算出したDifficultyで絞り込み
- 問題タイトル・コンテスト名・FAユーザー・最短ユーザー・最速ユーザー・etcで検索
- ユーザーダッシュボード
- AC数や連続新規AC日数などの確認
- 各種公式コンテストの埋め具合を確認
- 毎日のAC数の確認
- 自分の提出一覧
- 各言語でのAC数
- Difficultyを基にした問題推薦
- ランキング
クローラー
クローラーは Rust で書かれています。GitHub にプッシュすると Docker Hub でコンテナがビルドされ、 AWS の Elastic Container Service (ECS) 上で動きます。
今のところは提出クローラーは以下の4種類があります。結構重複していますし効率も悪いので、整理したいですね……
- 全部の提出をクロールし直す
- 各コンテストを回って新し目の提出をクロールする
- 最近のコンテストの提出をクロールする
- 最近提出があったコンテストにもう一度行ってクロールする
HTTP リクエストには reqwest というライブラリを、Html のパースには scraper というライブラリをそれぞれ使っています。
API サーバー
API サーバーはサーバーアプリケーションではなく Lambda として実装しています。Lambda は AWS の余剰計算資源を使って短時間の計算を低価格でできるサービスです。これによってサーバーアプリケーションを常時起動させているのではなく、アクセスがあったときのみアプリケーションを起動しているので運用コストを削減できます。Lambda 上に Rust 製アプリケーションがインストールされていて、ユーザー名を受け取ると別のサーバー上で動いているデータベースから提出一覧を取得してユーザーに返します。
Rust は公式に Lambda にサポートされているわけではありませんが、 lambda_runtime という AWS 謹製のライブラリがあるので、これを使うことでマクロに関数を渡すだけで簡単に実行してもらえるようになります。とは言えローカルでテストできないのは不便ですし、EC2とネットワーク周りのトラブルが時々あるので、乗り換えを検討しています。
フロントエンド
フロントエンドは TypeScript で書かれていて React を使っています。最近 redux を導入して、ほとんどの関数が副作用を持たないようになりました。contests や problems や submissions など複数のファイルから left join の要領で情報を結合することが多いので、内部で使っている List や Map は immutable-js を使うようにして、意図しない破壊が起こらないようにしています。
集計
一定時間ごとに、最短コードなどの各種集計情報を更新しています。集計バッチもクローラーと同じように ECS 上の Docker コンテナで動いています。直近の結果を見て更新できる部分だけを更新する差分更新バッチが数分おきに走っていて、全ての結果から集計情報を再構築する重いバッチが数時間おきに走っています。
難易度推定
amylase さんによってコンテスト結果から問題の難易度が推定できるようになりました。詳しくは本人が別の記事で書いてくれると思います。楽しみですね。
図
図です。
おわりに
AtCoder Problems をいつも使っていただきありがとうございます。どのようなものでもフィードバックをいただけるのは大変嬉しいです。ぜひ、使ってみた感想、あったら嬉しい機能、使ったことでレートが上がった、プログラミングスキルが向上した、就職できた、出世した、莫大な金銭を得た、余ったので1億ほど寄付したい、といったフィードバックをお送りください！
2019 JUST Programming Contest B. Memory Management System
問題
長さmの線分がとn個の区間があります。q個のクエリが与えられます。i番目のクエリでは整数k_iが与えられるので、線分上のn個の区間と重ならない長さk_i以上の区間で最も右にあるものを出力してください。
解法
空の集合Sを用意する。空いている区間を長さで降順にソートして持っておく。クエリを先読みしてソートしておき、大きい方から見ていく。クエリの値がk_qのとき、k_q以上の長さの直線をSに入れ、Sの中の最も右にある区間を出力する。
コード
use std::io::{stdout, BufWriter, Write}; fn main() { let s = std::io::stdin(); let mut sc = Scanner(s.lock()); let t: usize = sc.read(); for _ in 0..t { let n: usize = sc.read(); let m: u32 = sc.read(); let q: usize = sc.read(); let mut segments = vec![]; for _ in 0..n { let l = sc.read::<u32>() - 1; let r = sc.read::<u32>(); segments.push((l, r)); } segments.sort(); let mut cur = 0; let mut free = vec![]; for (l, r) in segments.into_iter() { if cur < l { free.push((cur, l)); } cur = r; } if cur < m { free.push((cur, m)); } let mut free_segments = vec![]; for (l, r) in free.into_iter() { let length = r - l; free_segments.push((length, l, r)); } free_segments.sort(); let mut queries = vec![]; for i in 0..q { let k = sc.read(); queries.push((k, i)); } queries.sort(); queries.reverse(); let mut ans: Vec<Option<(u32, u32)>> = vec![None; q]; let mut top: Option<(_, _)> = None; for (required_length, i) in queries.into_iter() { while let Some((length, l, r)) = free_segments.pop() { if length >= required_length { match top { Some(cur) => { if cur < (r, l) { top = Some((r, l)); } } None => { top = Some((r, l)); } } } else { free_segments.push((length, l, r)); break; } } if let Some((r, _)) = top { let l = r - required_length; ans[i] = Some((l, r)); } } let out = stdout(); let mut out = BufWriter::new(out.lock()); for ans in ans.into_iter() { match ans { Some((l, r)) => { write!(out, "{} {}", l + 1, r).unwrap(); out.write_all(b"\n").unwrap(); } None => { write!(out, "-1 -1").unwrap(); out.write_all(b"\n").unwrap(); } } } } } pub struct Scanner<R>(R); impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
Project Euler 684 Inverse Digit Sum
解法
各桁の数の和がxとなるような最小の整数 s(x) は必ず一番上の桁以外は全て9となる。
よって s(x) は以下のようになる。
s(x) の和 S(x) を考える。
S(20)=1074だが、これは以下のようにして求まる。
s(1) = 1 ... s(9) = 9 s(10) = 1 9 s(11) = 2 9 ... s(18) = 9 9 s(19) = 1 9 9 s(20) = 2 9 9
これは式変形の力によって以下の式で求まる。
よって S(x) が O(1) で求まるので、あとは各フィボナッチ数について計算すれば良い。
use self::mod_int::ModInt; const MOD: u128 = 1e9 as u128 + 7; fn main() { let mut f: Vec<u128> = vec![0, 1]; let mut ans = ModInt(0); for i in 2..91 { let fi = f[i - 1] + f[i - 2]; f.push(fi); ans += big_s2(fi); } println!("{}", ans.0); } fn big_s(x: u128) -> u128 { let nines = x / 9; let remain = x % 9; let mut sum = 0; sum += (remain + 1) * remain / 2; let mut upper = remain; for _ in 0..nines { sum *= 10; sum += upper * 9; sum += (9 + 1) * 9 / 2; upper += 9; } sum } fn big_s2(x: u128) -> ModInt<u128> { let nines = x / 9; let sum = if nines > 0 { let r = nines - 1; (ModInt(2).pow(r + 2) * ModInt(5).pow(r + 1) - 5 - ModInt(3) * r) * 3 } else { ModInt(0) }; let remain = x % 9; let head = (ModInt(10).pow(nines) - 1) * remain + ModInt(10).pow(nines) * (remain + 1) * remain / 2; sum + head } pub mod mod_int { use super::MOD; use std::ops::{Add, AddAssign, Div, DivAssign, Mul, MulAssign, Sub, SubAssign}; type Num = u128; #[derive(Clone, Copy)] pub struct ModInt<T: Copy + Clone>(pub T); impl Add<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: ModInt<Num>) -> ModInt<Num> { self + rhs.0 } } impl Add<Num> for ModInt<Num> { type Output = ModInt<Num>; fn add(self, rhs: Num) -> ModInt<Num> { let mut t = rhs + self.0; if t >= MOD { t = t - MOD; } ModInt(t) } } impl Sub<Num> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: Num) -> ModInt<Num> { let rhs = if rhs >= MOD { rhs % MOD } else { rhs }; let value = if self.0 < rhs { self.0 + MOD } else { self.0 }; ModInt(value - rhs) } } impl Sub<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn sub(self, rhs: ModInt<Num>) -> ModInt<Num> { self - rhs.0 } } impl AddAssign<Num> for ModInt<Num> { fn add_assign(&mut self, other: Num) { *self = *self + other; } } impl AddAssign<ModInt<Num>> for ModInt<Num> { fn add_assign(&mut self, other: ModInt<Num>) { *self = *self + other; } } impl SubAssign<Num> for ModInt<Num> { fn sub_assign(&mut self, other: Num) { *self = *self - other; } } impl SubAssign<ModInt<Num>> for ModInt<Num> { fn sub_assign(&mut self, other: ModInt<Num>) { *self = *self - other; } } impl Div<Num> for ModInt<Num> { type Output = ModInt<Num>; fn div(self, rhs: Num) -> ModInt<Num> { self * ModInt(rhs).pow(MOD - 2) } } impl Div<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn div(self, rhs: ModInt<Num>) -> ModInt<Num> { self / rhs.0 } } impl DivAssign<Num> for ModInt<Num> { fn div_assign(&mut self, rhs: Num) { *self = *self / rhs } } impl DivAssign<ModInt<Num>> for ModInt<Num> { fn div_assign(&mut self, rhs: ModInt<Num>) { *self = *self / rhs } } impl Mul<ModInt<Num>> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: ModInt<Num>) -> ModInt<Num> { self * rhs.0 } } impl Mul<Num> for ModInt<Num> { type Output = ModInt<Num>; fn mul(self, rhs: Num) -> ModInt<Num> { let t = (self.0 * rhs) % MOD; ModInt(t) } } impl MulAssign<Num> for ModInt<Num> { fn mul_assign(&mut self, rhs: Num) { *self = *self * rhs; } } impl MulAssign<ModInt<Num>> for ModInt<Num> { fn mul_assign(&mut self, rhs: ModInt<Num>) { *self = *self * rhs; } } impl ModInt<Num> { pub fn pow(self, e: Num) -> ModInt<Num> { let mut result = ModInt(1); let mut cur = self; let mut e = e; while e > 0 { if e & 1 == 1 { result *= cur; } e >>= 1; cur *= cur; } result } } }
ABC143 F - Distinct Numbers
問題
解法
K枚ずつ食べる時の最大の回数を求めるのではなく、H回食べるときの最大の1回に食べる枚数を求めることにする。
とする。H回食べると決めたとき、同じ数字を同時に食べないように選ぶ1回あたりの食べる枚数は
となる。例えば A = [1,1,1,1,1,2,2,2,3,3,3,4,4,4,5] で4回食べると決めたとき、以下のようにK=3となる。
1st -> 1 2 3 (4)
1nd -> 1 2 3 (5)
3rd -> 1 2 4
4th -> 1 3 4
(1)Hを大きい方から計算していくと線形時間で解ける。
コード
use std::cmp; fn main() { let s = std::io::stdin(); let mut sc = Scanner { stdin: s.lock() }; let n: usize = sc.read(); let mut count: Vec<usize> = vec![0; n]; for _ in 0..n { let a = sc.read::<usize>() - 1; count[a] += 1; } count.sort(); let mut ans = vec![0; n + 1]; let mut sum = count.iter().sum::<usize>(); let mut popped = 0; for height in (1..(n + 1)).rev() { while let Some(c) = count.pop() { if c >= height { sum -= c; popped += 1; } else { count.push(c); break; } } let columns = sum / height + popped; ans[columns] = cmp::max(ans[columns], height); } for k in (0..n).rev() { ans[k] = cmp::max(ans[k], ans[k + 1]); } for k in 1..(n + 1) { println!("{}", ans[k]); } } pub struct Scanner<R> { stdin: R, } impl<R: std::io::Read> Scanner<R> { pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .stdin .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n') .take_while(|&b| b != b' ' && b != b'\n') .collect::<Vec<_>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.read()).collect() } pub fn chars(&mut self) -> Vec<char> { self.read::<String>().chars().collect() } }
