ABC300 (2023/04/29)
〇A問題
Yuto.icon C.index(a+b)
sakana.iconfor文で探した
TK.iconTTT.iconCarpDay.icon 上に同じくforで書きました。
まーす.icon同上
おたふく.icon Yuto.icon同様
tako.iconYuto.iconさんと同じです。
yuichang.icon同上
〇B問題
Yuto.icon row_shiftとcol_shiftを愚直に実装する．
sakana.icon愚直に全ての行が一致するまで列を移動させてから、行も移動させて合わせた。popとappendでなんとか実装。
TK.iconグリッド系の問題苦手すぎてシャレにならない。多分方針が違う。列が一致する形になるか、行が一致する形になるか回して確認したつもりだが、自分の実装では何かが足りない。
おたふく.icon sの操作とtの操作の全組み合わせをひたすら行う。最初はAとBの対応している#を探して各#の偏差が1になっていれば、などの条件を考えるのかと難しく考え、時間を使ってしまい一旦冷静になるために先にC問題へ
TTT.icon B問題は#の行,列の位置を高さ,幅で割った余りで扱おうとしたりしていました。先週に引き続きAしか解けなくて悲しいです...
CarpDay.icon当初，一行or1列だけのシフトも可能だと勘違いして悩む．問題理解したあと，Aを縦・横ともに2個分，合計4個分並べたAAを作ってBと比較．この方法だとMOD使う必要ないのに，なぜかMOD使う方法にするという迷走もしつつ，27分かかってやっとAC．コンテスト終了後に改めて見ると，入力例4すごいね．ABC→300!になってるよ！
tako.icon素直に全探索すればよかったのに難しく考えて5回もミスしてしまいました。
まーす.iconAの添え字だけを動かしてBと一致するかを確認。4重forは怖い......。
yuichang.icon愚直に実装、つらい
〇C問題
Yuto.icon ICPCを彷彿とさせる見た目で，第一印象はめんどくさそう．iPadでお絵描きしてしばらくにらめっこしてたら閃いた．バツ印の左上頂点を探して，対角線に見ていけば行けるんじゃね？→半信半疑で実装して投げると無事にAC．良かった．
Yuto.icon 解説のUnionFind使った別解かっこいい．連結成分とみなす発想出てくるようになりたい．
TK.iconBが解けずCに行って5秒足りずに時間切れ、終了後4秒でAC。泣きたい；；
sakana.icon＃にフラグを設けて対になりそうな＃を見つけたら、そのサイズにあった×ができているか…と調べようとしたが添え字がややこしくなり間に合わなかった。
おたふく.icon 2重ループを回した場合、必ず最初に見つかるx候補になる#はxの左上になることに注目してそこからxの中心になる#を見つける。その後なんやかんやして発見したxの要素となっている#を全て削除してから、元の探索に戻る。
CarpDay.icon×の左上探して，見つけたら.に置き換えました．おたふく.iconと同じかな？
tako.iconxの中心を探してからどれだけ大きいかを数えました。
まーす.icontako.iconさんと同じ
〇D問題
Yuto.icon まず，エラトステネスで必要な分だけ素数を列挙する．a=2, b=3でN=10^12の時，cが最大で10^6くらいになるので，それくらい．あとはa, b, c, をどうするかだけど，列挙した素数の個数をMとすると，N=10^12の時にM=10^4なので，O(M^2)くらいならギリギリいけそう？なので，a, bを全通り試して，cを高速に求めたらいけそう．cがokかngか，は単調性があるので二分探索する．先週の勉強会で布教しためぐる式二分探索を実装し，解けた！！と思って提出すると半分以上TLE．まじか．．と思ってコードを眺めていたらbreakするべき場所でcontinueしてた．修正して無事にAC．95分で滑り込みAC気持ちいい :)
まーす.icon調整ゲー。素数判定で300000までの素数をリスト化し、N>=i^2*j*k^2の数をカウント。でも、これだけでは絶対にTLEになるので、もう一工夫必要。forで回す回数をできるだけ少なくしたいので、ifで自明なアウトなやつを排除(break)。Cが個人的に難しく感じたのでDに逃げた。
TK.icon一見簡単そうだが、BＣ解けてない状態でやるもんじゃないと思い後回し。5つかけるからＮの5乗根までの素数で行けんじゃねと思ったが、サンプル1でもうすでに違うからやめた。
おたふく.icon 10分程時間が余ったので、D問題へ。なんとなくの方針は立てられたので、後でもう一度考え直す。エラトステネスの篩で素数リストを生成。しょうもないミスでcの上限を求め間違い、予め用意しておく素数リストのサイズを間違えたためにWA。
CarpDay.icon手作業＋Excelでa, b, cそれぞれの上限を求めるものの方針立たずに一旦E問題へ．E問題諦めて，とりあえずcの上限までの素数リスト作成したら結構少なくてびっくり！あとはYuto.iconと同じく，a，ｂ固定して，cの個数は二分探索で求める．
yuichang.iconエラトステネスで素数列挙して探索。オーバーフローに気が付かなかった、C++は9e18?以上の数を扱いにくい
〇E問題
Yuto.icon 問題文読んでたらコンテスト終わった．これ以降見てない
CarpDay.icon入力例1ぐらい手計算で解ける，と思って計算したけど合わなかった...時間の無駄遣い．
おたふく.icon メモ化再帰を用いたdpを初めて知った。やっぱりdpを考えるのは楽しい。
〇F問題
まーす.iconチラ見後解けそうやなと思ったが、よく考えると難しいパターンのやつだった。連結はムズい。
おたふく.icon 二分探索の範囲を勘違いしていたため苦戦。どういう時に二分探索を行うと効力を発揮するのかが難しい。
〇G問題
まーす.iconDと同時進行で考えてた。Pまでの素数リストを作ってどうたらこうたらする感じかな......。いまいちこの後の指針が立たない。
CarpDay.icon熟考して方針立てるも，TLE逃れそうもなく解説を見る．半分列挙すごい！シンプルに解けました．
おたふく.icon 半分全列挙はICPCでも活かせそうな解法なのでマスターしておきたい。そしてここでも二分探索...。