どうしても解けなかった。ただ、SIMDで無理やり高速化できれば通る予感がしていて、実際解説を見るとSIMD高速化で通せる可能性に言及されている。 そんな訳なので、大して経験もないSIMDで突っ張って通してみた。 解法 凝ったことは何もせず単に二重ループを…

フローの問題を履修しているときに出くわしましたが、解説とちょっとグラフの作り方が違ったので。 解法 葉であるマス目を頂点として同じ行or同じ列どうしの頂点を辺で接続し、フローグラフを構築する。 すると、Sourceを、Destinationをとしたときの最小カ…

結構シンプルなコードが書けて、説明としてもわかりやすいものになったと思うので残します。 本質的には公式解説などと何も変わりないので、新規性はないかも。 解法 手番の偶奇を考えるのは面倒なので、以下のようなDPを考える。 マスから先攻でゲームを開…

結構迷走しながら考察しましたが、何とか解けました。 解説見たらめちゃくちゃ賢い解法が書いてあってビビりましたが、自分の賢くない解法も残します。 解法 である各について、との間に辺を張った頂点の無向グラフの連結成分を考える。 まず、すべての連結…

計算量がよくわかりませんが、なぜかACできてしまったので書きます。(公式解説を見たら同じような解法が載ってました) 解法 問題の条件を言い換える。 まず、条件を満たすの組み合わせは、(であるような場合をさておくと)対称になるので、との関係はとりあえ…

公式解説では二分探索をうまく適用する賢い方法がとられていますが、私はそんなこと思いつくわけもなく… しかし、気合で数え上げることによってコンテスト中にACできたので解法残します。 解法 個以上リンゴが載っている皿のみ、小さいほうから考える。 もし…

ABCの解き直しをやっていて、ちょっと悩みましたがなんとか解き切りました。解説を見てみると、ちょっと効率の良い解法だったので一応残します。 解法 各島について西側からなめつつ、自身より西側のみを考える。自身より東側に仲の悪い島がある場合、その島…

コンテスト中に解法思いついたけど、計算量改善の実装が間に合わず無念の敗退… 結局、コンテスト後に自力ACに成功しました。しかし公式解説見てみると、解法が違う気がする。なので、一応解法残します。 嘘が含まれていたら教えてください。 解法 問題を、有…

導入 AHCではローカルテスタが用意されているので、手元で自身の実装の改善度合いを具体的な数値で見ることができます。 しかし、1個1個テストを回すのは面倒なので、当然、どうにかしてテストを簡単にできるようにしたいと思うでしょう。 そこで、一例とし…

早速本題 先週のABC237にて、順位455位、perf1860で、入青を達成しました。入水したのは昨年6月19日のようなので、入水時と同様、色変は半年以上ぶりということになります。 まだかなり水色とのボーダー上ですが、備忘録ということで。 入水したときから今ま…