ABC294 (2023/03/19)
〇A問題
Yuto.icon パソコンの前でたそがれてたら21:00:30くらいで，めちゃくちゃ焦った．言われたことをやるだけ問題だったので，落ち着いて実装し，AC．
おたふく.icon 偶数の時だけlistに追加。
TK.icon偶数なら答えのリストに追加。最後にprint
CarpDay.icon内包表記の練習
TTT.icon 2で割った余りが0ならスペース入れて出力、としました。
wataumi.icon同上
まーす.icon自分は19:00開始と勘違いしていて、18:50位から待機していた。泣
解法はおたふく.iconさんと同じ
〇B問題
Yuto.icon string.ascii_uppercase[A[y][x]]
おたふく.icon 久々にascii.uppercaseにお世話になりました。ascii.uppercaseの文字列の先頭に' . 'を追加。
TK.iconoad("A")-1を持っておき、来た数字が０以外ならその数字をプラスしてchrで文字に変換。大文字を羅列するやつどこにメモしたっけと探そうとしたが、その前に思いついたので書いた。あと答えを空白区切りにしてWA...
CarpDay.iconord()とchr()を駆使．そういえば，ascii_uppercaseありましたね...すぐ忘れてしまう...
TTT.icon chr(65)='A'を利用して、chr(64+A( j )( i )))としてアルファベットに変換しました。
wataumi.icon同上
まーす.iconC(言語)でやったようにアルファベットをずらしていくやつをしようと思ったが、なかなか思い出せなかったので一つ一つif文で場合分けをした。(しょーみ最初からこの書き方でよかった。)
〇C問題
Yuto.icon Cを作ってソートして，二分探索するだけ．簡単すぎて不安になりながらも提出すると無事AC．良かった．．
おたふく.icon 最初に問題を見たときに、AとBを繋げたCの長さが10^10になってしまうと勘違い。計算時間の短縮の仕方を思いつくことも無く、D問題へ行く。D問題でTLEが出たの返ってきてみて、計算時間を再度確認すると2*10^5になることに気付く。AとBを繋げたリストCをソートし、ans_Aとans_Bを用意。AとBをsetにキャストしてからCを順にforで回して、AとBに含まれるか確認し、含まれる方のansに追加する。
wataumi.iconほぼ上に同じ、実行時間はこちらがやや早い(AとBが狭義単調増加列だから？)
TK.icon冷静に見ると2*10^5だからCを作ってソートしても良かったかも。dequeを使って二つのキューを用意しソートしたA,Bを入れて、取り出したものを比較してループの番号を割り当てる。片方のキューの中身がなくなったときの処理に苦戦
CarpDay.icon AとBの各データに対して（データ，A or B，A or Bでのindex）というリストを対応させて，リストCを作る．Cをソートして，AとBの各データがCにおける何番目になるかを求め，AとBの元のデータを上書きして出力．
TTT.icon C( 0 )から探索してA( 0 )が見つかったら探索位置はそのままで次A( 1 )を探す、という風にして探索量を削りました。
まーす.iconAとBの集合(set())とCの配列を作り、Cをsort。そこから、forをでCの要素でまわし、ifでA or Bに場合分けをした(説明ムズイ)。
〇D問題
Yuto.icon 動的な最小値→heapq．．．なんだけど，heapqモジュールでは指定した値の削除が出来ない(event:2)．なんか良いデータ構造ないかなーと彷徨っていたら，CarpDay.iconが作ってくださったLazyHeapなるものがScrapBoxにあるじゃないですか！ありがたく使わせていただき，無事にAC．Dを通した時点で学内1位だったので，今すぐコンテスト終わってくれないかなーと思ってた．
TK.iconキューを使っていろいろ試してみたが、サンプルのみうまくいった程度。TLEとREが出ていたので、使い方に関する理解の甘さが出たか、方針が違うのか。変数とか管理するデータが多くなってしまったので、自分の中でも整理しきれていなかった
CarpDay.icon呼ばれたけど受付していない人の集合は，最小値の抽出と値の削除が必要なので，heapqでは対応できない．愚直に別のデータを用意して，削除した情報を保持する方針で対応．ケアレスミスで1WA．今回は何とか原因を見つけてAC．やれやれ．LazyHeap？なにそれ？
おたふく.icon 最小値なのでheapqなどを考えましたがどうしようもないと思い、一旦呼び出しを受けた人の集合をsetで保持。TLEが出ると思いつつも単純にmin(set)で実装するも案の定2件のTLE。よく考えてみると呼び出しを受けた人の集合を呼び出された人の番号をキー値としてdictで保持しておくとキー値は必ず昇順になるし、呼び出された人を集合から削除するのもO(1)で行えることに気付く。したがって、最小値はキー値の先頭を取り出すだけで良いのでTLEを解消、無事AC。順位を確認するとZuka君とCarpDay.iconを除くと2位だったので、これは外れくじでは...?
TTT.icon クエリに従ってキュー(FIFO)を操作し、クエリが3の時に最小値を出力すればいいのではと思い実装していましたが、上記の方の反省を見る限り、そんなに単純ではなさそうだと思いました。実装途中でコンテスト終了です。以降の問題は覗いていません。
wataumi.icon21:36 deque()使用、tle6。21:44 set()使用、tle2。紆余曲折、閑話休題。22:10 heapqだろうな……分かんね☆（勉強不足により実装できず）
〇E問題
Yuto.icon 愚直にやるだけなら簡単だけど，$ L \leq 10^{12}なのでランレングス圧縮したまま上手いことやらないとだめ． 区間クエリだからセグメント木とか使いたくなるけど，これもLがデカすぎるので使えない．暫く考えていたら，ふと，これ前から順に見ていくだけでは？と思い実装してみたら結構ややこしい．方針は合ってそうなんだけど，実装しきれずにコンテストが終わってしまった．．．実装力が欲しいです
TK.icon数学系の問題を求めてこれ以降の問題（E,F,G,Ex）を見たが、以降の問題がグラフとかクエリっぽい入力例だったので詳しくは読まず、数学系なしと判断してDへ戻った
CarpDay.icon Lが大きいので1文字ずつ確認できないので，圧縮したまま対応（ランレングス圧縮っていうんだぁ）．サンプル1に基づいて実装．サンプル3でWAで考慮漏れに気付き，無事AC．サンプルに救われました．
おたふく.icon 制限時間内に考えていた方針で実装を続けると無事AC。2つの文字列の添え字を上手く調整することでランレングス圧縮されたままの状態でも実装可能。問題を解く速度を速めていきたい。
wataumi.icon以降未読
〇F問題
Yuto.icon Kが小さかったら上位K個だけを保持して上手いこと出来そうだけど， Kが絶妙に大きいので，無理そう？Eに戻った．
CarpDay.icon濃い順に調べたらいいんじゃね？と思ったら，Kがむっちゃ大きい．．．orz