いろいろな記録

大学院生やってます

2020/05/05

スマブラが楽しい休日。

研究

  • 文献 : 3h

休みすぎ。

 

競プロ

D - Face Produces Unhappiness

解説AC : 40分

この手の問題がやはり苦手。当然シミュレートできる操作ではないので、結局この操作ってこういうことだよね、という「結果に注目した時の単純化」を模索するべし。

今回は、結局1回の操作につき最大2人まで不幸→幸福にできるので、それを数えようというところに帰着。

D - 756

自力AC : 25分

いい反応ができた。約数の個数は、各素因数の次数(累乗でかかってる数)プラス1を素因数ごとに掛け合わせていったもの。 75 = 3 \times 5 \times 5なので、素因数分解の候補としては a^2\times b^4\times c^4,\, a^4\times b^{14},\, a^2\times b^{24},\, a^{74}が挙がる。あとは、 n!素因数分解し、各パターンについて可能な場合の数をコンビネーションで計算して出していく。

素因数分解するライブラリを手際よく問題に合うように改造できたのでよし。

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分

 X_{i}から見て2Dの距離にあるものを二分探索でリスト化、まではできたが、そこから区間への加算クエリをどう高速化できるかわからず、TLEが取れなかったので解説を見た。

imosのシミュレートをカウントと一緒に進めていけばいいというのは新しい発想で面白かった。すごい。

参考

 

 

英語

  • DMM英会話 (streak : 1)
  • Word Power Made Easy : 0.5h

毎日やらないと会話は鈍ってしまう。できればstreakは切らさないように。

 

---

明日も頑張りましょう。