ABC 341 （2024/02/17）
〇A問題
Yuto.icon ans += "01"[i%2==0]
sakana.icon おたふく.icon forでn*2+1回して偶数番目なら1、奇数番目なら０を出力しました
tako.icon"10" * N + "1"
TTT.icon iが奇数なら1を，iが偶数なら0をans.append()して，print(*ans, sep = '')
まーす.iconYuto.icon さんと概ね同じ．
Kaplam.iconこういう問題いつもおしゃれに書く人すごいなーって思いながらfor回してる
yuichang.iconやる
CarpDay.icon tako.iconさんと同じ．1行で書けて嬉しい．
TK.iconfor文回して10書く。最後に足りない1を書く
〇B問題
Yuto.icon Bなので制約見ずに愚直にやったらTLE．一気に足さないとだめなんですね．
TTT.icon 問題文の理解ができませんでした．飛ばしてCへ．落ち着いて考え直してみます．
sakana.icon１国から順番に両替していってN国まで求めました
tako.icon最初からするだけ
まーす.iconi = 1から順番に"下記の操作"とやらを行うだけでOK．個人的には例が良くないと感じた．
Kaplam.icon小さい所から上げてく、RE出たと思ったらむしろサンプル通ったのが意味わからないぐらい変なことしてた
yuichang.icon 1から回す
おたふく.icon Bなら何も気にせず実装しても大丈夫と思っていた...。
CarpDay.iconみなさんと同じく1から順に行う．何も気にせず実装して大丈夫でしたが．．？
TK.icon前から1回ずつ清算したらサンプルが合わすに焦る。単に複数回清算できるってだけだったので、何回精算できるかを計算してその回数分清算。
〇C問題
Yuto.icon 全探索してシミュレーションするだけ． 適切に枝刈りすれば TLぎりぎりでAC．
TTT.icon じっくり時間をかけて実装しましたがTLEでした．WAもありました．今回時間内に解けたのAだけで反省書くのがつらいです．．．
TTT.icon 探索開始位置が陸であるかの条件式が抜けていたのに気づき訂正して提出するもpythonだからかTLE．でもpythonで全探索してACの方もいらっしゃるのはなぜ...？
TTT.icon Pypyで提出したらACでした．前回はCpythonで提出していました．
tako.icon全探索
sakana.icon端の海を除いて全探索しました
Kaplam.iconちゃんと進めるか辿る、最後のマスが今までにあったマスかはsetに入れて確認
yuichang.icon 全探索。pythonはTLEが厳しいらしい。C++を始めないか？
おたふく.icon え...? 全探索で解ける...???
CarpDay.iconスタート地点を全探索で40ケース中の1ケースだけTLE．スタート地点から上下左右に最大でどれだけ動くか を計算してスタート地点の候補を絞ってAC．スタート地点からの移動量の集合を作る方法の方が王道だろう，とAC取ってから気付く．
tako.iconTLEの提出とほぼ同じので通ってます。何が違うんでしょうか...?
CarpDay.icon 調べたところ，実行速度に一番大きな違いが出たのはSを文字列のままか，リストにしたかの違いでした．この問題，結構絶妙な大きさで，同じコード提出しても，ACになったりTLEになったりします．yuichang.iconさんの言うのが正しい気がしてきました．．
CarpDay.icon sakana.iconさんのコードが速いので調べてみると，UDLRの移動量を辞書で持つより，ベタに4方向場合分けする方が実行時間は短くなるようです．また，checkのような関数を呼ばない方が実行時間は短いです．実装時間短縮が重要か，実行時間短縮が重要か，状況によりますね．
TK.icon全探索した。関数に切り出したりして結構考えを整理しやすいように書いたのにWAが大量に出て一度あきらめてDへ行く。結論としては最後の一マスを移動だけしてチェックしていないというやらかし。
〇D問題
tako.icon割り切れるときの処理がうまくできなかった(そもそもやり方が合ってないと思われる)
Kaplam.icon最小公倍数で規則性が1巡するので最小公倍数までにいくつ出てくるかを計算する、最初1巡分配列に入れたらMLE起こした
yuichang.icon二分探索!!!!
おたふく.icon コンテスト後にAC...涙。最小公倍数までで1巡することを利用して、1周期を全て求めたらいけると思ったがTLE
CarpDay.icon 多分 おたふく.iconさんと同じ方法で実装するが，入力例3がローカルでも終わらず．一方だけの倍数を必要な数だけベタに作ったらAC．この方法でどんなインスタンスでもTLEにならないのか確信持てないままで，ちょっとしっくりいってない．
CarpDay.icon ユーザ解説とほぼ同じだけど，嘘ACだと思われる．数値例3でK = 9999999850にするとむっちゃ時間がかかる（答えは499999994900000001）．ユーザ解説のコードでもAfter Contestインスタンスが追加されたらTLEになりそう．yuichang.iconさんの方法が正攻法．
CarpDay.icon コードテストしたら，時間内に間に合ってた．嘘コードではなかったけど，二分探索が正解だろうね．
Yuto.icon コンテスト後，解説AC．包除原理+にぶたん か...にぶたんはコンテスト中に考えたんだけどなぁ...
TK.icon倍数の個数の考え方が使えそうと思い、いろいろ考える。制約が大きいから2分探を使って、バカでかい数字が条件決まるか調べる。数字を決めてしまえば、個数は求められるというのに気付けたのが良かった。しかし、またもサンプルが通らないので、試しに条件を逆にしてみたら通った。まだちゃんと使いこなせていない。
〇E問題
Yuto.icon (左端の01，右端の01, 区間内が良い文字列か) のタプルを要素に持つ二分木で，区間XOR，区間取得の遅延セグ木かな？と思ったけど，op, mapping, compositionを上手く設計出来なかった．そもそも遅延セグ木にXORが乗るのかよく分からん．
おたふく.icon 単位元が存在する演算なら載せられるっぽい。xorなら単位元は0かな。
tako.icon結合則が成り立つ必要もあるみたいです
Yuto.icon 公式解説見たら，普通のセグ木で解けるらしい．直前に遅延セグ木の話を聞いていたせいで思考停止してたかも．
Yuto.icon コンテスト後，atcoder.segtree.SegTree使って解説AC．．．したけどあんまりしっくり来ていない．0-indexed, 1-indexedが関数によって違う？のがキモい．doc string 付いてないから調べに行くのも面倒だし，ライブラリ整備するべきかなぁ
CarpDay.icon 0-indexだと思うけど，1-indexの関数があるの？
tako.icon遅延セグ木。実はABC322-Fを少し変えるだけで通る。それの解説コードを変えて通したので実力ではない。
tako.iconコンテスト後自力AC。pythonでは遅延セグ木に載せるデータはクラスとかタプルとか使うと遅くなる(?)ので使わないやり方をやるべきということが分かった。遅延セグ木結構わかってきた気がする。
CarpDay.iconコード見せてもらいました．コンテスト中にTLEだったやり方と同じだけど，データを1次元にする方法，見事ですね．勉強になりました．
Kaplam.iconセグ木を使う所までは合ってたけどここ以降の数字はここまで10101...を保ってるって考え方したら上手く作れなかった、急にセグ木の問題増えた気がする
yuichang.icon クエリ2が無理じゃね？
おたふく.icon クエリ2がtako.iconが言っているように、いつぞやのコンテストと一緒なことに気付くも探す余裕がなくD問題の沼へ。
CarpDay.icon遅延セグ木で実装するもTLE．綺麗な演算と単位元が設定できず時間切れ．悔しい．
CarpDay.icon遅延セグ木に載せる方法，色々考えるもどれもTLE．諦めてtako.iconのコード見たら，C++？？Pythonだと定数倍が重い遅延セグ木は無理な気がする．（追記）他の人のACコードから遅延セグ木での実装を発見！よりシンプルなコードにして遅延セグ木でAC取れた！！データを1から始まる良い文字列(1010...)との差異の個数と区間長にする点がポイント．よく思いつくなぁ．
CarpDay.icon「セグ木でできる」という上の情報を見て，改めてじっくり考えてみたら確かにセグ木でできるやん！ac-liblary-pythonのSegTree使ってAC．更に別解解説のSortedSetを使う方法でも実装してAC．Yuto.iconさんの言う通り「直前に遅延セグ木の話を聞いていたせいで思考停止」が今回の敗因でした．
TK.icon以降見てない。
〇F問題
yuichang.iconWでpriority_queueのせたダイクストラじゃダメ？
CarpDay.icon最大操作回数求める問題なので，その方法で実現するのは難しくない？どちらかといえば，距離よりも流量（配る個数）を考えるような問題だし．
CarpDay.iconコンテスト翌日にやっと問題確認．やり方思いついて，以前教えてもらったGraph×Graph使って，入力例3でハンドシミュレーション＆Excelで積和求めたら合っていたので実装してAC．好きな「あれ」の問題で楽しかった．
〇G問題
CarpDay.iconシンプルな問題だけど手も足も出ず．解説見て計算幾何の問題とみなす見事な方法に感服．凸包を求めるアルゴリズムはICPCでも（AHCでも？）使えるかもしれないから，ライブラリ持っておいても損はないかも．