2020/10/24、25に開催されたコンテストの感想

AtCoder Regular Contest 106

A

3^A+5^B=Nをみたす正整数の組(A,B)の有無

• オーバーフローに気を付けて全探索
• pow関数に頼るとまずいらしい

B

グラフの各頂点の数をaiからbiにできるか

操作：辺の片方の頂点+1、もう片方-1

• 総和は不変
• 総和が等しいならできる
• 非連結の場合を忘れた
• union-findします

C

区間スケジューリング問題の解法二つの出力の差をMにできるN個の区間を構築

• M=0：全部独立な区間
• N=Mはあり得ない：どちらも1つは区間を取る
• abs(M)+1=Nもない：片方1、もう片方全部しかないが後者を満たすのは全区間独立のみ、前者と矛盾
• 実はabsではない
• ところでN=1でM=0は最初の条件より例外
• のこり：

ーーーーーーー

　ーーー

　　　ーーー

　　　　　－－－

こんな感じ

• 区間の右端によるソートは最適なことに気付くのが遅れた
• M<0はあり得ない

D

1~KのXに対してΣ L Σ R (AL+AR)^X mod 998244353 (L<R)

• 時間があればあるいはという感じ

Codeforces Round #678 div.2

A

aを並び替えてΣΣ aj / j == mにできるか (i:1~N, j:i~N)

• 総和が等しいかじゃない？
• そうでした

B

各行の和、各列の和が素数となるような、素数でない非負整数のN*N行列をつくれ

• 0が使える
• 1が使える
• 2は素数、3は素数
• [[1 1] [1 1]] と[[1 1 1] [1 1 1] [1 1 1]] の組み合わせ

C

配列からxの二分探索に成功する、n要素でxがposにある配列の総数

• 探索ルートは一定で、各ループでleftとrightどちらを動かすかは決まる
• 各場所、x以下のみ/x超のみ/どちらでも の一つに決まる
• これを満たす数列の数え上げ

D

根付き木で1対多のおにごっこ。最適な行動で捕まえられる人数は

• 二分探索を試みるも通らず
• 方針：葉から見て、葉のほうに人を可能な限り逃がして、逃がし切れるか

Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1)

A

Σaibi=0なるbを構築せよ 要素数は偶数

• 1項めと2項めで0にできればいい
• a1b1=-a2b2
• b1=a2, b2=-a1

B

1~mnの要素が1つずつ含まれるn*m行列の行ベクトルと列ベクトルが与えられる。復元せよ

• 共通の要素を含む行ベクトルと列ベクトルの組みを探して頑張って復元するだけ。でも大変

C

aのいずれかを使ってai+jとし、bのすべてを作りたい。jの最大と最小を最小化せよ

• （案の定ではあるが）解けず
• 方針：各bを作るときのjの最大の最小値と最小の最大値を見つけてそれらを満たす最小区間→×

D

商品を 置いた/買われた+買われた物 の履歴が与えられる。矛盾の有無を判定し、商品を置いた順を復元せよ。客は置いてある最安のものを買う

• 商品がないのに買われたパターンは矛盾。排除
• 棚をpriority_queueで管理しつつ操作を最後から見ると、置いた時に何を置いたのかは決まる
• 最安のもの以外が買われた情報があれば矛盾 あとはok