問題概要 長さL( 考えたことなど (easyが酷い点数で残り時間も少なく、焦った状態で問題を開いた。いつもはDivision Summary見てから問題開くのに今回は余裕がなくて忘れていた) (問題を下から眺める。確率か。しかも複数求めるやつだしどうせDPだろう)。 問…

問題概要 [0,X)*[0,Y)(X,YB->C->Aというルートで巡回する。ある地点からある地点まで移動するにはマンハッタン距離に比例した時間がかかる。時間が[minT, maxT]に収まるような3点の選び方は何通りあるか求める問題。 考えたことなど (まず問題を下から眺める…

結果。 またしてもレーティング上がって2400を突破した。1年前の青だった自分と比べても特に解ける問題の範囲はそんなに変わってないのにとても不思議。easyに安定感持たせてmediumから苦手意識を取り除くだけでこんなに変わるのか…。 最近は明らかに好調な…

問題概要 ある数字列X(Xの長さは50以下)がある。いくつかの適当Xを一文字だけ置換した数字列が与えられるので、Xとして考えられるものがいくつあるか求める問題。 解法 候補はたかだか10*50しかないので全生成してチェックすれば良い。

問題概要(適当) 板をあるルールに従って並べる。並べ方が何通りあるか求める問題。 解法 素直に(長さ、最後に使った板のタイプ、最後に使った板は縦か横か)を状態としてdpする。計算量結構怪しいけど間に合う。 …というのがwriterも引っかかった間違いで、こ…

問題概要 長さL1,L2( 解法 公約数全部試すのは高度合成数のときに危ないし、有名問題っぽい割に知らなかったので敬遠してたけど、大量に通されていたので愚直にやって間に合うと判断して愚直に書いた。ただ危ない感はあったので気持ち程度の枝刈りを入れた。…

問題概要 長さN( 解法 全部符号をひっくり返して2回考えるようにすれば絶対値最大化は単なる最大化で解けるので以下それで考える。 幅Lの窓をスライドさせて考える。窓の中にある負の数字を覚えておいて、絶対値の大きい方からk個の和をとって素の部分和に2…

問題概要 コマンド列を短くする最適の置換を求める問題。 解法 割り当てを全通り試してDP。貪欲にやっても良いので適当にreplaceしてlength調べるだけでも多分大丈夫なはず。

問題概要 指定された日以降で、年が(月*日)で割りきれる最初の日付を求める問題。 解法 一日ずつ進める。1日でダメだったら次の月に行くとか、年をまたいだら無条件でOKとかいろいろあるけど、どうせ間に合うのだから余計なことはせず愚直にやってOK。

問題概要 うるう年かどうかの判定をする。 解法 DFA。

結果。 3/4完。D言語で連想配列の初期化がなぜかうまくいかなかった。あとDDTが^^使ったときにエラーだと怒ってきたりして困った。さらに提出してみたらコンパイルエラーで、エラーの詳細が見れずに絶望的な気分になった。clar出したら10分くらいで対応して…

問題概要(適当) カレンダーを手動で合わせるとき何回余分にめくる必要があるか求める問題。

結果。 4完。とはいえ1問はジャッジ解にミスがあって、そのミスに終盤まで気づけなかったので実質3完みたいなものだった。C問題で平衡二分探索木が欲しいなーと思ったけどsetとheapで何とかなった。一度は何か平衡二分探索木書いてC問題でverifyしたい。Trea…

問題概要 A[i] 解法 貪欲に選ぶ。S>=B[i]なiがあればそれをクリアし、なければS>=A[i]なiのうちBが最大のものを選べばよい。heapを使えばN*log Nで解けそうな気もするけどN