ABC289 (2023/02/11)
〇A問題
Yuto.icon 最初，入力をbinで受け取って全体をXORしようとして時間ロスしてしまった．無駄にきれいに書こうとせず，愚直にやってAC
TK.icon単純に一度入力を受け取って0なら１、1なら０をprint
CarpDay.icon単純に一度入力を受け取って0なら1，1なら0をリストに格納して，最後にまとめてprint
おたふく.icon↑同様
まーす.icon1111111(10)を用意して、そこから与えられた2進数sを引く方法、与えられた2進数sの2の補数をとったものxをf文字列で出力。自分は繰り返し文でxをつくったが「~」でよさそう。
〇B問題
Yuto.icon 言われていることをそのままやる．連結成分→みんな大好きUnionFind．ついにB問題でUFが出るようになったんですね．．．インフレ怖い
TK.iconUnionFindでできそうだと思ったが、昇順のリストを準備して、レ点が連続している範囲を考える。連続している範囲を反転して昇順のリストの同じ範囲に代入
CarpDay.icon問題につられてUnionFind使ったけど，↑の通りそんな必要がないことに終了間際に気付く．知っているとついつい使いたくなるよね（その１）．
おたふく.iconレ点分だけ昇順リストを反転
まーす.icon↑と同様reverse使用
〇C問題
Yuto.icon 最初問題文の意味が全く理解出来なくて一旦飛ばした．Dが簡単だったので数分後戻ってきた．落ち着いて問題文を読んだら「これただの全探索やん」と気付いたのでbit全探索してAC
TK.iconいろいろ考えたが全探索ができそうだということに気づいた。数日前にbitdpをやっていたので集合の組を二進数で表現して全探索できることを活用してAC
CarpDay.iconbitDPで解きました．．．時間消費＋2度のRE．．．知っているとついつい使いたくなるよね（その２）
おたふく.icon解き方を思いついたときには時間ギリギリ、コードを実装できた時には数分オーバー
〇D問題
Yuto.icon Dの割にはめちゃくちゃ簡単なdp．dp[i] := iに到達できるかどうかとして，遷移は各iからi+A[i]に配る．
TK.icon単純なｄｐだから普通にやってクリアと思ったが、サンプルすらあっていない。Ａの配列を前から1回ずつしか使っていなかったため違った。サンプルの例を見ると複数回使っている。条件が足りていないことに気づいて修正したが一部WA。修正します。
CarpDay.icon何でDのDPの方が簡単なの？．．．と思ってC問題がDPでないことに気付きました．．
おたふく.iconBで時間がかかり、Cで分からずテンパったままDだけ覗きに来ると、とても簡単なDP。...だと思ったらTLE & WA。制限時間後にCを解いてから戻ってくると自分でも意味の分からないミスに気付く。落ち着きが欲しい。
〇E問題
Yuto.icon ぱっと見制約が厳しそうに見えるが，落ち着いてみるとそうでもない．毎回最短経路求めたりしても良さそう．．．というのは分かったけど，何をすれば良いのか分からない．UnionFindで二部グラフ判定してみたり，最短経路の長さの偶奇で判定してみたりしたけど無理だった．
CarpDay.icon制約リストの下2つをよく確認せず，T≦1000，N, M≦2000から各ケースをO(N+M）で解く必要あると思い込み，時間内に方法思いつかず．．お手上げすぎて，コンテスト内残り時間でC問題解き直しました．コンテスト中は諦めず，問題をよく読んでヒントを探し求めることが大切．
TK.iconこれ以降見ていない
おたふく.icon初見でdpとdfsの併用で解けそうと思いコードを実装すると、恐らく解くことは出来てるとは思いますが探索範囲を上手く削れずにTLE。最短経路を求めるのにはdfsよりbfsの方が向いていることを学んだ。
〇F問題
Yuto.icon これ以降見てない
CarpDay.icon移動のたびに領域候補が増えるので，複数の領域を効率良く記憶する手段が必要で，その方法知らないから多分解けないだろう，と踏んで諦める．解説の最初の一文一次元で考えるを見て，問題を分割するという考え方の基本を思い出す．意外に容易にAC．