ABC291 (2023/02/26)
〇A問題
Yuto.icon s.isupper()
TK.iconwataumi.icon上に同じ
CarpDay.iconaより小さいかどうかで判定．isupperの存在忘れていました．．．
まーす.icons.isupper()を使用(初めてで時間かかった)
おたふく.icon英大文字の判定できるものが何かあった気がして調べ、isupperを発見する。
i9.icon大文字小文字を数字に変換しようかとも考えたのですが、s.isupper()を使いました
〇B問題
Yuto.icon sum/len
wataumi.icon 0-index，sum(x［n+1:4*n+1］)/(3*n)，1回目は雑デバックでWA(涙)
CarpDay.iconソートして，頭と尾をスライスして，合計／個数
まーす.iconソート→delで前N個と後ろN個を消去→sum/len(sumのところにEXという変数を使ったが、これは一般的に期待値を表すのでsumを用いた方が良かったと後悔)
おたふく.icon -> CarpDay.icon同様
i9.iconremoveで愚直に最大最小を取り除いて、sum()/3*nで計算しました
TK.iconsort -> スライスn:4n -> sum/len 〇C問題
Yuto.icon DFSするだけ．終了条件のしょうもないバグで1WAしてしまった．もったいない．．
wataumi.icon場合分け、(key)x (value)set(y) の辞書を用いて判定、1回目はRE、何が悪かったのか、確証できていない。
CarpDay.icon指示通り動かして，到着点を集合に保存．到着点が集合内にあるかどうかで判定
まーす.iconset()を使って集合(x,y)の要素数がN+1かどうかを判別
おたふく.iconDFSがC問題に来るかなと疑問に思いつつもDFSで実装。上手な方法が思いつかず不格好ながらAC
i9.icon移動した位置を配列に格納しつつ、set()をもちいた
TK.iconkey:移動で到達した座標、value:到達回数の辞書作成。到達回数が一回以上の場所に来たら終了。メモリが多くなりそうだから最初別の方法でメモリ節約できないか考えて、原点に戻ってきたときの判定しかしていないプログラムを提出しWA
〇D問題
Yuto.icon DPっぽいなーと思いつつ，遷移が実装出来なかった．ひっくり返せるかは直前のみを考えれば良いから，DPなのはあってそうなんだけど．dp[i] = i番目まで考えた時の総和 % MODというテーブルを更新する方法が分からなかった．下のおたふく.iconを見て，二次元にすればよかったのか．．．となりました
CarpDay.icon最初に思いついた方法で合っていました．またMOD忘れてWAしてしまった．．
wataumi.iconひとつ前のa,bと現在のa,bの組み合わせにより場合分けする方針でコーディング、結果はWA。
wataumi.icon 追記：CarpDay.iconさんのアドバイスをもとにコンテスト終了後に解けました！
おたふく.icon1次元でトランプを1枚目から順に伸ばそうとして上手い方法が思い付かず、翌日2次元にすればいいことに気付く。
TK.iconmaxで2^nだから裏返せない場合を引けばいいと思ったが、条件分岐が多すぎて方針が違うかもしれないと思い別の方法を考えたが間に合わず。コンテスト後DPで実装しました。
〇E問題
CarpDay.icon終了5分前に思いついた解き方で実装．終了17分後にAC．悔しい．コンテスト中は一度WAのあとDAG判定とトポロジカルソートを使えば解けると考えて実装したものの，サンプルすら通らず．実装完成までの時間が無駄．「正しく動きそう」と判断してからコーディングに入るべし．
Yuto.icon 同じく，終了15分前に思いついた解き方が合っているか，解説見る前に実装してみます (DAGで判定出来るかな？と思っています)
Yuto.icon 思っていたこと(入り次数ゼロの頂点からDFSして，パスの長さがNならOK)実装したけどTLEだった．．．解説見たけど二つ目の方針と全く同じだし，何が遅いのかよくわからん．
wataumi.icon以降見ていない
おたふく.icon上二人を見て、まあ間違いなく知らないアルゴリズムだろうなと思い解説をチラ見。案の定だったのでアルゴリズムを調べ、それを利用して無事AC。
TK.iconこれ以降見ていない。終了後に見てみたが数学っぽいと思い方針を考えてから解説確認したら全然違った。名前だけ知っているあれが使われていたので、いろいろなサイトを行き来してロジックを勉強しました。
〇F問題
CarpDay.iconE問題に詰まって，終了10分前に確認しただけ．解き方分からず解説見る．良いDPの問題でした！