TTPC2019参加記

コンテスト

東京工業大学プログラミングコンテスト2019 - AtCoder
チームolphe_konaiphe(oshibori，tsutaj，ferin)で参加しました．

B問題

部分文字列okyoのあとに部分文字列echが存在するかを判定すればいいことがわかったので書いてAC

A問題

oshiboriさんが解いてた．

D問題

tsutajさんに素数=素数+素数となる場合，片方の素数は必ず2と教えてもらった．あとはgrundy数を愚直に計算するだけなので書いて出した．

C問題

tsutajさんに方針の確認だけされたのでokだと思うと答えたら通ってた．

E問題

「同じ行/列の要素をswapしても行/列の和には影響しないのでswapをしてうまいこと和をずらすみたいなことを考えると奇数の場合は構成できる．偶数の場合 と が を法として合同になることはないので必ずNoになる．」みたいな考察をtsutajさんとしたので書いてもらうと通る．

F問題

DAGしか与えられないことを教えてもらう．始点と終点が1つずつならDPするだけ．2つあって合流したり分岐したりするのが複雑そうなのでDPっぽい．頂点から連結から連結と両方から連結 連結するのに必要な最小コスト とするDPができそう．これだけだと分岐した後を表現できないが，分岐したあとなら独立に解けるので終点からの最短距離を求めておけばいいとtsutajさんに教えてもらう．合流せずにwからx，yからzにそれぞれ独立に向かうパターンを忘れていてWAを生やすがなんとかAC．

G問題

Kが大きい場合はどうせ になるとか，気合で詰めれば解けそうな見た目をしているとかtsutajさんと話す．

H問題

oshiboriさんに平衡二分探索木があれば解けると言われ，さすがにそんなライブラリ使わないのでは？と思ったけど他の方法が全く思い浮かばない．実装がやばそうなのでとりあえず放置．

O問題

なので3マスで2倍を表現して2べきを頑張るみたいないつものだろと思い，考えたが思いつかないので放置．

H問題

実装に入れる問題がHしかない．仕方がないのでRBSTを貼って頑張ることにする．
クエリを前から見ていく．そもそも連結な集合を結ぶ場合答えは変化しないのでどうでもいい．新たに連結した集合以外の頂点の部分が変化することはないので，新たに連結した集合に関してのみ解ければよい．頂点の連結性についてはUnionFind等を使えば管理できる．
pが大きい方から並べる順序付き集合とxの和を各連結成分に持たせる．pが大きい方から貪欲に割り当てて行けばよいので，集合のprefixのxやpxの和が取得できれば連結成分ごとに答えを求めることは可能．集合のマージはマージテクで高速にできる．
気合で実装をするとサンプルが合ったので通る気しない～～～と言いながら投げたら通った✌🏻．

G問題

i文字目と対称の位置にある文字が同じ/違うものが何個あるかと文字列の中心が存在するか(=奇数長か)で3グループに分ける．各グループに操作する回数を何回割り振るか？で元の文字列が何通りあり得るかが変わってくる．それぞれのグループで何通りあるか計算した後，畳み込みを計算すれば答えが求められそう．という話をtsutajさんから聞く．任意MODのNTTが想定解ではないだろうなあと話し合いつつも考察は合っていると思うので書いてもらう．

M問題

Gの実装をチームメンバーの二人に任せて，割と解かれていたMをやることにする．まず木の根を一つに固定した場合はdfsすれば解けることがわかる．各頂点を根にした場合を求めたいので明らかに全方位木DPっぽさがある．全方位木DPで親側の情報として渡すものは，(親側の部分木の転倒数)+(新たに根になる頂点より小さい頂点の数)となる．これを求めるには各頂点を根とした部分木で転倒数と自分より小さい頂点が何個あるか？をそれぞれ計算できればよい．順序付き集合をマージしていきながらdfsを1回すればこの値は計算できるので，全方位木DPで解ける．Gと交代しながら実装するとサンプルが合ったので投げると通る．

G問題

Nが偶数のとき1ケース，奇数のとき数ケースが通らないということで考えるが間違っている場所がわからない．色々試して調整するものの合わずコンテスト終了．

後半集中が切れててGのK=0のコーナーを指摘できなかったのとO問題にもうちょっと時間を割けばよかったかな～というのが反省点．

懇親会では寿司とピザがフューチャーさんから提供された(ありがとうございます🙏)ので食べながらお話したりした．翌日にはリアル脱出ゲームに行ったりボドゲをやったり夕飯を食べたりした．周りの謎解きスキルが高くて脱出のプロだった．