ABC315 (キーエンスプログラミングコンテスト2023夏)
5完60分+4WA 931st performance:1531
1ヶ月で100近く落としてるんだが俺なにかやっちゃいました？（何もしてないのでは）
atcoder.jp
A 正規表現使えば早いと思いつつ正規表現がぱっと書けないのでset
atcoder.jp
B 中間の日数を求めず条件式をぐだぐだ書いてしまった。奇数だしさっさと求めたほうがよい (21:06)
atcoder.jp
C なぜか味が異なるときのおいしさを(s0+s1)/2にして1WA、テストケースで落ちないのが悪い (21:17)
atcoder.jp
C++20だしrangeを使ってみたい
atcoder.jp
D set
atcoder.jp
構造体を作って、色々関数作って、行・列の消去判定をO(1)でやるやつ
atcoder.jp
E 見るからにトポロジカルソートなのでコピペって帳尻を合わせる。無思考でdsuで塊を管理して、1を含むやつだけ出力。1の先を出力してしまい1WA。よくよくトポロジカルソートのコードを見れば、塊ごとにDFSしてるだけなので1からDFSするだけでよい。(21:59)
atcoder.jp
1からDFSするだけのやつ
atcoder.jp
F DPっぽいなと思ったんだけどパスできる頂点の個数をO(N)と見積もってしまいやめに。ダイクストラ法っぽいやり方でいけるやろうと挑戦したが時間が足らず10:39提出TLE。(チェックポイント,無視数)を頂点とするグラフでダイクストラするのだが、単純にやると枝数が多くなりすぎてTLEする。最初に全チェックポイントを巡るルート長を求めておく。各頂点からは、いまいるチェックポイントの先のチェックポイントをそれぞれ、コストを求めていく。そのコストが最大コストを超えた場合はそれ以上先のチェックポイントにいかないようにすればよい（なんかぎりぎりすり抜ける例とかできそうだけど、今のテストケースはこれで通るぜ！）。C++20で900msぐらいで通る。訪れた頂点の管理を（無視数の見積もりをせずに）setで管理しているが、適当な大きさのvectorにするともう少し速くなる。
vectorで管理
atcoder.jp
ABC313 (第四回日本最強プログラマー学生選手権-予選-)
19分3完+1WA 1713th performance:1272
パフォがどろどろ溶けて死んでいる
A 2人目以降の最大値を取得し比較するだけ (21:01)
atcoder.jp
B グラフ探索っぽさがあるが、「誰かより弱い」という情報がない人間はすべて最強の可能性があるので、M個の情報から弱い人間を最強候補から外すだけでよい。 (21:04)
atcoder.jp
C multisetとかで貪欲にやるのかと最初考えたが、総和が変わらないことに注目すると、最終状態は「MがN-X個、M+1がX個」の状態になり、Mは平均（切り捨て）、Xは総和をNで割った余りである。とりあえず全部Mにする操作回数を求めて、Xだけ引いたが、WA。M以上の値であればM+1にするのは操作回数が1減るが、そうでなければ1増えるのでM以上の値の個数を求めて厳密に求める必要がある。(21:14->21:19)
atcoder.jp
D N+1回聞けるならいけるな～と思いながらあれこれして実装もグチャグチャになって時間だけが過ぎる。そこからEにいって時間が足りない、とかいう戦略ミス。
2つの質問で、1つの位置以外共通であるとき、その2つを比較することで異なる位置の数字が一致するかが分かる。K個質問することで、前K個の一致関係が分かる。このK個の和を質問することで、K個の値が確定する（1番目を0としてK個決めておき、その総和と答えが異なる場合、すべて反転させればよい）。残りについては、確定している数字K-1個と未知のものを聞いていくことで確定できる。
atcoder.jp
E 1以外の数字が連続するとき、操作は無限回になる。後ろから見て、i文字目について「その前の数字が1個になる」までの操作回数をDPする。i文字目が1の場合は+1するだけ。1以外の場合、「1をK個」挿入する操作が「それまでの操作回数+1」回行われる。1はK-1個ずつ増えるので、(K-1)(DP+1)個1が増え、Kが消えるのも含め(K-1)(DP+1)+1回操作を必要とする。
atcoder.jp
ABC312 (ユニークビジョンプログラミングコンテスト2023 夏)
31分+2WA 4完 1504th performance:1338
4月以来の低パフォ叩き出しで1800が遠のく。悲しみ。
A 「ACE、BDF、CEG、DFA、EGB、FAC、GBD」をメモ帳にコピペします。「、」を「","」に置換します。エディタに貼り付けます。 (21:01)
atcoder.jp
B B〜Cっぽい実装が重い問題。こういうのは正規表現で殴るんだよぉ！と久々に正規表現を使おうとすると混乱する。始まりと終わりのパタンしか書いてないのに9文字に対しregex_matchして合わないなあとかやってた。regex_searchを使いましょう。エスケープ文字がややこしいのでraw string literalを使いましょう。MとするところにNを入れて1WA。サンプルで弾いてくれえ (21:14->21:14)
atcoder.jp
C 何も考えずにソートして答えを二分探索して、中でも二分探索で数えてやればOK。答えの二分探索を見るために、OKの初期値を小さな値にしたまま提出しWA。落ち着きましょう。(21:22->21:23)
atcoder.jp
全部合わせてソートして順番に見ていくやつ。売る側を先になるようにソートしましょう。
atcoder.jp
D シンプルDP。最初開き数マイナスも含めて計算したら合わなくてちょっと混乱。開き数がマイナスになった時点で破綻していることに気づき書き直し。(21:31)
atcoder.jp
E 言われてみれば簡単なんだけど、各面で考えようとして二次元imosか？いやvector<vector<vector<map<ぐわあ、、、諦め。順位表見て低さに死につつもFが解けそうな感じを出しているので挑戦
F 鍵を何個使うかを全探索して残りを二分探索や！……いやこれ最大を求めるタイプの二分探索？三分探索になるんだっけ？1個でも交換した場合に下がるとかいう条件でなんとかならんか……死ぬほどエラーが出る……Eもむずいしつらい……解けん……死……
終了後も貪欲戦略を優先度付きキューとかでなんとかやろうとしたがこちらもエラーWAしまくって死亡。こういうときは寝るに限る！
ベッドで缶切り必要缶詰の個数を全探索すればええやんということに気づき、実装。缶切り必要缶詰をx個開けるとき、必要な缶切りの数は降順ソートした缶切りの累積和を二分探索すれば求まり、残りの個数缶切り不要缶詰を開ければよい。いずれも降順ソートしたうえで累積和を持っておけば計算が速いのでそうする。必要な缶切りが用意できないとか用意したらM個超えてるとかに注意。
atcoder.jp
G 全方位木DPあんまわかってないんだよなあと思いつつ挑戦。そのままの通り数も計算できるっぽいが、頭が痛くなってきたので余事象を考える。パスになる3点のうち、中点を根とする木を考えると、残りの2点は異なる子部分木から選べばよい。これは、sum x_i * x_j なので、((sum x_i)^2 - sum x_i^2) / 2 で求まる。あとは子部分木の大きさが分かればよく、最初にDFSして0を根としたときの各子部分木の大きさを求めておく。根をuに張り替えたとき、元親のほうの子部分木の大きさはSize[0]-Size[u]である。もう一度DFSして数え上げていけばOK。
atcoder.jp
ABC311 F DP+累積和解法
解説とは少し違う方法な気がしています。本質的に同じになるかもしれませんが、詰めるのが面倒くさい。
各列について考えます。美しいグリッドの各列は下から何マスか黒色で、その上はすべて白色になります。各列何マスを黒色にできるかは、その列が元々どのように黒色に塗られていたかと、左右の列の塗り方によります。したがって、「i列目をkマス黒色に塗るときの、i列目までの塗り方の通り数」をDPすればよいです。以後DP[i][j] とします。
i列目の下からj' マス目が元々黒色のとき、i列目をj (＜j') マス黒色に塗ることはできません。すなわち、DP[i][j]=0 (j=0,1,..., j' - 1)。
i列目をjマス黒色に塗るには、i-1列目がj+1より大きいマス黒色に塗られていてはいけません。逆に言えば、0マス～j+1マス黒色に塗られているのはOKです。したがって、DP[i][j] = DP[i-1][0] + DP[i-1][1] + ... + DP[i-1][j + 1]。
これはもちろん律儀に計算していると間に合わないので、累積和を求めておきます。副作用として、最終的な答えがCum[M-1][N]=DP[M-1][0]+DP[M-1][1]+...+DP[M-1][N]と求まっています。これにより、O(NM) で計算でき、十分に高速です。
右から決めていくほうが制約が強くて良さそうな感じがしますが、強い分部分和を求める必要があり、累積和でウッとなることになります。その点、左から決めていく方法であればつねに0～j+1の和であるので、0に番兵を置いて良い感じにしなくても済むというメリットがあります。
私は（特に本番でない場合）DPの計算に必要でない部分はすぐに捨てるタチなのでこのように捨ててやっていますが、混乱する人はすべてのDPの値と累積和を保存しても間に合います。
ところで、こうやって捨てていると、上の提出でもまだ無駄な部分が見えてきます。まず、DPの値を求めてから累積和を計算していますが、DP[i][j]の値が求まったそばから次のCum[i][j]を計算しても問題ありません。DP[i][j+1]の計算に必要なのはCum[i-1][j+2]またはCum[i-1][j+1]なので、Cum[i][j]を新しい配列Cum[i]に入れておく必要もなく、常にCum[i-1][j]に上書きして問題がありません。これにより、Cumは一つの一次配列Cumのみを使い回すことで計算が済みます。また、DP[i][j]の値は、Cum[j]を計算するのにしか用いませんから、二次配列DPどころか、一次配列DP[i]を保持する必要もありません。Cum[0]=DP[0]のみ別に計算する必要があることに注意してください。
DP[i][j]の値をxと置いたのが以下の提出です。
atcoder.jp
それも省くと以下になります。Cum[j] = Cum[j - 1] + (j >= st) * Cum[min(N, j + 1)]はもはや何を計算しているのかよくわからないですね。
atcoder.jp
ABC309 (デンソークリエイトプログラミングコンテスト2023)
85分+5WA 6完 784th performance:1631
思ったよりかは死ななかったがrate1800が遠い
atcoder.jp
A 私は左右を上下左右と読みました、悪問 (21:01->21:02)
サンプルにも上下隣接がないの、極悪（あったらあったで首を捻り続けてそうな気がするが）
B 隣接を求めて反時計回りにいい感じの回数入れ替えていく、隣接を求めるのが反時計回りか時計回りかで混乱するし、条件分岐が多くて時間を溶かした (21:13)
atcoder.jp
C ソートして順に見て合計がKより小さくなった日を求める (21:18)
atcoder.jp
D BFSして前後最も遠い点を探す。 (21:27)
最初「なるほど、2つに分かれているグラフを結んだときに1とNが最短になるときか……1とNを結べば常に1では？」となった、そんなのDで出題されるか。「最短距離」と聞くとすぐダイクストラを連想する人が多いのかトレンド入りとかしてたけど、辺長1のグラフの最短距離はたいがいBFSで済むので変な学習をしてる人がいないか心配ではある（BFSもダイクストラも更新順が変なDPという認識があんまないのかも）
atcoder.jp
E 保険が効く長さを更新しつつBFS (21:40)
同じ人間が複数の保険に入っている場合があり、そこらへん入出力で見逃しそうという感じがした（短いほうの保険で上書きしてしまう）
atcoder.jp
Dの影響もあり、普通にグラフにしたが、問題の制約から常に親は子より若い番号であるから、受け取るDPで解ける。
atcoder.jp
F (22:25)
条件を満たす2つの箱のサイズを{a1,a2,a3} ＜ {b1,b2,b3}とする。a1≦a2≦a3とすると、b1≦b2≦b3となるように並べ替えたときにa1＜b1, a2＜b2, a3＜b3となる。したがって、すべての箱のサイズはa1＜a2＜a3となるように並べ替えてよい。並べ替えたものを(h,w,d)とする。
Nの制約より、明らかにソートはOK。最初は最大と最小を比べるだけでOKかと思ったが、(1,10,3),(2,3,4),(3,4,5)みたいなときにダメ。2番目のサイズについても昇順に見たいので(w,d)の優先度付きキューとかでなんとかならないかと思ったが、(1,2,10),(2,3,4),(3,4,5)みたいなときにダメ。mapで「wがX以下のときのdの最小」を管理できないかと思ったが、後ろに波及するのでダメ。
ここでmapを使ったあたりから座標圧縮するとなんか良さそうな感じに気付く。「wがX以下のときのdの最小」はもう少し難しいデータ構造を使えばできそうな感じがしたのでちょっと考えた感じセグメント木が使えそうだと気付く。wはそのままでは10^9でセグメント木に乗らないが、座標圧縮すれば2*10^5になり間に合う。それでなんとか書き上げて提出するがWA。落とし穴に3箇所ぐらい嵌った。
1箇所目がソート順。単に昇順で良さそうだが、常にh(i-1)＜hiが保証されているわけではなく、h(i-1)=hiの場合があり、w(i-1)＜wi, d(i-1)＜diのときにOKと誤判定してしまう。hを昇順、wを降順とすることで、h(i-1)=hiのときは常にw(i-1)≧wiにできる。ソート用のラムダ関数を間違えて1RE、1WA出ていたもののランタイムエラーの影響と考えて、ラムダ関数を直して突っ張ったがもう2箇所ミスがあり、+1WA。
2箇所目がセグメント木の更新。常に出てきたseg[w']=dと更新していたが、w'はこれより前に登場している可能性があり、seg[w']＜dとなっている場合がある。最小値更新する必要がある。これを直して+1WA。dも降順にソートすればOKじゃね？と思ったが、hi≠hj, wi=wjのパタンがあるのでダメ。
3箇所目がセグメント木のprodの範囲。w'を含めてしまっていたが、これはhi＜hj, wi=wj, di＜djのパタンをOKと誤判定してしまう。w'を除いた範囲にする必要がある。これを直して4WAでなんとか突破した。
座標圧縮してセグメント木とかかなり牛刀を持ち出してしまった感じがしたが、解説を読む限り想定解でビビった。そのうえで900人近くこれを通していることにもビビった。レベルが高い。
G Fで沼ったときにちょっと見て包除原理と筋肉！という感じがしたのでパス。X≦5あたり行列累乗かなあとか思ったが、2^(2X)状態を考える感じのDPらしい。
ABC308 (CodeQUEEN 2023 予選)
43分+1WA 6完
atcoder.jp
A はい (21:01)
atcoder.jp
B 最初C,Dを20以下の整数と勘違いした、map (21:06)
atcoder.jp
C 分数構造体を作っていますか？はい。ただ比較をlog取って済ませるタイプ（たしか分母×分子がlong longに収まらないタイプの問題用だった）にしてて誤差で1WA、10^18はlong longで間に合うので辺々払って比較した (21:15->21:16)
atcoder.jp
等号演算子を定義しなくて済むので、stable_sortを使うのがよいですね
atcoder.jp
D BFS、条件をコピペしまくった (21:21)
atcoder.jp
まあ"snukes"を用意してfindしましょう
atcoder.jp
E M0,M1,M2,X0,X1,X2について累積和して数え上げ、全パタン書き出したのはよくない方針だった (21:34)
atcoder.jp
M, Xを二次元vectorにしてmexの計算はプログラムにさせましょう
atcoder.jp
Eを探すのは2文字目からで良いから、M[0]にアクセスする必要がないので、1-indexedにしなくても累積和がどうにかなりそう
F 割引額の大きいほうから使える商品で一番安いのを選ぶ貪欲でよい、multisetで二分探索して除去 (21:43)
atcoder.jp
公式解説は「安い商品から使える割引券で一番割引額が大きいのを選ぶ」という逆の貪欲でしたが、ユーザ解説でこちらの貪欲も証明されています（証明してから貪欲を投げろ）
atcoder.jp
G なんかbitごとにいい感じにやればxを使うXOR最小値求まりそうだなあと思って色々やったけど複雑すぎて諦めた
解説AC、天才の発想すぎて無理……「整数集合から2つ選んだXORの最小は整列させた隣り合う数のXORのどれか」、典型感はないけど類題あったりするのかなあ
atcoder.jp
プログラミングの基礎文法力を上げると良い
だいたい競技プログラミングにおいてレートを上げるのに効くのは、使える道具を増やすか速解き力をつけることである。
速解き力について人はなんとなく苦手意識を持ちがちだが、これはだいたい「焦って解きたくない」という誤解に基づく（私もそうだった）。しかし実際、速解き力とは焦らずにプログラムを書く能力であると思う。したがって、使える道具の数によらず、常に速解き力は鍛えることができ、次に使えるようになるべき道具が手に余るようであれば速解き力に目を向けたほうが良い。ある程度速解き力がつくと次の道具を身につける余裕も出てくる。
速解き力についての苦手意識その2が、これが「慣れ」によって得られるものであるから、というヤツである。確かに「慣れ」は重要であるのだが、そもそもどうやれば速く解けるのか、ということを理解していないのに「慣れ」が生じることはなく、ここにあまり伸びる余地はない。タイピング力を鍛えるのもそこまで重要ではない。
で、手っ取り早く速解き力を上げる方法がプログラミングの基礎文法力を上げることである。だいたい基礎文法力がないプログラムは、無駄に長い。試しに自分の昔の提出なりレートの低い他人の提出を見てみると、無駄なことを書いてあることがわかると思う。今まで書いていた「プログラムの書き方」を短くするだけなので高度な数学能力は必要なく、「なんとなく」で済ませていた文法に目を向けるだけである。
コンテスト後は解説を読み、提出したプログラムの書き直しをするとよい。理解していたとしても本番で実践できているとは限らず、見直すことで無駄が見つかることも多い。
以下、C++を使う上で自分が意識できていること。
