6完57:34 0ペナでパフォ2160くらい
ABCは比較的安定していていい感じですかね
A Six Characters
ひさびさにやるだけ、場合分けしてもいいんですがめんどいのでwhile文を回します(AC 1:21)
B At Most 3 (Judge ver.)
3つしか選ばないので三重ループをかきます
0追加すればいいな～と思ったけど、めんどくさくて普通にそのまま書いた
set使って出現判定したけど普通に通った、遅い言語だと落ちるのかも？(AC 4:53)
C Poem Online Judge
久しぶりに簡単めなCがきましたね、setの練習です
「オリジナル」かどうかの判定は、setで出現したかをみればよいです
あとはスコアの最大値が更新されたかをチェックするだけ(AC 7:39)
D At Most 3 (Contestant ver.)
うーーーーん、構築つらい、B問題で内容は理解できているのが救いですね
とりあえずW = 10^6で満たすならなんでも満たすのでW = 10^6について解ければよいです
こういうのいくつかパターンはあって、一番多そうなのがbitでごちゃごちゃするやつなんですが、あんまり思いつかないので他の方針も考えてみます
フィボナッチ数列ってうまく和に変換できた気がするので調べてみると、「ゼッケンドルフの定理」という定理にあたります...がこれは選ぶ数を3つに限定していないので直接使えません、こまった
で、なんかどうしようかなと思っていると2桁ずつに区切って1~99を用意すると、それぞれ独立に決められるのでこれで解けることがわかります
10^6についても、10000 + 990000でできるのでコーナーケースの心配もありません
ハマる前になんとかなってよかったです
(AC 18:43)
E Takahashi and Animals
い つ も の
ABC229-F Make Bipartiteをはじめとして、何回か出題されているタイプのDPです
こういう円環系のものは1をどうするか？を状態として追加で持っておけばよいです
dp[i][j][k] = i番目まで見てiが塗られているか(j=0,1),1は塗られているか(k=0,1)
という風に定義します
あとはこれに従って計算するだけです、なんか頭が壊れてて整理するのに時間がかかってしまった...
(AC 34:35)
F Two Spanning Trees
問題文を読みますがちょっと条件が複雑です
いろいろ状態をもってDPとかできるのかな～と思いますが、Nが大きいのもあって難しそうです
パッとみ不可能に思えるんですが、順位表を見ると時間の割に通されているので「実は簡単な貪欲とかでできるのでは？」とあたりをつけます
一番素直なのはBFS,DFSなのでそれを考えると、厳密な証明はできませんが、それぞれT2,T1に対応していそうです
ということでこれが合っていることを信じて実装すると通ります、やったね(AC 57:34)
G Intersection of Polygons
次にGCJが控えていることもあって休憩してました、また考えてみよっかな
総括
ちょっといつもとタイプが違ったかもしれませんが、とりあえず黄パフォとれてよかったです
賞金は...ちょっと厳しいかな、いつになったら取れるのやら
