naoya_t@hatenablog

いわゆるチラシノウラであります

AGC埋め(先日のAGC 030の問題を解く大晦日)

晦日にC, D(ともに1000点問題)を解いてみた
と言っても両方とも30日に開いたけど解けず、31日にも考えたけど解けず、Dに至っては解説を見たけど大事なところが分からず人の実装を見てなるほどと思ってAC取れた次第

続きを読む

Single Round Match 745 - Fun and Unrated

12/28(金) 11:00-12:??

Div I/II混合で75分で6問、という謎のSRM(unrated)が生えてたので起きてたら出ようと思っていて、起きてたので(レジぎりぎり間に合ったので)出ることになった。

intervalとそのchainに関する6つの問題。(200-300-500-600-800-1000)

続きを読む

LeetCode: 312. Burst Balloons

https://leetcode.com/problems/burst-balloons/

LeetCodeのTop 100 Liked Questionsを埋めてて最後に食べ残して*1解説ACした問題。

ざっくり訳すと

風船がn個あり、0n-1 の番号が振られている。i番目の風船には番号 a_i が書かれている。
すべての風船を割るように頼まれているが、風船を1つ割るときに

  • 割る風船に書かれている番号
  • その風船のすぐ左にある風船に書かれている番号(左に風船が存在しなければ代わりに1)
  • その風船のすぐ右にある風船に書かれている番号(右に風船が存在しなければ代わりに1)

の3つの数の積と等しい枚数のコインがもらえる。(風船を割ると、そのすぐ左・すぐ右にあった風船は隣りあうことになる)

風船を割る順序を賢く選んだときもらえるコインは最大何枚か。

制約:
0\le n\le 500
0\le a_i\le 100

といった問題。
5万2千人ほどにしか解かれていなくて、Top 100 Liked Questionsの中では難しめなのだと思われる。

*1:鍵がかかっていて有料会員しか開けない問題が1つあるけどそれとは別。

続きを読む