AtCoder参戦記録

C問題簡単だったはずなのに、DFS解法に走ってしまってTLE地獄から抜け出せず。30分くらい時間を溶かした後に、別方針で一から書き直してAC。すごく短いコードだった。D問題は時間切れになったが、終了後10分でACできたから、C問題の時間ロスが悔やまれる。

Cまでしか解けなかったが、31分で解けたら、緑パフォにはなるんだな。

かえでさんが凄い点を叩き出した。Heuristicは年齢も性別も関係ないと勇気づけられる。生成AIをうまく活用というのも、まるで若手のよう。
https://atcoder.jp/users/kaede2020?contestType=heuristic

Dまで４完で久しぶりに緑パフォ行けるかも。
A問題でまさかのWAを食らったが、Cはすぐ解けた。
D問題はlong longでもオーバーフローする場合があるのに気をつける必要がある。

・全マス別の色にする
・BFSで最短ルートを全目的地に対して求める。
・目的地を内部変数として色と最短ルートをルール化する
・全目的地を通して使っていない色は別の１色にする（Cの削減）
・状態を共有していない色どうしを統一色にする（Cの削減）
・一度も交差しないルート同士を同じ内部変数にする（Qの削減）
・邪魔石を置いて似通ったルートを統合する（Qの削減）

Qを削減するため、（色と状態）に対するA,S,Dの値が全て同じであれば更にQを共用できることに気づき、実装を試みたが最後まで正解を出せず、単に重複を避けた圧縮にとどまる。

Tに余裕があるので、似たような経路は多少遠回りしてでも共通化するのがポイントなんだろうけど、邪魔板を置いてみるくらいしかアルゴリズムが思いつかず。邪魔板の位置と方向で山登りすると、5個くらいQは減らせました。

↓ 0001の例とヒートマップ 

BFSではなくダイクストラを使っている人がいました。確かに、未使用のマスを通る場合はコストが高く付くように、重み付きグラフにしてやれば、経路の統合ができそう。
https://note.com/tetra4_cp/n/n6be697ae0f1d

C問題まで19分で解けて行けると思ったら、それ以上解けず。
D問題はナップサック問題のDPなのはすぐ分かるが、DPが構成できず。。

C問題まで解けましたが、みんな解けていた灰diffレベルだった様で、また瓦2枚に下がってしまった。
D問題も解き方は分かったが時間切れ。

思いつく実装は出来たが、なんか順位低い。山登りとか焼きなましには勝てないか。

今日は何故か３０分遅れて開始。Cまで解けましたが、endlの時間が長すぎてTLEで苦しみました。
デバッグ用にcerr << endl;が残っていただけでTLEだった。

Bに手こずって時間取られてしまいましたが、Cは意外と早く解けた。Dは３分で諦めて、Eに１時間取り組んで終了。Cはbit全探索。

Cは、Union-FIndを使って解けました。アップデートするOSをアップデート先のOSグループに融合していく感じ。このアルゴリズムを実戦で使えたのは確か２回目。

最初の週末の時点で、AAを渦巻き配置のトレントで護衛する方針を立て、その時は100位以内。
一重の壁では、反対側のトレントが認知されていない時に、知らずに仲間で突き進んで偶然見つけられてしまう事があるので、2重の壁にしたらグンと上がった。
ただ、左上の(-2,-3)の位置にトレントを置くと、何故か1ケースだけWAになる不具合があり、最後まで解決できず。終了後の3000ケースのシステムテストでも引っかかる恐れあり。

その位置が森の入口になるレアケースであることが判明。初手だから不要と思って入れていなかった確認済み判定を追加したところ、全てAC。

Cは累積和とIMOS法でできるかと思いきやとなり出来ず。累積和だけO(N^2)のTLE解までは作れた（サンプルはACするが意味無し）。解説を見たが、これは全く思いつかず。

CはDFSで解けましたが、バグ取りに３０分以上かかった。
DはDPなのは分かったが、能力がないので諦めてｗ，
Eは長さと本数のペアを管理すれば解けそうだったが時間切れ。後で続きをやってみよう。

Cのバグ取りが終わらず２完で終了。。
そして今CもAC。。。戦略はあっていたのに。

今日ABCかと思って21時にスタンバったら19時からAHCだったorz
2時間でもやりたいことは出来たかな．というかそれくらいのアイデアしかないとも言える．

１．全部の山をLで埋める．
２．残りを見ながら，大きいカードから順に載せられるところが無くなるまで山に積んでいく．

なんと、前回のAHCの1位の人は、延長戦でさらに工夫して、全ケース満点を取れるプログラムが出来たそうです。しかも、山登り解法に近いものの、演繹的なアルゴリズムっぽい。
https://yosupo.hatenablog.com/entry/2025/09/15/213945

Cまではミスりつつも順調。
Dは公式解説よりも、snukeさんの逆から解く方法が秀逸。
E問題も解けそうで解けず。乱択という戦法は思いつかなかったが、思いついても良さそうで悔しい。

点数が高いのでやる前から難しいのは分かっていたが、、ここまでとは。

D問題、２枚のBFSという戦略自体は合っているようだが、実装がうまく行かない、、、

とおもったらif文のバグだった。

D問題まで解けた！いわゆるimos法ですね。
E問題を悩む残り時間もあったが、貪欲法ではなかったようだ。

交差しない有効な木構造を構築するアルゴリズムが思いつかず．
score関数だけは作れたのですが，結局提出０で終了

時間が合わず参加できませんでしたが、後から解きました。Cまでは解けました。Dは単にDP組んでも駄目なようで無理。

D問題。multisetの二分探索をするとき、multiset::lower_bound()を呼べばO(log(N))だが、std::lower_bound()を呼ぶとO(N)になってしまう罠。multisetのインスタンスからメソッドを呼ぶ必要がある。

最近、C問題のレベルが高い。

C問題。解けそうだったが時間切れ。終了直後にAC。一部reverseしてなかっただけだったorz

D問題、サンプル３つは通ったが、やっぱりだめだった。
絶対値でソートしたものが等比数列であることは必要条件で、あとは、交互にプラスマイナス、もしくは全部プラス、もしくは全部マイナスならOKかと思ったが違うみたい

そうか、絶対値にしてソートではなくて、絶対値を基準に（値は絶対値を取らずに）ソートすれば良いのか、、、
https://atcoder.jp/contests/abc413/submissions/67363952

↑のもう一つのテクニックとして、以下のif文。

if (a[i]*a[i+2] != a[i+1]*a[i+1]) ok = false;

少数になるリスクが有る割り算を避けて、整数の掛け算だけで等比数列を判定する方法。

Dが逆から解けるのが未だに理解できない。

Dは5WAが消せず諦め。Eも解けたと思ったがTLE。悔しさなし。

B問題に手こずる。setはランダムアクセスイテレータでないため、イテレータfor文で回す必要があることを学んだ。

余り何色も混ぜようとするとパレット構造が複雑化しそうなので、ターゲットの色を最も良く表現できる三原色を選び出す、というアプローチで解きました。

解法１
・色をCMY３次元空間のベクトルとみなす。
・ターゲット色を任意に選んだ３色の絵の具ベクトルに成分分解。
　ここでは、逆基底を求める方法を用いた。
　ターゲット色(c, m, y)　＝ a*絵の具1(c, m, y) + b*絵の具2(c, m, y) + c*絵の具3(c, m, y)
・この分解を持ち絵の具の組み合わせで全探索し、最も良い組み合わせを三原色とする。
・色を抜く操作は出来ないので、このa, b, cが全て正でなければならないが、ここでは、min(a,b,c)が最大となるものを三原色とした。
・選んだ三原色をa,b,cの配合で混ぜるようにウェルを色々組み替える。
この解法は精度が高いですが、ウェルの組み換えに手数を多く消費するので、Tが10000以下のケースでは対応不能。

解法２
・解法１は手数を消費し過ぎなので、もっと手数の少ないアルゴリズムを考えた。
・a,b,cを演繹的に求めるのではなく、a,b,cは０か１しか取らないとして、これもbit全探索して、最良同士を更に比較して三原色を選定。
・一度作ったウェルに残った絵の具もリスト化しておいて、ある程度近い色が残っていたら、新たに作らずそちらを提出。
・0か１なので、ウェルの組み換えは不要となり、1000色で最大でも2000ターン程度で完了。

実際は最大ターン数を見て解法１と２を切り替え。
中には、解法２の方がスコアが良いケースもあるので、その場合は解法２を提出。

Cの解法に気づくのに時間がかかってしまった。Dは解ける気がせず。

自分的にはまずまずの出来かな。dfsに慣れてきた感じ。

なにこれ、、爆死。

D問題で初めて多始点BFSを使って残り10秒でAC出来た。嬉しい。
しかし、B問題でハマって順位はそこそこ。

D問題、3^10回全探索できるのは気付いたが、3^nの全探索の手法が分からず。A問題は、いかに速く解くかですが、この解き方が良いと思いました。

REP(i,N) vis[S[i]-‘a’]=1;

文字ごとの出現の有無をこの一行で集計。

ブロックを設置しない愚直解から先に一歩も進めず。同じような人が435位に群がっている。。。

D問題。平行なペアの組み合わせを除くのは分かったが、幾何学的に三角関数使いまくったら何故か22WA