ABC315 （2023/08/19）
〇A問題
CarpDay.icon1文字ずつ，文字列aiueoに入っていないか確認して，解答用の文字列に連結．文字列中のinとか文字列連結とか，PyPyの苦手な方法だけど，サイズ小さいから大丈夫．
まーす.iconCarpDay.iconさんと同じ．
Kaplam.icona,e,i,o,uじゃなかったらprint
tako.iconKaplam.iconさんと同じです
おたふく.icon a, e, i, o, uではなければlistに格納してprint。
kakip.iconaiueo以外が入ったリストを作ってprint
Yuto.icon やるだけ．久しぶりの参加だったので，指が動かなかった．2週間休むともうダメですね...
yuichang.icon体調不良リアタイ参加できず。kaplam.iconさんと同じ
〇B問題
CarpDay.icon1年分の（月，日）を要素とするリストを作って，真ん中を出力．
まーす.icon減点方式．for 文で Diを引いていくイメージ．
Kaplam.icon多分まーす.iconさんに近い
tako.icon上に同じ
おたふく.icon あらかじめ日数の累積和を計算しておき、1年の中間の日がその累積和のどこに入るかなどで答えを求める。しかし、考え漏れやコーナーケースなどでWAが多数。
kakip.icon累積和を計算して、無駄にbisectを使って真ん中を計算
Yuto.icon 問題文を$ (d_1 + \dots + d_m) / 2を出力するのだと誤読していて2WA．なにをしてるんでしょうか．
yuichang.icondを足してって真ん中の値を超えたら調節して出力。>=、>のミスでWA
〇C問題
CarpDay.icon味ごとに美味しさを分けて，要素が2つ以上あれば1位＋2位÷2が候補．各味の1位を集めて，その中の1位＋2位が候補．候補の中のトップを出力．
まーす.iconCarpDay.iconさんと概ね同じ．
Kaplam.icon一番おいしいものの味の種類をsetで管理して、2種類以上あればmax*2、違ったらもう1回見直して一番おいしくなるように...としたらなぜか3WAが出続けて減りも増えもしなかったので書き方変えてAC、すごく時間かかった...
tako.iconCarpDay.iconさんと多分同じです
おたふく.icon 1つ上に同じく。
kakip.iconおいしい順にソートして味が2種類になるまでpop()
Yuto.icon 一瞬DP？と思ったけど，落ち着いて考えたら貪欲でいけそう．いろいろコーナーケースを考え漏らしていて，ここでも2WA．リアルタイム参加じゃなくて良かった...
yuichang.iconCarpDay.iconさんと同じ。multisetをsetにしてたりイテレーターの操作ミスって4ペナ
〇D問題
CarpDay.icon行／列ごとに，色をキー，列番号／行番号を要素とする集合を値とする辞書を作って，仕様通りべたに40分かかって実装．でもやっぱりTLE... もう少し考えます．．よく考えたら行／列ごとに，各色の個数だけ管理すればよいことに気付いて修正したらAC．コンテスト中に気付きたかった．残念．
Kaplam.icon残す行、列をlistに入れて動かす、何列,行消したかによって、例えば最初n=4で2行消したら次はn=2で探索して...ってやってTLE、解説見て納得したけどCで時間かかりすぎて問題よく読んでる暇なかった
tako.iconどう解けばいいのかわからず捨てました。
kakip.icon 行／列ごとに，各色の個数だけ管理してWA,TLE
Yuto.icon Cが終わって，D,Eを読んだら，Eの方が簡単そうだったのでEに行った．結局Dには戻ってきてない
yuichang.iconTLE解法しか思いつかず
〇E問題
CarpDay.icon点1から出る向きの有向枝を辿って到達可能な点が読まなければならない本．あとはトポロジカルソート．．．と思ったのにWA地獄から出られず終了．理由を熟考するも思いつかないので解説読むが，想定通り．他のACプログラム見るが，依然WAの理由が分からず．ふとトポロジカルソートのときにも，点1から未達の点から出る有向枝まで考えていたことに気付き，この有向枝を除外したらAC．考えが足りませんでした．．
まーす.iconD問題に10分程度費やした後こちらを考えてみたが，本１を読むためだけに必要な本以外にも別の本を読む必要があり，そこからの指針が立たなかったので諦めた．(結果論，DとEを放置してGで遊んだ方が面白かったかもしれない)
tako.iconD捨ててEに。読まなきゃいけない方に矢印を作ったグラフを考え、1番目の本から遠い順に出力すればいいと考えましたが5TLE。PyPyならいけるか？と思い提出するも2TLE。。。悔しい
おたふく.icon 最初はdfsの帰りがけで簡単に出来そうと思い実装するもWA。なぜだろうか...。その後、UnionFindで連結性を確認したうえでトポロジカルソートを行ったがWA。
CarpDay.icon帰りがけでできるよ．枝に方向あるから，UnionFindだとあかんのちゃう？（体験済み）
おたふく.icon 他のACプログラムを見たところ、visitedの更新を帰りがけのタイミングでするとACでした。ただ何故かはまだ分からないです。
Yuto.icon 見るからにトポロジカルソート．やるだけやんと思って実装したらWA．あぁ，本の数を最小にしてなかった．必要な本をピックアップ（逆向きグラフ上で1からDFS）してからトポロジカルソートして無事にAC．終了5分前ぎりぎりに通せて気持良い( ˘ω˘ )．まあリハビリにしては上出来じゃないでしょうか．
yuichang.iconトポロジカルソートだと思ったが、よく見るとdfsして帰りがけで見れば良いと気がつく。(サイクルは必ず存在せず、頂点1から見れば良いので）頂点1と連結かを判定しないとダメだと思い、連結性の判定のためにUnionFindを使ってACしたが今思うと必要なかった。(頂点1から1回だけdfsするので)コンテスト後UnionFind使わずにAC。
〇F問題
CarpDay.iconコンテスト中は見ることもできず．翌日問題確認して，すぐに「あれ」だと分かるも，立式に時間がかかる．やっと立式できて実装するもWA．方法は自信あったので，精度の問題かと思ってdecimal使うもWA．諦めて解答見るが，想定通り（今回このパターン多いな）．他ACプログラム見て，原因発見．∞として設定した値が小さすぎました．INF = 1e18としたらAC．ちなみにINF = float('inf')でも計算時間変わりませんでした～
Yuto.icon 問題は読んでませんが，infについて．float(xx)や1e18のようなfloat型よりも1<<64やpow(10,18)などのint型の方が早いということでしょうか
おたくふの参考文献読みました。なるほど、PyPyで64bit以上の数を扱うと遅いんですね。知りませんでした。
〇G問題
まーす.icon条件付きの3元一次不定方程式．プログラム中のコメントにも示した通り，まず，kの上限を決めて２元に持ち込む指針を立てたがWA．TLEは覚悟していたが，どのパターンがWAか不明．TLEケースはCが小さくXが大きいとき，kの上限はさほど減らせない．
CarpDay.iconまーす.iconさんお好みの数学問題なので，F問題とばして取り組む．確かに面白い．Webページで不定方程式の解法復習して実装．約1時間でサンプル通って提出するも，1/3ぐらいWA．解説見たら，やり方同じ．他のACプログラム見て，ループ終了条件設定ミスに気付いてAC． おたふく.icon コードは完成したが、条件設定の際に切り上げと切り捨てを利用しているが、math.ceil,math.floorを使った場合とCarpDay.iconが使用している式で何故結果が変わるのかが分からない。追記 : float型は16桁が有効数字