ABC340 （2024/02/10）
〇A問題
tako.iconやるだけ
Yuto.icon やるだけ．*range(a, b+1, d)．久しぶりにPythonで参加
CarpDay.icon Aにしては難しいかな？whileで実装．
yuichang.iconやる
Kaplam.iconやった
TTT.icon 同上です．
まーす.iconおたふく.icon Yuto.iconさんと同じ．
TK.iconwhileで作る
〇B問題
tako.iconこれだけ？
Yuto.icon やるだけ
CarpDay.icon クエリの練習問題．Pythonはindexの負数使えるので，後からk番目も簡単でいいですね．
yuichang.iconやる
Kaplam.iconやった
TTT.iconまーす.iconおたふく.icon 同上です．
TK.icondefaultdict使おうとして結局簡単なことに気付いて使わず実装。
〇C問題
Yuto.icon サンプル通るのにWA．わかんないです．メモ化再帰やるだけじゃないんですか？割り算誤差が気になったのでDecimal使ったりしたけど変わらない．
Yuto.icon コンテスト後AC．やっぱり割り算誤差が原因だった．Decimalを使うのは良かったんだけど，Decimalオブジェクトを割り算してmath.floor, ceilに通すとintに戻ってしまう．型ヒントでDecimalって書いてたけど，実際はintが渡されていたみたい．これでエラーが出ずに動いてしまうの，Pythonはクソだな...．Rustならコンパイル時に気付けてた．
tako.iconメモ化再帰久しぶりに使った気がする
CarpDay.icon 2WA．functoolsのキャッシュ使ったらWAだったので辞書にしたけどWA．さっぱり理由が分からず諦めかけたけど，ふと気になった int(x / 2)をx // 2に変更したらAC．うーん．
yuichang.icon メモ化してdfs
Kaplam.iconLRU_cache、合ってるはずなのに3WA出ると思ったらif x / y == x // yみたいな感じでやるとダメらしい
TTT.icon 2以上の数をqueueにappendして，popleftするのを繰り返してqueueの長さが0になるまでやってWAではありませんでしたがTLEでした．メモ化再帰はこの前勉強したのでそれで後日解いてみます．
まーす.icon私はheapを使用．setとdefaultdictでxの重複分をなるべく減らす．
おたふく.icon 数の大きい順にクエリを行う。また、それぞれの数の個数を管理して、重複したクエリをまとめて処理する。
TK.iconキャッシュ使おうとしてローカルの時点でダメそうだったからいろいろ考えた。結局分割しても、１が出るまではもとの数が足され続けるから、(1が出るまでの分割回数×N)＋(１が出てからの処理)で実装したがサンプルすら合わなくなって沼に入る。1が出た場合、加算する値をN*{（分割後に1以外になった数（重複有り））/（分割する前の数の和（重複削っている））}で更新した。
〇D問題
Yuto.icon サンプル通るのにWAその２．わかんないです．DPじゃないんですか？
Yuto.icon コンテスト後，ダイクストラしたら2TLE．？？？？？
Yuto.icon 解決．コストを確定させる部分で，<が<=になってたのが原因ぽい．
tako.iconダイクストラです
Yuto.icon _(:3 」∠)_
CarpDay.icon tako.iconさんと同じ．自作ライブラリの使い方が分かりにくく時間ロス．整備大切．
yuichang.icon爆速で自作ライブラリを貼る
kakip.icon辺の情報をlist[dict]にしていてWA
Kaplam.iconC++でDP書いてTLE出たのでダイクストラしたら初のMLE,ダイクストラで合ってるらしいし昔作ったやつだからやり方よくなかったっぽい 追記 小さい順にやってない似非ダイクストラになってた 再追記 問題そこじゃなくてn^2のlist作ってる所だった
TTT.icon DPだと思い実装するも答えがうまく出力されずコンテストが終了しました．ダイクストラ実装してみたいので後日解いてみます．
おたふく.icon tako.icon同様ダイクストラ。最初dpで考えてしまい時間ロス。
TK.iconｃで沼って少し見るが、ｄｐっぽいと思い考えるも、2次元で考えており、計算量的に無理だと思いＣに戻る。
〇E問題
tako.icon区間更新といえば
CarpDay.icon 区間更新の方，汎用的な自作ライブラリ作ろう，と思いつつ後回しにして今に至る．おたふく.iconさんの使おうかとも思ったけど，F問題が解けそう，と思って戻ることができず終了．
CarpDay.icon 解説見たら遅延でないセグ木でも解けるとのことで試しに実装．実行時間は短くなるが，考え方がややこしくなるので，実装時間がかかりそう．コンテスト中は素直な実装方法が一番だね．
yuichang.icon初めて使ったけどバグが
おたふく.icon 解法が分かったのに実装が間に合わず、コンテスト終了後AC。
〇F問題
Yuto.icon タコがつよすぎます
tako.icon＼(≧▽≦)／
Yuto.icon 青ぱふぉおめでとう！！！！！！！！！！
tako.iconほんとだやば笑
CarpDay.icon すごい！！500位台すごすぎ！！
tako.icon言い換えると一次不定方程式。ネットに転がってたライブラリをペタ。初の6完でうれしいな
CarpDay.icon 一次不定方程式解くために，MODの逆元を拡張ユークリッド互除法を使うがWA．中途半端な理解で他人のライブラリ使ったらあかんな．．
CarpDay.icon 一次不定方程式解くライブラリ作りました～ 一次不定方程式 おたふく.icon CarpDay.iconさんが作成してくれた一時不定方程式のライブラリを使用してAC。