水色コーダーになってから初めてのABC。つもりが、D問題で迷宮に陥り、時間切れ。Three素直にif-elseする問題。みたいに解いた人がいたらしい。確かに、同じ数を偶数回XORするとその数は消えるから、答えが残るね。絶対に思いつかないな〜。Minesweeperいわゆるマインスイーパの爆弾の位置が与えられて、空きマスについて、8近傍に爆弾がいくつあるかを求める問題。これも基本的なif-elseとfor文が使えればできそう。ABCのBにしては実装量が少し多い。仕方なく答えを書き出す用のansという配列の配列を用意してる。最終的にansを結合して出力してる。あとは、8近傍の調べ方がいくつかテクがあるっぽい。解説のソースコードを抜粋すると、↓の書き方だった。-1};でもこれ、うまく説明できないけど、なんかモヤっとする...。dx[i]とdy[i]はセットで意味をなすので、(dx[i],dy[i])みたいにまとめたいと思ってしまう。(dx[i],dy[i])とタプルでまとめたコードを貼り付けた。カッコで囲ってるぶん、タイプ数が少し多いような。競プロは早さを競うのだからうだうだ言ってられませんがな。次からは素直にdxとdyでやるか。(ズコーちなみに、上で載せた私のコードは実はブログ用に書き直してて、本番でAC取ったのは愚直なif-elseの山。Bridge二重辺や自己ループのない無向連結グラフがあって、取り除いたら連結じゃなくなる辺がいくつあるか。1print(ans)Union-Findを使って解いた。Union-Findは、競プロ歴5ヶ月の私が知ってる知識をざっくり説明すると、グラフのある頂点とある頂点が繋がってるかどうか高速に判定するよ辺がない状態から、辺を追加しながら構築するよ。構築の途中でも判定できるよ判定も追加もほぼ定数時間(ちょうはやい)。アッカーマン関数(とてもでかい)の逆数だとか初期化するのだけO(N)かかるよ(N:頂点数)上記コード中に出てきたroot()、is_same()、unite()がUnion-Findだけど、スニペットに入れてたやつそのままなのでかなり楽できた。辺eの両端が繋がってるかを判定していけばいい。計算量は、辺ごとにUnion-Find初期化+構築でO(N+M)なので全体でO(M(N+M))かな?NもMも小さいので大丈夫!ちなみに、想定解ではUnion-FindじゃなくてDFSで解いてたみたい。DFSは思いつかなかったので両方思いつくようになりたい。9/14(土)に、「ゆるふわ競技プ...2019-06-24Pythonでheapqから大きい順に取り出したいときにもバグらせにくいやつを書いた表題の通りです。月別アーカイブはてなブログをはじめよう!prd_xxxさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。