System76 の PC を買いました（Lemur Pro）
お外に出たときに使う（ほぼ競プロ）用のノートPC が欲しいなと思って、いろいろ探していて前から気になっていた System76 の PC を買いました。
今、家で使っているメインの PC が Windows のデスクトップなので、サブの持ち運び用も Windows にしようと思ったけど、なかなか良い感じのスペックのものが中々なかったと、 Lemur Pro が再入荷していたので、これは買えと言っているな！と思って注文しました。
スペック
- CPU : 4.7Ghz i7-1165G7(12MB Cache - 4 Cores - 8 Threads)
- メモリ : 16GB Dual Channel DDR4 at 3200 MHz (2 x 8GB)
- ストレージ : 500GB PCIe Gen3 Up to Seq Read: 2400 MB/s, Seq Write: 1750 MB/s
注文からの流れ
- 4/16 注文
- 4/19 確認コードの送信。カードの請求情報にコードが送られてくるので、メールで返信する。（多分質問ある？的な）電話が来るも取れず…。組み立てに入った模様。
- 5/4 メールには 「3-6営業日で発送するよ〜」って書いてたんだけど、何も音沙汰がないのでいつ発送されるの？って確認を出す。 → 次の日「５月末予定だよ」って返事が来る。
- 5/13 発送される
- 5/16 18時頃届く。 税金？19700円取られた。
- 開封
環境構築、その他良いところ
まだ、1週間も経ってなくて、途中なんだけど、入れたアプリとか。
日本語入力
英語でセットアップしたので、全く日本語入力ができない。 Settings → Keyboard → Input Sources で 日本語を追加すると Mozc ってやつが勝手にインストールされて使えるようになる。 切り替えが不便なので、 Settings → View and Customize Shortcuts → Typing で、 Switch to next inpu tsource に適当なキーを割り当てる。僕は Ctrl + Space が慣れているのでそれに。
JetBrains系
snap install を勧められたので、してみる。
sudo snap install clion --classic
↑ のアプリケーション一覧とか、デフォルトで入っているランチャーアプリで起動できない。 それでは不便なので、対応を考える。 Pop!_Shop なるところに JetBrains の IDE があったのでそちらでインストール。 そうするとアプリケーション一覧や、ランチャーアプリに表示される。
その他アプリ
以下は入れました。 Linux を CUI サーバー以外として使うの初めてなので便利なのものがあったら教えてください。
- Slack
- 1 Password
- Discord
Pop!_OS
Pop!_OS タイル表示がウィンドウを開くと勝手にいい感じに分割してくれて良い。
あとは、ショートカット を覚えたい。
Codeforces Round #787 (Div. 3)
Codeforces Round #787 (Div. 3) です。 ABCDEF 6完でした。
A. Food for Animals
ドッグフードが $x$、キャットフードが $y$ が必要。お店には、ドッグフードが $a$ 個、キャットフードが $b$ 個、どちらも食べられるものが $c$ 個ある。必要個数変えますか？という問題。
専用のものは、そっちを使った方が良いので基本的に $a,b$ を買えるだけ買って、足りない分を $c$ で補うようにする。 $\max(0, x - a) + \max(0, y - b) \leq c $ なら "YES"
fn main() { let t : usize = input(); for _ in 0..t { solve() } } fn solve() { let (a, b, c, x, y) : (usize, usize, usize, usize, usize) = input_t5(); let x = x.saturating_sub(a); let y = y.saturating_sub(b); println!("{}", if (x+y) <= c {"Yes"} else {"No"}); }
B. Make It Increasing
列が与えられるので $a_i = \left \lfloor \frac{a_i}{2} \right \rfloor$ の操作を何回かして、狭義単調増加にできるか。
後ろから貪欲にやると良い。途中で $0$ になると達成できないので -1。
fn main() { let t : usize = input(); for _ in 0..t { solve() } } fn solve() { let n : usize = input(); let mut a : Vec<usize> = input_vec(); let mut ans = 0; for i in (0..n-1).rev() { while a[i] >= a[i+1] { if a[i]==0 { println!("-1"); return; } a[i]/=2; ans += 1; } } println!("{}", ans); }
C. Detective Task
泥棒されたので友達の証言から、泥棒の可能性がある人を数えてという問題。
1 は物があった、 0 は無かった、 ? は覚えていない。
泥棒以外は正しい事を言っているので、最後から2番目に 1 を言った人までは絶対に正しくて、最後に 1 を言った人は泥棒の可能性がある。同様に頭から2番目に 0 を言った人は絶対に正しくて、最初に 0 を言った人は泥棒の可能性がある。よって、最後に 1 と言った人から最初に 0 を言った人が泥棒の可能性がある。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let mut s : Vec<_> = input::<String>().chars().collect(); let n = s.len(); if n == 1 || s[0] == '0' { println!("1"); return; } let (index, _) = s.iter().enumerate().filter(|(_, &c)| c == '1').last().unwrap(); let mut ans = 0; for i in 1.max(index)..=n { ans += 1; if s[i] == '0' {break} } println!("{}", ans); }
D. Vertical Paths
問題読解に時間がかかった…。 木が与えられるので、1本のパスに分解してねって問題。
それがパスのスタート地点かどうかを持ちながら DFS する。
1個目の子供は親に繋がっていて、他の子供はパスのスタート地点にしたら良い。
葉まで来たら ans に入れておく。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let n : usize = input(); let p : Vec<usize> = input_vec(); let mut g = vec![vec![]; n]; let mut root = 0; for i in 0..n { let p = p[i] - 1; if i == p { root = i; continue } g[p].push(i); } let mut ans = vec![]; dfs(root, &g, true, &mut vec![], &mut ans); println!("{}\n{}", ans.len(), ans.join("\n")); } fn dfs(v:usize, g:&Vec<Vec<usize>>, p:bool, path:&mut Vec<usize>, ans:&mut Vec<String>) { let mut leaf = true; path.push(v); for (i, &u) in g[v].iter().enumerate() { leaf = false; if i > 0 { dfs(u, g, true, path, ans); } else { dfs(u, g, false, path, ans); } } if leaf { ans.push(format!("{}\n{}",path.len(),path.iter().map(|&p| (p+1).to_string()).collect::<Vec<_>>().join(" "))); path.clear(); } }
E. Replace With the Previous, Minimize
$a$ に含まれるあるアルファベットを全て1つ前のアルファベットに置き換える操作が $k$ 回できるので、辞書順最小の文字列を求めて下さいという問題。
辞書順最小は、前から 'a' に近づけて行けば良い。
操作は 1 つずつアルファベットが1つ戻っていくので、 そこ以前のアルファベットは全て同じだけ戻すことができる。 例えば 'f' が 'a' にできるなら、その間の "bcde" は全て 'a' にすることができる。
よって、以下のような変換のテーブルを持って、更新しながら貪欲に前から変換していけば良い。
例に挙げたような 'f' が 'a' にできるときは、こんな感じで更新しておく。
fn main() { let t : usize = input(); for _ in 0..t { solve(); } } fn solve() { let (n,mut k) : (usize, usize) = input_t(); let mut s : Vec<_> = input::<String>().chars().collect(); let mut t : Vec<_> = "abcdefghijklmnopqrstuvwxyz".chars().collect(); for i in 0..n { let mut index = (s[i] as u8 - b'a') as usize; let c = index.min(k); for j in index-c..=index { if t[j] != t[index-c] { k-=1; } t[j] = t[index-c]; } s[i] = t[index]; } println!("{}", s.iter().collect::<String>()); }
F. Vlad and Unfinished Business
木が与えられて、 $x$ から $y$ に行きたいが、途中で $a_1, a_2, \cdots, a_k$ のノードに寄る必要ある。その最短経路の距離を求めて下さいという問題。
必要な頂点の最小全域木みたいなものを考える。このとき、 $x$ と $y$ の間にない頂点は、行って帰ってくる必要がある。よって2倍かかる。だいたい 最小全域木の辺の数 * 2 であることが分かる。後は、 $x$ から $y$ の間は往復する必要がないのでその分を引いてあげる。
035 - Preserve Connectivity（★7） に思いを馳せると解ける。
fn main() { let t : usize = input(); for _ in 0..t { let _ = input::<String>(); solve() } } fn solve() { let (n,k) : (usize, usize) = input_t(); let (mut x, mut y) : (usize, usize) = input_t(); let mut v : Vec<usize> = input_vec(); for v in v.iter_mut() { *v-=1; } v.sort(); v.dedup(); x-=1; y-=1; let mut g = vec![vec![]; n]; for _ in 0..n-1 { let (mut a,mut b) : (usize, usize) = input_t(); a-=1; b-=1; g[a].push(b); g[b].push(a); } let mut lca = LowestCommonAncestor::from(&g); lca.init(x); v.push(x); v.push(y); v.sort_by_key(|&v| lca.time[v][0]); v.push(v[0]); let ans = v.windows(2).map(|v| lca.distance(v[0],v[1])).sum::<usize>() - lca.distance(x,y); println!("{}", ans); }
本当は、 v.into_iter().cycle().take(n+1) とかしたいんだけど、 tuple_windows() が使えないので、諦めた…
G. Sorting Pancakes
本番では解けてない。
合計が $m \leq 250$ と小さいので DP する。 $i$ 番目を決めるとき 直前が $k$ だったら $k$ 以下にしかできない。で、 この桁を $b$ とするときの操作回数は、$a$ のここまでの和と今まで使ったやつの差の絶対値を求めて行けば良いので、そんな感じで計算する。
$k$ は以下ならなんでも良いので、今までの min を取ってくると良くて、累積min すると良い感じになる。
fn main() { let (n, m) : (usize, usize) = input_t(); let a : Vec<i64> = input_vec(); const INF : i64 = std::i64::MAX / 10; let mut csum = vec![0; n+1]; for i in 0..n { csum[i+1] += csum[i] + a[i]; } let mut dp = vec![vec![INF; m+1]; m+1]; dp[0][m] = 0; for &s in csum.iter().skip(1) { let mut next = vec![vec![INF; m+1]; m+1]; for j in 0..=m { let mut min = INF; for k in (0..=m).rev() { chmin(&mut min, dp[j][k]); if j + k > m { continue } chmin(&mut next[j+k][k], min + (s - (j+k) as i64).abs()); } } dp = next; } let ans = dp[m].iter().min().unwrap(); println!("{}", ans); }
まとめ
コドフォレート 1329 → 1506（+177） これは成功回。 F 諦めなくて良かった～
Codeforces Round #786 (Div. 3)
Codeforces Round #786 (Div. 3) 。苦手の詰め合わせ。
6ペナ4完。
A. Number Transformation
$x,y$ が与えられるので、$y = x \times b ^ a$ な形にできるかという問題。最初素因数分解して良い感じにゴニョゴニョしよ～って思ってたんだけど、なんかめっちゃペナった。何がダメかと考えていたんだけど、 $y$ が小さいので雑に全探索するようにした。
制約が小さい時は愚直にやりましょう…
というかよく考えたら、 $x$ で割り切れたら、 $(y/x) ^ 1$ で良いじゃん。
fn solve() { let (mut x,mut y) : (usize, usize) = input_t(); if y % x != 0 { println!("0 0"); return; } y /= x; if y == 1 { println!("1 1"); return; } for i in 2..=y { let mut t = y; let mut cnt = 0; while t % i == 0 { cnt+=1; t/=i; } if t == 1 { println!("{} {}", cnt, i); return; } } println!("0 0"); }
B. Dictionary
癒やし枠。 同じアルファベットは使わず2文字の単語を順番良く生成しておいて、それが何番目か出力したら良い。
fn main() { let mut mp = BTreeMap::new(); let mut cnt = 1; f(&mut vec![], &mut mp, &mut cnt); let t : usize = input(); for _ in 0..t { let s = input::<String>(); println!("{}", mp[&s]); } } fn f(c:&mut Vec<char>, mp:&mut BTreeMap<String, usize>, cnt:&mut usize) { if c.len() == 2 { mp.insert(c.iter().collect::<String>(), *cnt); *cnt += 1; return; } for i in 0..26 { let ch = (b'a' + i) as char; if c.len() == 1 && c[0] == ch { continue } c.push(ch); f(c, mp, cnt); c.pop(); } }
C. Infinite Replacement
これも癒やし枠。 $S$ の中にある 'a' を $T$ に置き換える操作を何回かできる。その操作をして得られる文字列の種類数を求める問題。
$T$ が1文字で、それが 'a' であるなら、どんなに置き換えても結果は変わらないので、 $1$種類。$T$ の中に 'a' が含まれていて、長さが $1$ より大きいなら無限種類作れるので -1。後は、 $S$ の中の 'a' を置き換える/置き換えないの2種類が 'a' の個数分選択できるので、$S$ に含まれる 'a' の個数を $x$ とすると 2x が答え。
fn solve() { let s : Vec<_> = input::<String>().chars().collect(); let t : Vec<_> = input::<String>().chars().collect(); if t.len() == 1 && t[0] == 'a' { println!("1"); return; } if t.contains(&'a') && t.len()>1 { println!("-1"); return; } let cnt = s.iter().filter(|&&c| c == 'a').count() as u32; println!("{}", 2usize.pow(cnt)); }
D. A-B-C Sort
苦手。$N$ が偶数のとき、$A_0$ と $A_1$ の好きな方を $C_0$ にして、残った方を $C_1$ にすることができる。その後ろも同様に $2$ 個ずつ考えると良い。$N$ が奇数のとき、 $A_0$ は必ず $C_0$ に行く。その後は、偶数のときと同じように2個ずつ好きに swap して配置できる。後は、良い感じに配置して非減少な列にできるか判定したら良い（もうちょっと良い感じに処理まとめても良かったかも）。
fn solve() { let n : usize = input(); let a : Vec<usize> = input_vec(); let mut min = 0; if n % 2 == 0 { for i in (0..n).step_by(2) { let x = a[i].min(a[i+1]); let y = a[i].max(a[i+1]); if x < min { println!("NO"); return; } min = min.max(y); } } if n % 2 == 1 { min = a[0]; for i in (1..n).step_by(2) { let x = a[i].min(a[i+1]); let y = a[i].max(a[i+1]); if x < min { println!("NO"); return; } min = min.max(y); } } println!("YES"); }
E. Breaking the Wall
嫌い嫌い嫌い！算数をさせるな！！！ 本番中解けなかった…
2箇所遠く離れた場合は、それぞれ $2$ で割って切り上げしたやつの最小を足したとき。 後は、連続する $3$ 箇所と、連続する $2$ 箇所で良い感じにやる方法を考えると良い。
連続する $3$ 箇所は、$3$ 箇所であることを使いたいのでとりあえず真ん中を連打して、両サイドの小さいをなくす。後は、真ん中か余ってる方を消せば良いので小さい方をまた切り上げで出す。
連続する $2$ 箇所。これが爆発してた。連続する箇所の値を $x, y$ とすると $\max(\lceil x/2 \rceil, \lceil y/2 \rceil, \lceil (x + y) / 3 \rceil)$ が最小手数。
fn main() { let n : usize = input(); let a : Vec<usize> = input_vec(); let mut ans = std::usize::MAX; for i in 0..n { let mut v = vec![]; if i>0 { v.push(a[i-1]); } if i+1<n { v.push(a[i+1]); } v.sort(); let c = v[0]; let x = a[i].saturating_sub(2*c); let y = if v.len()>1 { v[1] - c } else {std::usize::MAX}; ans = ans.min(c + (x.min(y)+1)/2); } let mut v = a.iter().map(|&i| (i+1)/2).collect::<Vec<_>>(); v.sort(); ans = ans.min(v[0] + v[1]); for a in a.windows(2) { let x = (a[0] + 1) / 2; let y = (a[1] + 1) / 2; let z = (a[0] + a[1] + 2) / 3; ans = ans.min(x.max(y).max(z)); } println!("{}", ans); }
いやぁ…こういう問題苦手だなぁ…
F. Desktop Rearrangement
パッと見たけど、問題の意味が分からず。
G. Remove Directed Edges
見てない。
まとめ
苦手なコンテストでした。
コドフォレート 1344 → 1328（-16）
AtCoder Beginner Contest 248
AtCoder Beginner Contest 248 です。
A - Lacked Number
"0123456789" のうち $S$ の中にあるやつを削除します。文字数が少ないので多少計算量の悪い書き方しても大丈夫です。 filter で1つずつ contains で確認すると良いです。
fn main() { input! { s : Chars } let ans = "0123456789".chars().filter(|&c| !s.contains(&c)).collect_vec(); println!("{}", ans[0]); }
B - Slimes
$A$ が $B$ 以上になるまで $K$ 倍していきます。 while 実装したら良い感じになります。その回数を数えたら良いです。
fn main() { input! { mut a : usize, b : usize, k : usize } let mut ans = 0; while a < b { a*=k; ans+=1; } println!("{}", ans); }
C - Dice Sum
$K$ 個のボールと $N-1$ 個の縦棒を良い感じに並べる組合せとか考えたんですが、筋が良く無さそう。 $A_i \leq 50$ と結構少ないので、 $A_i$ を1つずつ決めていけば良さそう。
とりあえず良い感じに再帰で $A_i$ を決めていって $K$ 以下となる組合せを数える。後は、$i$項決めた・合計が $j$ でメモ化したら良い。
fn main() { input! { n : usize, m : usize, k : usize } let mut memo = FxHashMap::default(); let ans = f(0, 0, n, m, k, &mut memo); println!("{}", ans); } fn f(i:usize, sum:usize, n:usize, m:usize, k:usize, memo:&mut FxHashMap<(usize,usize), usize>) -> usize { if let Some(res) = memo.get(&(i, sum)) { return *res; } if i == n { if sum <= k { return 1; } else { return 0; } } let mut res = 0; for j in 1..=m { res += f(i+1, sum+j, n, m, k, memo); res %= MOD; } memo.insert((i, sum), res); res }
D - Range Count Query
なんかパッと見良い方法が思い浮かばなかったので、 Mo's algorithm を貼る。終わり。 まともな方針は、値毎に index 持って、 lower_bound と upper_bound 使って間の数を数えたら良いっぽい。
fn main() { input! { n : usize, a : [Usize1; n], q : usize, queries : [(Usize1, usize, Usize1); q] } let mut queries = queries.into_iter().enumerate().map(|(i, (l, r, x))| (i, l, r, x)).collect_vec(); queries.sort_by_cached_key(|&(_, l, r, _)| hilbertorder(l, r)); let mut cnt = vec![0; n]; let mut count = 0; let mut nowl = 0; let mut nowr = 0; let mut ans = vec![0; q]; for (i, l, r, x) in queries { for i in (l..nowl).chain(nowr..r) { add(&mut count, &mut cnt, a[i]); } for i in (nowl..l).chain(r..nowr) { del(&mut count, &mut cnt, a[i]); } nowl = l; nowr = r; ans[i] = cnt[x]; } println!("{}", ans.iter().join("\n")); } fn add(count :&mut usize, cnt:&mut Vec<usize>, x:usize) { if cnt[x] == 0 { *count += 1; } cnt[x] += 1; } fn del(count:&mut usize, cnt:&mut Vec<usize>, x:usize) { cnt[x] -= 1; if cnt[x] == 0 { *count -= 1; } } fn hilbertorder(mut x:usize, mut y:usize) -> usize { const LOG : usize = 20; const MAXN : usize = 1 << LOG; let mut d = 0; let mut s = 1 << (LOG - 1); while s > 0 { let rx = if x & s > 0 {1} else {0}; let ry = if y & s > 0 {1} else {0}; s /= 2; d = (d<<2) | ((rx*3) ^ ry); if ry>0 { continue } if rx>0 { x = MAXN - x; y = MAXN - y; } std::mem::swap(&mut x, &mut y); } d }
E - K-colinear Line
なんですか？この問題。
幾何ライブラリを貼って、 ccw を使うと良い感じになりそう。
引用
端点を2つ選んでその間に $K$ 個以上の点があるか確認したら良い。点 $A, B$ と $C$ の関係を決める。 $A,B$ の間ではなく先にあると困るので、良い感じにする必要がある。
$A$ と $B$ を端点に ccw して、 +2 または -2 なら $A, B$ を伸ばした先に $C$ があるのでスキップする。そういう点が無い場合は、 0 になる点を数えたら良い。
僕の幾何ライブラリが f64 でできているので多分誤差で WA。判定に必要な部分だけを i64 で書き直す……。つ、辛い…。$K = 1$ のときは、その点を通る直線は無限にあるので注意。
整数で求める幾何ライブラリも作ります……。
fn main() { input! { n : usize, k : usize, xy : [(i64, i64); n] } if k==1 && n>=1 { println!("Infinity"); return; } let cross = |p1:(i64, i64), p2:(i64, i64)| { p1.0 * p2.1 - p1.1 * p2.0 }; let dot = |p1:(i64, i64), p2:(i64, i64)| { p1.0 * p2.0 + p1.1 * p2.1 }; let dist = |p1:(i64, i64), p2:(i64, i64)| { (p1.0 - p2.0) * (p1.0 - p2.0) + (p1.1 - p2.1) * (p1.1 - p2.1) }; let ccw = |p1:(i64, i64), p2:(i64, i64), p3:(i64, i64)| -> i64 { if cross((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) > 0 { return 1 } if cross((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) < 0 { return -1 } if dot((p2.0 - p1.0, p2.1 - p1.1), (p3.0 - p1.0, p3.1 - p1.1)) < 0 { return 2 } if dist((p2.0 - p1.0, p2.1 - p1.1), (0,0)) < dist((p3.0 - p1.0, p3.1 - p1.1), (0,0)) { return -2 } 0 }; let mut ans = 0; for i in 0..n { for j in i+1..n { let mut cnt = 0; for l in 0..n { if i==l || j==l { cnt += 1; continue } if ccw(xy[i], xy[j], xy[l]).abs() == 2 { cnt = 0; break } if ccw(xy[i], xy[j], xy[l]).abs() == 0 { cnt += 1;} } if cnt >= k { ans += 1; } }} println!("{}", ans) }
F - Keep Connect
なんかヤバい DP が思い浮かぶ。同じ形が続いているので、連結な状態を続けられる形を全部持って DP する。 ↓ みたいな感じの状態を持つ。
しかし、これでは接続を先延ばしにしているパターンと、既に接続しているパターンの見分けがつかないのでダメでした。本番中は地獄だった…。
ちゃんと解いたら追記します。
G - GCD cost on the tree
見てない
Ex - Beautiful Subsequences
見てない
まとめ
ここ2回レート下がってて辛い… 冷えまくり…
AtCoder Beginner Contest 247
AtCoder Beginner Contest 247 です。
A - Move Right
二進法表記されたやつを右シフトしてください。みたいな問題。
受け取るのがめんどくさいので Vec<char> みたいなもので受け取って rotate_right して先頭を '0' にしたら OK。
fn main() { input! { mut s : Chars } s.rotate_right(1); s[0] = '0'; println!("{}", s.iter().join("")); }
B - Unique Nicknames
なんですか？この問題。 姓か名のどちらかが他の人の姓・名と被っていなければ OK。フラグ持ってやれば良い。
fn main() { input! { n : usize, st : [(String, String); n] } let mut used = vec![vec![false; 2]; n]; for (i, (s,t)) in st.iter().enumerate() { let mut sf = true; let mut tf = true; for (j, (sj, tj)) in st.iter().enumerate() { if i == j { continue } sf &= !(s==sj || s==tj); tf &= !(t==sj || t==tj); } if !sf && !tf { println!("No"); return; } } println!("Yes"); }
C - 1 2 1 3 1 2 1
定義が再帰的になっている。$N \leq 16$ なので雑に f(n-1) + n.to_storing() + f(n-1) みたいなことをしたら良いです。
fn main() { input! { n : usize, } println!("{}", f(n)); } fn f(n:usize) -> String { if n == 1 { return "1".to_string() } let mut res = "".to_string(); let s1 = f(n-1); res.push_str(&s1); res.push(' '); res.push_str(&n.to_string()); res.push(' ' ); res.push_str(&s1); res }
D - Cylinder
最初 $c$ 回 deque に push しようと思ったけど $c \leq 109$ なのでランレングス圧縮したような状態でもって、取り出したときに調整します。余ったら push_front して戻しておきます。
fn main() { input! { q : usize } let mut a = VecDeque::new(); let mut ans = vec![]; for _ in 0..q { input! { t : u8 } match t { 1 => { input! { (x, c) : (usize, usize) } a.push_back((x, c)); } 2 => { let mut sum = 0; input! { mut c : usize } while c > 0 { let (x, mut d) = a.pop_front().unwrap(); let b = c.min(d); sum += x * b; c -= b; d -= b; if d != 0 { a.push_front((x, d)); } } ans.push(sum); } _ => unreachable!() } } println!("{}", ans.iter().join("\n")); }
E - Max Min
なんか最初に良い方針が思いつかなくて焦っちゃったかも。めちゃくちゃ迷走した。 途中で左端を固定して二分探索っていうまともそうな方針をたてたんだけど、バグらせて無事死亡。
結局、$Y \leq A_i \leq X$ となる範囲を切り出して、そこでしゃくとり法をするようにした。最終的には楽そうな実装にできたけど、うーん……。 良くなかった。
fn main() { input! { n : usize, x : usize, y : usize, a : [usize; n] } let mut v = split(y, x, a); let mut ans = 0; let mut cnt = BtreeMultiSet::new(); for v in v { let mut j = 0; let mut yf = false; let mut xf = false; for i in 0..v.len() { if j < i { j = i; yf=false; xf=false; } while (!yf || !xf) && j<v.len() { if v[j] == y && !cnt.contains(&y) { yf = true; } if v[j] == x && !cnt.contains(&x) { xf = true; } cnt.add(v[j]); j += 1; } if yf && xf { ans += v.len() + 1 - j; } cnt.remove(v[i]); yf &= cnt.contains(&y); xf &= cnt.contains(&x); } } println!("{}", ans); } fn split(min:usize, max:usize, a:Vec<usize>) -> Vec<Vec<usize>>{ let mut res = vec![]; let mut tmp = vec![]; for &a in a.iter() { if !(min..=max).contains(&a) { if tmp.is_empty() { continue } res.push(tmp.clone()); tmp.clear(); } else { tmp.push(a); } } if !tmp.is_empty() { res.push(tmp.clone()); } res }
F - Cards
本番中にあんまり読めなかった……。焦って読んだからかあんまり問題の意味を理解してなかったし、本番中に解けなかった。
いくつかのカードを選んで、$1$ ～ $N$ 全ての数があるようにしたい。$P$ と $Q$ は順列なので、カードに書かれている数を繋ぐといくつかのサイクルに分かれる。それのなんかの値のかけ算になる。頂点が1つだと $1$、 2だと $3$（どちらか片方+両方）、みたいに計算して OEIS に投げるとリュカ数というそれっぽいやつが出てくる。 なんか良い感じに計算したら良い。
fn main() { input! { n : usize, p : [Usize1; n], q : [Usize1; n] } let mut uni = UnionFind::new(n); for (p, q) in p.into_iter().zip(q) { uni.merge(p, q); } let mut memo = FxHashMap::default(); let roots = (0..n).filter(|i| *i == uni.root(*i)).collect_vec(); let ans = roots.iter().map(|&i| f(uni.size(i), &mut memo)).fold(1, |acc,v| (acc * v) % MOD); println!("{}", ans); } fn f(n:usize, memo:&mut FxHashMap<usize,usize>) -> usize { if n==0 { return 2 } if n==1 { return 1 } if let Some(res) = memo.get(&n) { return *res } let res = (f(n-1, memo) + f(n-2, memo)) % MOD; memo.insert(n, res); res }
G - Dream Team
本番中にチラッと読んだんだけど、なんとなーく最小費用流みを感じて「使ったこと無いし…」って諦めちゃった。500点取ってもあんまり順位上がらないので、こちらを頑張った方が良かったかもしれない。
所属大学と得意分野のマッチングで、人が辺だと考えると重み付き二部マッチングになる。MinCostFlow に min_cost_slope というのが合って、流量とコストの関係を折れ線グラフで返してくれる関数があるので、それを使う。が、なぜかグラフの形を間違えてバグらせる。折れ線グラフで間がないので復元（？）をして出力すると良い（僕は Rust版ACL をお借りした）。
fn main() { input! { n : usize, edges : [(Usize1, Usize1, i64); n] } let mut g = MinCostFlowGraph::new(450); const S : usize = 400; const T : usize = 401; const B : usize = 150; const BASE : i64 = 1_000_000_000_000_000; for i in 0..B { g.add_edge(S, i, 1, 0); g.add_edge(i + B, T, 1, 0); } for (a, b, c) in edges { g.add_edge(a, b + B, 1, BASE - c); } let slope = g.slope(S, T, 500); let slope = slope.into_iter().map(|(flow, cost)| (flow, flow * BASE - cost)).collect_vec(); let mut ans = slope.windows(2).map(|s|{ let base = s[0].1; let a = (s[1].1 - s[0].1) / (s[1].0 - s[0].0); (0..(s[1].0 - s[0].0)).map(|i| base + i * a).collect_vec() }).flatten().collect_vec(); ans.push(slope.last().unwrap().1); println!("{}\n{}", ans.len() - 1, ans.iter().skip(1).join("\n")); }
Ex - Rearranging Problem
手も足も出ない感じなので今度。
まとめ
E に意味分からないくらい時間をかけてしまった。 青になりたかったが結構冷えちゃった……。
青へのプレッシャーと、寝不足とでいろいろダメになっている気がするのでとりあえず寝不足解消しようかな。
AtCoder Beginner Contest 246
AtCoder Beginner Contest 246 です。
A - Four Points
長方形の3点の座標が与えられるので、残り1点を求めて下さいという問題。長方形の各辺は $x$軸か $y$軸に平行になっているので、必ず2点はペアになっているはずです。ということで $x_1 == x_2$ なら $x_4$ は $x_3$ と同じになるはずです。他の組合せも同じ感じで場合分けして書きます。
fn main() { input! { (x1, y1) : (i64, i64), (x2, y2) : (i64, i64), (x3, y3) : (i64, i64) } let x4 = if x1==x2 {x3} else if x1==x3 {x2} else {x1}; let y4 = if y1==y2 {y3} else if y1==y3 {y2} else {y1}; println!("{} {}", x4, y4); }
ちなみに同じ値を xor すると $0$ になるので、 $x_4 = x_1 \oplus x_2 \oplus x_3$ として求める事もできます（コード）。
B - Get Closer
$(0,0)$ から $(A,B)$ に向かって距離1だけ進んだ座標を求める問題。
これは、$(A, B)$ までの距離が分かればそれで割れば良いです。 $\sqrt{A2+B2}$ で求められます。 C++ や Rust には hypot という関数があってそれで求めるのが楽です（他の言語はあるか知りません…）。
fn main() { input! { a : f64, b : f64 } let dist = hypot(a, b); let ans = (a/dist, b/dist); println!("{} {}", ans.0, ans.1); }
C - Coupon
クーポンを使うと1枚につき $X$円安くなるのでできるだけ安く買ったときの金額を求める問題。
$k$ 枚使って、 $kX$円値引きして $0$ 未満になると $0$ 円になってしまうので、 $X$円きっちり引かれる方を優先したいです。そこで一旦、$kX$ が $a_i$ を超えないように値引きをして、後で超える分の値引きをします。
超える分に関しては、$1$ 円の商品と $2$ 円の商品があったときに、どちらに $3$ 円クーポン使いますか？というのを考えると $2$ 円に使った方が良いので、大きい方から貪欲に割り当てていきます。
fn main() { input! { n : usize, mut k : usize, x : usize, mut a : [usize; n] } a.sort(); a.reverse(); for a in a.iter_mut() { let c = k.min(*a / x); k -= c; *a -= c * x; } a.sort(); a.reverse(); let mut ans = 0; for &a in a.iter() { if a > 0 && k > 0 { k -= 1; continue } ans += a; } println!("{}", ans); }
D - 2-variable Function
$X = a3 + a2b + ab2 + b3$ としたとき、 $N$ 以上となる $X$ の最小値を求める問題。 $N \leq 10^{18}$ と制約がかなり大きいです。ただ、 $a3$ ということに注目すると、 $a3 = 10^{18}$ になる値を考えると $106$ くらいで良いことが分かります。そこで、 $a$ を全探索してみます。 $a$ の値を決め打ったときに、 $b$ の値が増加すると $X$ の値も単調増加することが分かります。よって、 $N$ 以上となるような $b$ を二分探索などで求めたら良いです。
fn main() { input! { n : u128 } let z = |a:u128, b:u128| { a*a*a + a*a*b + a*b*b + b*b*b }; let mut ans = std::u128::MAX; for a in 0..=1_000_000 { let mut l = 0; let mut r = 1_000_001; while l+1 < r { let b = (l+r)/ 2; if z(a,b) >= n { r = b; } else { l = b; } } let zi = z(a,l); if n <= zi { ans = ans.min(zi); } let zi = z(a,r); if n <= zi { ans = ans.min(zi); } } println!("{}", ans); }
E - Bishop 2
障害物がある盤面で、ある座標からスタートしてある座標までビショップの動きをしてたどり着けますか？たどり着けるとしたらなん手で行けますか？という問題。障害物は取ったり飛び越えたりはできません。
愚直に探索すると、ちょっと難しそうなので ビショップ について考えてみます。ビショップのは障害物が無いかぎり斜めの全てのマスに1手で移動できます。よって進む向きに番号を振ってみます。左上に$0$、右上に$1$…という感じです。そして、同じ方向に進み続ける限り 移動の手数は $0$ だと考えて良いです。つまり、同じ方向に進む場合のコストは$0$、方向を変える場合のコストは$1$ として各マスへの最短経路を求めたら良いです。辺に重みがある最短経路なので dijkstra法をしたくなりますが、今回は $0,1$ しかないため deque などをしようし、 $0$ の場合は先頭、 $1$ の場合は末尾に追加することで正しく探索できます（01-BFSと呼ばれてたりします）。
fn main() { input! { n : usize, a : (Usize1, Usize1), b : (Usize1, Usize1), s : [Chars; n] } let mut q = VecDeque::new(); for i in 0..4 { q.push_back((a.0, a.1, i, 1)); } let mut dist = vec![vec![vec![None; 4]; n]; n]; for i in 0..4 { dist[a.0][a.1][i] = Some(Reverse(1)); } while let Some((y, x, e, c)) = q.pop_front() { if let Some(Reverse(d)) = dist[y][x][e] { if d > c { continue } for (i, (dx, dy)) in vec![(!0, !0), (!0, 1), (1, !0), (1, 1)].into_iter().enumerate() { let cost = if e == i { 0 } else { 1 }; let mut xi = x.wrapping_add(dx); let mut yi = y.wrapping_add(dy); if n <= xi || n <= yi || s[yi][xi] == '#' { continue } if chmax(&mut dist[yi][xi][i], Some(Reverse(d + cost))) { if cost == 0 { q.push_front((yi, xi, i, d + cost)); } else { q.push_back((yi, xi, i, d + cost)); } } } } } if let Some(Reverse(ans)) = dist[b.0][b.1].iter().max().unwrap() { println!("{}", ans); } else { println!("-1"); } }
F - typewriter
各行で与えられる文字だけを使って $L$ 文字入力するとしたとき、その文字列は何通りありますか？という問題。
まず、$N=1$ のときを考えて見ます。このとき、$L$ 桁の文字列のうち、1文字目は $S_1$ の種類数分あってそれが $L$ 桁あるので、 $S_1$ の文字の種類数を $|S_1|$ とすると、 $|S_1|^L$ になります。では、 $N=2$ のときはどうでしょう？$S_1$ と $S_2$ それぞれで作れる物を足して、両方から作れる物を引けば良いです。では、 $N=3$ では？ $|S_1|^L + |S_2|^L + |S_3|^L - |S_1 \cap S_2|^L - |S_1 \cap S_3|^L - |S_2 \cap S_3|^L$ としたくなりますが、これでは、 $S_1, S_2, S_3$ 全部で共通して作れる物が余計に引かれます。つまり、 $|S_1 \cap S_2 \cap S_3|^L$ を足してあげれば良いです（包除原理）。
拡張すると、$S$ が何個変わった式かっていうのの偶奇で良い感じにします（詳しくは自分で調べて下さい…）。良い感じに足し引きすると求まります。
fn main() { input! { n : usize, l : usize, s : [Bytes; n] } const MOD : usize = 998_244_353; let s = s.into_iter().map(|s|{ s.into_iter().map(|c|{ (c - b'a') as usize }).collect_vec() }).collect_vec(); let mut ans = 0; for i in 1usize..1<<n { let mut cnt = vec![0; 26]; for j in 0..n { if i>>j & 1 == 1 { for &c in s[j].iter() { cnt[c] += 1; } } } let c = cnt.iter().filter(|&&cnt| cnt == i.count_ones()).count(); if i.count_ones() % 2 == 1 { ans += pow(c, l, MOD); } else { ans = ans + MOD - pow(c, l, MOD); } ans %= MOD; } println!("{}", ans); }
G - Game on Tree 3
解いたけど元気がないので今度書きます。
Ex - 01? Queries
解いたけど元気がないので今度書きます。
まとめ
この回で青行きたかったな……
AtCoder Beginner Contest 237
AtCoder Beginner Contest 237 です。
久しぶりに Rated 参加しました。ちょっと悲しい気持ちになっています。 5完 57:41（4ペナ） でした。
A - Not Overflow
Rust で良い感じに $2^{31}$ を計算する方法が思いつかなかったので、愚直に求めました。
よく考えたら 2i64.pow(31) したら良かったです。
fn main() { input! { n : i64 } let mut p = 1; for _ in 0..31 { p *= 2; } println!("{}", if (-p..p).contains(&n) {"Yes"} else {"No"}); }
B - Matrix Transposition
最初 D 問題が表示されていて、「Bにしては難しくない？」って思いながら解いて出したら全部 RE になってめちゃくちゃ焦りました。
Rust で，行と列を転置する を思いだしたんですが、出力するだけなら自分で書いた方が早いかな～と雑に書きました。↓→ みたいな順で出力されるようにしたら良いです。
fn main() { input! { h : usize, w : usize, a : [[usize; w]; h] } for i in 0..w { for j in 0..h { print!("{}{}", a[j][i], if j+1==h {"\n"} else {" "}); }} }
C - kasaka
雑なことをしたら、コーナーケースでかなり死にました。
基本的には、後ろ側にある 'a' を削除して回文なら OK です。
ただし、前側にある 'a' か、後ろ側にある 'a' の数の小さい方だけ後ろに残します。
そのときに回文であればOK（なんかもう少し筋の良い書き方ありそう）
fn main() { input! { mut s : Chars } if s == s.iter().rev().cloned().collect_vec() { println!("Yes"); return; } let mut cnt1 = s.iter().rev().take_while(|&&c| c=='a').count(); let mut s = s.into_iter().rev().skip_while(|&c| c=='a').collect_vec(); s.reverse(); let cnt = s.iter().take_while(|&&c| c=='a').count(); for _ in 0..cnt.min(cnt1) { s.push('a'); } println!("{}", if s == s.iter().rev().cloned().collect_vec() {"Yes"} else {"No"} ) }
D - LR insertion
難しいです！
挿入される位置が、バラバラなので Vec などでやると大変なことになりそうです。
昇順に処理をすると間に挿入する事になるのですが、降順に処理すると $S_i$ が 'R' なら列の最初に $i-1$ を追加、 'L' なら 列の最後に追加するだけで良くなります。
後は、 Deque などを使えば実装できます（Vecを2つ持つでもOK）
fn main() { input! { n : usize, mut s : Chars } let mut ans : VecDeque<_> = vec![n].into_iter().collect(); for i in (0..n).rev() { match s[i] { 'L' => ans.push_back(i), 'R' => ans.push_front(i), _ => unreachable!() } } println!("{}", ans.iter().join(" ")); }
E - Skiing
負辺があるので普通のダイクストラではダメです。
一度登って、降りることを考えたときに何度も登り降りして楽しさが増加することはないので、 BFS みたいなことをしながら楽しさに更新があったらそこから再更新をしていけば良いです（落とすようなケース作れるのかな？）。 コンテスト中には知らなかったんですが、これ SPFA って呼ばれるアルゴリズムの劣化版みたいな感じになってそうですね？
2秒で「ダイクストラではダメだな～」って思ったのに、ダイクストラで通ったみたいです。 これはお気持ちなんですが、解説 に以下のように書いてあるので ただのダイクストラで通らないことを確認してくれ！と思いました。
この問題に直接ダイクストラ法を用いることはできません。
fn main() { input! { n : usize, m : usize, h : [i64; n], edges : [(Usize1, Usize1); m] } let mut g = vec![vec![]; n]; for (a,b) in edges { g[a].push(b); g[b].push(a); } let mut q = VecDeque::new(); q.push_back((0,0)); let mut ans = vec![std::i64::MIN/10; n]; ans[0] = 0; while let Some((v, c)) = q.pop_front() { if ans[v] < c { continue } for &u in g[v].iter() { let p = ans[v] + if h[v]<h[u] {2*(h[v]-h[u])} else {h[v]-h[u]}; if ans[u] >= p { continue } ans[u] = p; q.push_back((u, p)); } } println!("{}", ans.iter().max().unwrap()) }
F - |LIS| = 3
最初、最長増加部分列の長さが $i$ で最長増加部分列の最後が $j$ みたいなものを考えていたんですが、情報が足りないな～と思って、 最長増加部分列の長さが $i$ で最長増加部分列の最後の1つ手前が $j$ で、最長増加部分列の最後が $k$ を書いていました。しかし通らず…
3つが確定なので LIS で使う配列を lower_bound で更新していくように、 DP の添字に LIS 配列を持って後で集計したら良かったです。 これは解けたなぁって感じです…
use proconio::input; fn main() { input! { n : usize, m : usize } const MOD : usize = 998244353; let mut dp = vec![vec![vec![0; m+2]; m+2]; m+2]; dp[m+1][m+1][m+1] = 1; for _ in 0..n { let mut next = vec![vec![vec![0; m+2]; m+2]; m+2]; for i in 1..=m+1 { for j in 1..=m+1 { for k in 1..=m+1 { for m in 1..=m { if m<=i { next[m][j][k] += dp[i][j][k]; next[m][j][k] %= MOD; } else if m<=j { next[i][m][k] += dp[i][j][k]; next[i][m][k] %= MOD; } else if m<=k { next[i][j][m] += dp[i][j][k]; next[i][j][m] %= MOD; } } }}} dp = next; } let mut ans = 0; for i in 1..=m { for j in i+1..=m { for k in j+1..=m { ans += dp[i][j][k]; ans %= MOD; }}} println!("{}", ans % MOD); }
G - G
見てません
H - H
見てません
まとめ
久しぶりに Rated 参加したのに B 問題と D 問題が入れ替わってて全部 RE が出たり（心臓に悪い）、 100% 想定できる嘘解法を落とすようなケースがなかったりで、ちょっと悲しい気持ちになりました。
まぁ、次頑張ります…
