- やった回: ABC361
- 成績: ABC3完 / 1ペナ / 75:25(ペナ込み) ※21:30頃参加
- パフォーマンス: 717(unratedなのでコンテスト終了時点での推定)
30分ほど経過してからなんだけどとりあえず参加してみた。比較的すんなり3完できたのでとりあえずよしとしておく。
たらればの話をしてもしゃーないとは思いつつ、所要時間をそのまま30分減らしてみたらだいたい現在のレート程度のパフォーマンスだったのでそんなもんかなぁという気持ちになっているがこのDは450点のわりにワンチャンあったと思う。
A問題: ABC361-A Insert
「絶対に途中に値を入れるメソッドあるでしょ」と思いつつ愚直にやり、コンテスト後に他の人の提出読んだら案の定 Array#insert あったじゃんんんんんんんん
B問題: ABC361-B Intesection of Cuboids
ABC343-Eで「絶対計算方法覚えられない」って言ってた直方体の重なり体積を使う問題。
とは言えこっちは座標全部正数だし計算するだけなのでだいぶマシで、とか言って案の定計算方法を覚えてなかったので過去の自分に甘えて記事を読みつつ図を書いて何をしたらいいのか理解。 配点250点にビビりつつもすんなり解けてよかった。解き方の「気持ち」は分かったので、多分次は大丈夫。
C問題: ABC361-C Make Them Narrow
全要素をソートした後、連続した N-K 個を選んだときの差の最小値が答え。
問題文で「残った要素を順序を保って連結した」って言ってるけど別に順序を保つ必要は一切ない。
インデックスをeachする範囲を計算するのが面倒で、Ruby Silverの勉強で学んだ Array#each_cons を使って解いたら
TLEしたところが最高に格好悪いポイント。
D問題: ABC361-D Go Stone Puzzle
(upsolveしたコード) atcoder.jp
コンテスト終了時点では未提出。Nの制約上とりあえずシミュレーション出来そうだったのでDFSでメモ化再帰をやってみたけどサンプルの結果が合わんぞ？？？ってところで時間切れ。 解説はBFSで、まぁ言ってしまえば最短経路探索なのでそうねって感じ。でもDFSでも出来そうな問題だと思うので両面からやってみたい気はする。
多分文字列のままにしておくより配列にしちゃって取り回した方が楽なんだろうなぁ。文字置換に地味に手間取った。
(以下、upsolve後の追記)
DFSでもいけんじゃね？って思ったけど、スタンダードなBFSではTLEしたので難しそう。あと文字列じゃなくて配列にしたらもっと重くなった。
スタンダードなBFSだと「今の深さのノード」を持っているところの取り回しをかなり工夫しないとACするのは難しそうだった。
一方でACしたコードだとBFSっていうかどことなく一次元(？)DPというか木DPというか、みたいな雰囲気になっている。
