精進メモ 2021/04/5~ - ツバサの備忘録

先週はモンハンしていたら一週間が終わりました。

ARC049 D - Convex Sequence
ARC107 E - Mex Mat
ゆきこ
GCJ 2021 Round 1A
AGC053
- A - >< again
- B - Taking the middle
ABC198

ARC049 D - Convex Sequence

問題
 提出コード
$i(i + 1) / 2$ をひたすら両側で生成することになるので、これをうまくまとめていければ良いです。 $i$ は $\sqrt{M}$ までに収まるので、DPの添え字として持つことができます。
$dp[i][j] = i$ まで見て、総和が現在 $j$ となっているもののパターン数、というDPを考え、左側と右側をマージしていきます。
あとは、最小値が0でないパターンをうまく考慮するよう、累積和をとりつつマージができれば、答えが求まります。

ARC107 E - Mex Mat

問題
 提出コード
実験ゲーです。大きい $N$ を入力すると、右下の方は対角線上の値が同じになります。
上4行、左4列程度だけ計算すれば、あとは対角線の長さを調べることで、答えを出せます。
提出時は完全未証明です…ここが課題ですね。
初手実験ゲーだ、という部分から時間がかかりました。小さいケースで法則を探すのも大事ですが、大きいケースを試すのも重要ですね。

ゆきこ

yukicoder contest 290 - yukicoder

No.1471 Sort Queries

区間に存在している文字をソートすればよいので、a ~ zそれぞれの区間に含まれる文字ごとに個数を求められれば良いです。
ということで26本の累積和を計算しておしまいです。

No.1472 作為の和

初手実験です。
$N \neq 0$ の場合、 $29 \ldots \times 30\ldots 1$ が $89\ldots$ になっているように見えるので、これを出力(本番は未証明)しました。
$A \leq B$ という制限を見落としていて1ペナ + かなりのタイムロスをしました。

No.1473 おでぶなおばけさん

問題を読んだ時点でこの問題を思い出したのですが、結構違う問題でした(二分探索 + 最短路という意味では同じですが)。競プロを始めたばかりで、yamadさんに解法を投げてもらって実装した記憶がよみがえりました。懐かしいですね…
重さを二分探索します。重さを一つ固定すると、通れる道が決まるので、その中で1から $n$ にいけるかどうか愚直にBFSをすればOKです。

No.1474 かさまＪ

問題の設定が普段全く見ない形なので少し困惑しましたが、解くとその条件が必要になりなるほどなぁ、となりました。
ある人について、qを混ぜる、と決めた時点で、その人には合計 $L$ 個以上のp,qをあげることが決まります。
重要なのが $S_{i} \lt L$ という不思議な制約です、これのおかげで、qを混ぜる相手には、先に合計 $L$ 個渡してしまえばよいことがわかります。すると、qをあげた個数の合計と、qをあげた人数がわかれば、そこから既にあげたpの個数を計算できるようになります。
$dp[i][j][k] = i$ 番目の人までみて、 $j$ 人に対してqを渡し、その合計個数が $k$ になるようなパターン数、とします。
初期値は $dp[0][0][0] = 1$ です。
$dp[i][j][k] = dp[i-1][j][k] + \sum_{x = 1}^{S_{i}}dp[i-1][j-1][k-x]$
という遷移ができあがります。総和の部分は、dpの累積和を別で用意してあげることで簡単に高速化できるので、このdpが $O(N^{2}M_{q})$ ほどで解くことができます。あとは、 $j L - k$ が正でかつ $M_{p}$ 以下であるような $dp[n][j][k]$ に対して、余ったpを自由に割り振る $_{n}H_{M_{p} - (j L - k)}$ をかけてその和を取れば答えです。

GCJ 2021 Round 1A

多分通過したはずです。

Code Jam - Google’s Coding Competitions

Appen Sort

小さい方から貪欲でOKです。ギリギリの値にしたいので、
$A_{i-1} \lt A_{i}$ であればそのまま
$A_{i-1} + 1$ を $A_{i}$ の状態から作成できればその値に
そうでなければ $|A_{i-1}| \lt |A_{i}|$ になるように10をひたすらかけていけば良いです。
$|A_{i}|$ は最大でも $O(N)$ で収まりますが、18桁は軽く超えるので $A_{i-1} + 1$ を作成するパートはstringで処理する必要がありました。
文字列比較なんかも頑張って実装すると、無事ACです。適当に書いたら1ペナ出しました。

Prime Time

Med制約までです。
$\sum N_{i} \leq 100$ 、と書かれています。
全体の総和が49900で収まります(はじめ、 $2153600$ だと勘違いしてしまい、途方に暮れていました)。ので、取り得る値、つまり1 ~ 49900に対して、愚直に素因数分解を行い、総和側が積と一致するか、そもそも作成できるか、をチェックしても間に合います。

Hacked Exam

こちらもMedまでです。
1人の場合、答えは $\max (S_{1}, Q - S_{1})$ です。
前者であれば入力の文字列をそのまま、後者であれば反転して出力します。
2人の場合、 $A_{1,i} = A_{2,i}$ の個数 $s$ と、そうでない個数 $d$ に分けます。
$s$ 個の問題に対しては、二人とも正解、もしくは二人とも不正解のどちらかです。 $i$ 回正解したとしましょう。
1人目は、 $S_{1} - i$ 回(これを $x$ とします)、2人目は $S_{2} - i$ 回(これを $y$ とします)回正解する必要があります。
残っている $d$ 個の問題に対しては、少なくともどちらか一方が正解するので、 $x + y = s$ となっている必要があります。
ということで $x,y$ にもとの値を入れてあげると、 $S_{1} + S_{2} - 2i = d$ という方程式ができます。これにより、 $i$ が確定します。
後は、 $s$ 個の問題に対しては、
$i \geq s - i$ であれば、二人の入力をそのまま利用し、1問あたり $\frac{i}{s}$ の確率で正解できます。
そうでなければ、二人の入力の反転を出力し、 $\frac{s-i}{s}$ の確率で正解します。
$d$ 個の問題に対しては、
$x \geq y$ であれば、1人目の出力を利用し、 $\frac{x}{d}$ の確率、そうでなければ2人目の出力を利用し、 $\frac{y}{d}$ の確率で正解します。
あとは、出力をまとめ、確率の総和を求めれば答えです。分母は最大 $sd$ 、分子もそこまで大きくならず、オーバーフローはしません。

AGC053

順位表みて少し焦ったかもしれないですね。解ける問題をきちんと素早く解かないと置いて行かれますね…

All Submissions - AtCoder Grand Contest 053

A - >< again

基本、ギリギリを攻めた数列を配置すれば良いです。個数を固定し、ギリギリ配置の数列を個数分用意した後、残った数を均等に割り振り、条件を満たしているかチェックすれば良いです。
個数を1から試してTLEしたので、単調性があることを利用し二分探索に切り替えました。

B - Taking the middle

二人分の操作一回で、常に真ん中にあるどちらか片方が消えます。右側を取ると、左側の右端が消え、逆も同様です。
半分で折りたたむと、並んだ列をそれぞれペアにしていき、その両方を取る(取らない)、片方のみを取る、の3パターンに分かれます。
両方取る個数と取らない個数は同じ、かつ、括弧列の条件を満たしている必要があります。片方のみを取るケースはペアの数字のうち大きい方を選べばOKです。よって、あとは両方取る、取らないパターンをうまく割り振っていけば良いです。
この部分を詰めていく(省略)と、優先度付きキューを用いて、上手く交換をしていけば答えを求めることができます。

ABC198

All Submissions - AtCoder Beginner Contest 198

C - Compass Walking

誤差が怖いので二分探索をしました。
$\sqrt{x^{2} + y^{2}} \leq Rk$ を満たすような $k$ の最小値が答えです。
移動回数 $k$ を決め打つと、ルートの部分を二乗により外せるので、安全に比較できます(オーバーフローに注意)。
$k = 1$ もしくは $k = 2$ の場合だけコーナーケースになるので、この部分だけ気を付けて実装すればOKです。

D - Send More Money

ICPCで無限にありそうです。楽、かつ計算量をキチンと把握できる解法をひねっていたら時間がかかりました。
違う文字で同じ数字になることが許されていないことに気づければ、一気に楽になります。文字の種類が10種類を超えていたらまず答えはありません。そうでない場合は、最大10!通りを全探索すればOKです。next_permutationをまわすのが楽に実装できると思います。

E - Unique Color

よくみるDFSです。BFSだと計算量が2乗になってしまうので、DFSでカウントを増やしたり減らしたりします。