ABC330 （2023/11/25）
https://atcoder.jp/contests/abc330/tasks
CarpDay.icon とうとう「さな」にトップを取られる．．．
Yuto.icon 次のコンテストでは私も変数名をnatori, sanaにしてみましょうかね...
〇A問題
Yuto.icon やるだけ
TTT.icon L <= A[i]の個数を数えます．
まーす.iconTTT.icon さんと同じ．
tako.icon javaでやってみました。やるだけ
CarpDay.icon 内包表記派
おたふく.icon すっきり書く方法がありそうだが、問題を見てすぐに思い付かなかったので素直にコーディング。
TK.iconL以上の個数数えた
〇B問題
Yuto.icon 場合分けするだけ，なのに1WA．．．L <= a <= Rの場合を見逃してた．
TTT.icon Yuto.iconさんと同じ見逃しをしていました．私は2WAです．
まーす.iconA[i]<=L，L<A[i]<=R，R<A[i]で場合分け．難しそうにみえて簡単なやつ．Cにとばさなくて良かった．
tako.icon javaのintってどこまで入るのかなっていうことに気を取られすぎて適当に回してTLE。馬鹿だね
CarpDay.icon 問題文理解に時間がかかる．早く理解できる読解力欲しい．
おたふく.icon 同じく問題文を見てからつまり何を求めればいいのかすぐに理解できず...。場合分けを丁寧に。
TK.icon1行でなく1列に出力していた。条件分岐も見やすくしようと不等号の向きを変えて変数を入れ換え忘れててWA１。修正してAC
〇C問題
Yuto.icon 定式化して，pulpで実装して，解けた！！と思って実行してみたらRE．そういえば，制約が二次になってました．LPじゃないのでpulp使えないですね...
Yuto.icon 解説見た．x固定してyを探すというのは考えたけど，そこから先が無理だった．惜しい．
Yuto.icon 原案者の解説の「半径Dの円の円周に最も近い格子点」こんなの気付けるようになりたい．
まーす.iconむずい．簡単そうにみえてむずいやつ．実行時間がなぁ......．
まーす.icon追記，とある授業で二分探索法による解法を思いつく．具体的には，半径 D^0.5 の円周を挟むようにとった2点をbisectで探索していった．この問題は良問！！
tako.icon javaでやってたらいろいろぐちゃぐちゃになってわけわかんなくなったのでpythonに帰ってきました。そっからループの範囲とかいろいろいじってACするまでに3ペナ。時間かかりすぎ
CarpDay.icon 数学系なので絶対に跳ばさないと決意しつつ挑む．落ち着いて対処してAC（の前にケアレスミスでWA．この1ペナが原因でkakip.iconに負け．．）
おたふく.icon 複数個の変数があるときの基本解法。
CarpDay.icon 合宿で作ってくれた「Candle」と似てない？
おたふく.icon 「Candle」で内部の格子点を数えるにあたってx座標を固定して、そのx座標での円周上の点よりy座標が小さい最大のy座標を持つ格子点を調べる部分が、今回の問題に通じる部分がありますね！ それと合宿で僕が想定していたC相当の難易度というのも共通していますね。
TK.iconあらかじめDを超えない平方数を計算しておく。bisectでD-x^2の値が入る位置を計算して、その前後の値を用いてabs(D-(x^2+y^2))を計算して、最小値を取る。最初、前後でなく片方だけを計算していてWA１。
〇D問題
Yuto.icon 実装ゲーっぽかったので一旦飛ばした
まーす.icon個人的にCよりも簡単．dictでその列，行にある o の位置を記憶して，{(i列のoの数)-1}×{(j列のoの数)-1}，但し，i, jはoの位置をさす を数え上げていくだけ．
CarpDay.icon まーす.iconと同じ．楽しい．
おたふく.icon 上2名と同様。これだけで大丈夫なのか？と思いつつ提出。
TK.icon上に同じ
〇E問題
Yuto.icon mexでググって，良さげな記事 が出てきたので，やってみる．SortedListを使って実装してたらコンテスト終了．解説見ずに解きたい．
Yuto.icon 一生サンプルが通せず，解説をチラ見．nok0さんの解説 と同じことをしようとしてた．方針はあってたけど，この方針は実装が面倒．
Yuto.icon Aに含まれる数を区間で管理する方法 は実装が面倒すぎる． 結局，Aに含まれない数を管理する方法 でAC．
CarpDay.icon 素直に実装するがやっぱりTLE．SortedSetで実装してTLE解消するがWA．反例見つけてシンプルに作り直したらAC．WAの原因わからないときは，考え改めて作り直すのが良いね．
おたふく.icon grundy数関連の問題を何回か解いて勉強していたので、mexの持つ性質などをしっかり抑えられていれば解けた問題だっただけに悔しいです。
TK.icon終了時間的に解ききれなかった。
〇F問題
CarpDay.icon E問題のWA取れず，チラッと覗く．SortedSet使えば，こちらの方が簡単そう？コンテスト翌日，何時間もかけて実装する．WAは取れてもTLE地獄．3日寝かせたら解法思いついてやっとAC．解説見たら，別解に近かった．
#AtCoder #ABC