問題 atcoder.jp 感想 色とかグリッド上の状態をどのようにすればいいのか。ちょっと複雑で迷った。 解法 まず、一番知りたいのは最終的な「各色のカウント数」である。それを知るためには以下の二点に気を付けなくてはいけない。 同じ行、列にクエリが飛ん…

問題 atcoder.jp 感想 わからないものがあったら変数おいて解こうね 解法 サンプルケースの２がわかりやすいのでそれを用いて解説する。 5 3 8 7 5 5 山が５個のパターンですね。 まず、求める山の水量をX1,X2,...X5とし、またダムの水量もA1,A2,...A5とする…

問題 atcoder.jp 感想 やらかした。愚直に見ていこうとしてしまいちゃんとテストケースで落とされた。 解法 明らかに足りなかった考慮が完成形が決まっていること。つまりは....####や#####、.....という左側に白、そこから右側に黒がある（もしくはどちらか…

問題 atcoder.jp 感想 わかりませーん。緑diffですが、解けませんでした。「同じ数字が二つ生まれればいける」みたいなところも気づいたが、全く気にも留めずにスルー。こういうのって日頃から頭を使っていない証拠なのだろうか... 解法 まず、Ｒ,G,Bの組み…

問題 atcoder.jp 感想 間違えたわけではないんだが、キレイに解けなかったので一応はっておく。三角形の面積を使った問題で変数を固定化するところまではよかった。 が、変数を固定化する部分を間違えて誤差にやられた。 解法 editorialでわかる。 https://i…

問題 atcoder.jp 感想 無事死亡。平方根を見ると反射で「math.isqrtだ！」と飛びついてしまい、誤差にやられた。 解法 等式通りに、A,B,Cの範囲を絞っていくだけ。ただ、問題なのは平方根や立方根の扱い。そのままnumpy.cbrtなどとやってしまうと誤差がやば…

問題リンク atcoder.jp 感想 愚直にやってTLEした。そこから「もとの文字列から順序を変えずにつなげたもの」をそのまま受け取ってしまい、元の配列の順番のまま数え上げる方法がわからず（というか面倒）になって集中力がつきてしまった。 ちなみに、今回も…

問題リンク atcoder.jp 感想 茶difだができなくてすごい落ち込んだ。そもそも問題文の意味理解にかなり苦戦した（１０分ぐらい...しかも結局誤読した）。 M=20と反射的にBIT演算でやろうとしたがうまくいかず。そこから思考停止に近い感じになってしまった。…

今更も今更、小数計算でなぜ誤差が起こるのか。そして、その対策って何すればいいのだろうかというお話です。 そもそも小数は「正確」に表現できていない。 まず、コンピュータは数字を二進数で保持しているかと思います。 たとえば、56だと 56 = 111000とな…

高校数学ではさらっと習ったぐらいですが、まさか大人になってこんなに苦しむことになるとは思いませんでした「二項係数」 こちらをコードベース、競技プログラミングで使われている方法をまとめます。 ＊こちらも自分のメモ用です。 奇数・偶数個の組み合わ…

競技プログラミングでよく最大公約数がらみの問題が出てそのたび解けずにおります。なので、ここらでいっちょ自分で簡単にまとめていこうかなと。 ではいきます。 ＊どんどん追記していく自分用メモになります。 ~~ユーグリッド互除法の簡単な証明と忘れがち…