2020/05/05
スマブラが楽しい休日。
研究
- 文献 : 3h
休みすぎ。
競プロ
- AtCoder : 6AC
D - Face Produces Unhappiness
解説AC : 40分
この手の問題がやはり苦手。当然シミュレートできる操作ではないので、結局この操作ってこういうことだよね、という「結果に注目した時の単純化」を模索するべし。
今回は、結局1回の操作につき最大2人まで不幸→幸福にできるので、それを数えようというところに帰着。
D - 756
自力AC : 25分
いい反応ができた。約数の個数は、各素因数の次数(累乗でかかってる数)プラス1を素因数ごとに掛け合わせていったもの。なので、素因数分解の候補としてはが挙がる。あとは、を素因数分解し、各パターンについて可能な場合の数をコンビネーションで計算して出していく。
素因数分解するライブラリを手際よく問題に合うように改造できたのでよし。
B - Two Arrays
解説AC : 30分
あさかつで解けなかった。難しい。解説ACしたがなぜこうなるのか証明できていないのでちゃんと見直す。
D - Saving Snuuk
自力AC : 25分
あさかつで間に合わなかったが後から解けた。スタートゴールが決まっており、かつ中継地点である両替所から通貨が変わる。スタートから円について見るダイクストラと、ゴールからSnuukについて見るダイクストラをして、各頂点を両替所とした時の手持ちに残るSnuukの数を計算する。あとは各年について、手持ちに残るSnuukの最大値を後ろから更新する。
E - Max-Min Sums
自力AC : 20分
組み合わせで見たら無理なので、各数についてmaxになる回数とminになる回数を数えるゲーミング。
F - Silver Fox vs Monster
解説AC : 60分
から見ての距離にあるものを二分探索でリスト化、まではできたが、そこから区間への加算クエリをどう高速化できるかわからず、TLEが取れなかったので解説を見た。
imosのシミュレートをカウントと一緒に進めていけばいいというのは新しい発想で面白かった。すごい。
英語
- DMM英会話 (streak : 1)
- Word Power Made Easy : 0.5h
毎日やらないと会話は鈍ってしまう。できればstreakは切らさないように。
---
明日も頑張りましょう。