記録
NEC Programming Contest 2022 (AtCoder Beginner Contest 267) - AtCoder
賞金が高い. 飛び賞を狙う. 100位圏内に入れば期待値がなんと1000円なので参加する他はない. NECありがとう！
A,B,C,D,E,Exの6完で, 7725人中137位だった.
Fは間に合わなかったが, Exが先に解けた. なんとか100位圏内なのでよかった！たぶん学生50位くらい.
解法
A
A - Saturday
提出 2:04 (0)
解法
愚直なIF文でokだが, スタイリッシュに解ける. MondayからFridayまでの3文字目はどれも異なるから, そこで判定すればokである.
提出
Pypy3
Submission #34532133 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
B
B - Split?
提出 16:44 (1)
解法
ボウリングのスプリットとかは知らなかった. そのせいか知らないけれど, 定義を理解し間違えてしまった. 隣接する3つの列に対して判定するのかと思った.
ただの3重ループでokでした. しかも, 35通りしか判定しなくてよいので, 計算量は余裕.
提出
Pypy3
Submission #34542770 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
C
C - Index × A(Continuous ver.)
提出 11:01 (0)
解法
こっちは問題文が理解できた. ある連続部分列から, 次の連続部分列への遷移を考える.
最初の連続部分列から2個目の連続部分列への遷移を考えれば, 残りも同様に行える.
最初は
である. これは
で可能.
次は
である. 最初から次で減ったのは
で, 増えたのは
である.
累積和を考えれば任意の
に対して
は簡単に計算できるから, ここはO(1).
これを繰り返せばよい.
提出
Pypy3
Submission #34539589 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
D
D - Index × A(Not Continuous ver.)
提出 15:01 (0)
解法
だから,
の制約は許される.
dp[i][j] : i個の部分列で,
の
以下の項だけを使った
の最大値
というちょい典型なDPが立てられる. dp[i][j]は最初すべて-∞で, dp[0][0]だけ0.
遷移は dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + i * a[j]) となる.
なんかCより簡単な気がしたが…？
提出
Pypy3
Submission #34541743 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
E
E - Erasing Vertices 2
提出 37:47 (2)
解法
問題文を誤読しかけた.あぶない.
これは貪欲でいけそう. 今消せるもののうち, コストが最小のものをどんどん消していく.
コストが最小のものが複数あっても, 求めるものは「コストの最大値」なので, これによって最終的な結果は変わらない.
「コストの和」だったら少し変わってきたかも.（こっちは解がよくわからない）
コストの最小値をどんどん取っていくのは, 優先度付きキューか, Multisetのいずれかを使えばいい. コストは変動していくが, 変動回数は高々
回であるから間に合う
Python・Pypyだとちょっときついかもしれない. ぼくはtatyamさんのSortedMultisetを使って解いた. ありがとう！
のはず.
GitHub - tatyam-prime/SortedSet
実装に二重にミスがあって2REを出してしまった…
最小値を素早く！といえば優先度付きキュー or Multisetというのが思い浮かべたのはよかった. これでスムーズにことが進んだ.
提出
Pypy3
Submission #34554165 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
F
F - Exactly K Steps
提出 コンテスト後
解法
我々が馴染み深いのは頂点
から頂点
が与えられて, その距離をもとめるやつである. これはダブリングでok.
しかし, これでは駄目！その逆？みたいなことをしなければならない.
まず自明な
解が考えられるがもちろん駄目. そこから発展させることもできなさそう.
かなり考えたが, どれも無理そう. 数十分後の結論として, 次の考察を得た.
クエリをオンラインで考えたとき, 二分探索によって
木の直径を求められる.
ここで, 木の直径をなすパスを軸として考えて, 頂点と軸との距離を求める.
から可能なパスのうち, 最長なものの1つは必ず軸の端となる. そうじゃないとき, そっちを軸とすれば木の直径が伸びる.
軸から出発するとき, 遠い方の軸の端に向けて走り出す. 軸の頂点をリストにしておくと, 簡単に求められる.
軸以外から出発するとき, まず軸に向かう. 軸にあたったときは上の操作をする.
軸以外から軸までの途中に目的のものがあったら？距離が長い場合はうれしくない. このとき, ダブリングというものを使う.
dp[i][j] をjの2^i個先の頂点とすると, uのk個先の頂点は
で求められる. ダブリングは前処理は
.
軸の途中に目的のものがあったらこれは
.
これはかなり難しかった. これで青色Diffなのはなぜだ…
結局やることとしては
1. 入力受け取り
2. 木の直径と, そのパス（軸）を求める
3. その軸を起点として, 各頂点がどの軸の頂点に属しているかと, 距離はどのくらいかを求める.
4. ダブリングの前処理をする.
5. クエリを処理していく.
いやー難しいですね
提出
Pypy3
Submission #34579320 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
Ex
Ex - Odd Sum
提出 70:10 (1)
解法
これは見た瞬間に
yukicoder No.2062を思い浮かべた. 次の記事に解説がある. この問題は, その問題と同じノリで考察できる.
参加記 yukicoder contest 358 - しょぼんブログ
一旦奇数個という条件を除いてみよう.
これは形式的冪
級数なのだが,
![[x^M] \prod_{i=1}^{N} (1+x^{A_i})](https://chart.apis.google.com/chart?cht=tx&chl=%20%5Bx%5EM%5D%20%5Cprod_%7Bi%3D1%7D%5E%7BN%7D%20%281%2Bx%5E%7BA_i%7D%29)
を求めればいい.
形式的冪
級数についてはこれをおすすめします
trap.jp
でも愚直にやると間に合わない. そこで,
の種類数が高々10通りなのを考慮すれば,
に対し,
なる個数を
とすれば
![[x^M] \prod_{i=1}^{10} (1+x^i)^{f(i)}](https://chart.apis.google.com/chart?cht=tx&chl=%20%5Bx%5EM%5D%20%5Cprod_%7Bi%3D1%7D%5E%7B10%7D%20%281%2Bx%5Ei%29%5E%7Bf%28i%29%7D)
となる.
これはちょっと主客転倒っぽい.
は
となる. あとは
FFTしまくればok.
種類数を
とすれば 計算量
.
奇数個という条件を入れてみる.
今まで選んだのが奇数個なら, 次の種類で奇数個選べば偶数個になるし, 偶数個選べば奇数個になる. 偶数個も同様.
だから, evを
, odを
とすれば, 4回
FFTをすれば次の状態に遷移できる.
の倍数個選ぶ方法を求めたい.
である. これで提出したがTLEだった.
だが,
なのがでかすぎる. ちょっと工夫をする.
について,
までの項だけを考えればよい.
FFTする側もいままでの総和だけ保持すればいい.
これでちょっと計算量が良くなったはず. これで提出するとACである.（計算量は謎だった）
提出
C++
Submission #34567007 - NEC Programming Contest 2022 (AtCoder Beginner Contest 267)
反省
どの問題も面白かった. Exは998問題だが, 解けてよかった. 998問題の特訓をしたのが毎回効いている.
もうすこし素早く正確な実装ができれば, Fも解けたのかなと思う.
Gも橙998だからあとで挑戦してみようと思う. もし解けたら追記する.
