ABC218-C「Shapes」を解きました✅
図形を切り出して正規化し、90度回転を最大4回試して一致するか判定するだけ。`zip(*fig)`と`[::-1]`を組み合わせた回転の書き方がエレガントで気に入っています🔷
https://gist.github.com/maehrm/0abeae3c19bc75e8ad5c77e690e1b8ad
#AtCoder #競技プログラミング
YMM728 @hyuki.net AIとの付き合いの変遷の見える化は面白いですね。初めてメルマガで話題になったのが2022年12月、もう3年も経つのかという印象と、この間に世界は大きく変わってしまって、もはやAIのなかった時代が想像できないですね。本メルマガのお陰でAIとの付き合い方を学ばせてもらってます。感謝。
ABC139-E「League」を解きました✅
「試合」を頂点、「先にやるべき試合 → 後の試合」を有向辺としてグラフを構築し、トポロジカルソートで最長パスを求める問題でした。試合を頂点に見立てる発想が面白かったです🏆
https://gist.github.com/maehrm/a00cd9f67064615ffb4e03427f8efe2a
#AtCoder #競技プログラミング
ABC280-D「Factorial and Multiple」を解きました✅
N!がKの倍数になる最小のNを求める問題です。Kを素因数分解し、各素因数ごとにN!で必要な個数が揃うNを求めてその最大値が答え。素因数ごとに独立に考えられるのがポイントでした🔢
https://gist.github.com/maehrm/09fd96029aa0f7af7e678ed0c096db4b
#AtCoder #競技プログラミング
『AIと生きる』、昨晩、届いてたようです。今朝、気づきました。配達してくださった方々、ありがとうございます！楽しみたいと思います。
もう少し。Kindle版を購入すれば、すぐに読めるんでしょうけど、本棚に立てて、家族と共有して読もうと思う本は、紙の本がいいですね。
ABC253-E「Distance Sequence」を解きました✅
dp[i][j]で管理し、遷移は累積和でO(1)に高速化。「j-K以下」と「j+K以上」の2区間の和を使うのがポイントでした📏
https://gist.github.com/maehrm/f6011fa7f5d8cea5808eff57b04cb3a7
#AtCoder #競技プログラミング
ABC331-E「Set Meal」を解きました✅
副菜を金額の高い順にソートし、各主菜に対して禁止されていない最高値の副菜を選ぶ貪欲法で解きました🍱 禁止ペアが少ないので内側ループは実質O(1)に近いです。
https://gist.github.com/maehrm/ede2d2ce87e99946bf536fd697ac9e57
#AtCoder #競技プログラミング
ABC381-D「1122 Substring」を解きました✅
2つおきに要素を見るスライディングウィンドウで解きました。偶数・奇数インデックス始まりの2パターンを試して重複が出たら左端を縮める実装です🔢
https://gist.github.com/maehrm/4dd46b9f137cccb677370dd553ca0231
#AtCoder #競技プログラミング
『AIと生きる』、本日到着予定とのこと、首を長くして待ってます。
ABC181-E「Transformable Teacher」を解きました✅
先生を挿入する位置を二分探索で求めて、前後の累積和を合算するABC334-Cと同じ発想で解けました。つながりを感じる一問でした👨🏫
https://gist.github.com/maehrm/d1e8b2b6eb58001c8f094158bdefae6e
#AtCoder #競技プログラミング
ABC334-C「Socks 2」を解きました✅
Kが偶数なら隣接ペアを順に組むだけ。奇数のときは除く1枚の位置を前後の累積和で管理してO(K)で全探索しました🧦
https://gist.github.com/maehrm/78232c047cca088a099c1915ac153adf
#AtCoder #競技プログラミング
ABC323-E「Playlist」を解きました✅
dp[t]を「時刻tに曲が始まる確率」として定義し、各曲の長さで遷移する確率DP。逆元を事前計算してmod演算に対応しました🎵
https://gist.github.com/maehrm/a585820894c64d4e4069966c23f82f92
#AtCoder #競技プログラミング
ABC241-E「Putting Candies」を解きました✅
Kが最大10^18なのでループ検出が必要。訪問履歴でサイクルを見つけ、ループ分をまとめて計算してO(N)に収めました🍬
https://gist.github.com/maehrm/5c203894c1abe415a349f86b4f3d84a4
#AtCoder #競技プログラミング
ABC261-D「Flipping and Bonus」を解きました✅
dp[i][j]（i枚目・連続表j回）で管理し、裏が出たときは直前の連続回数の最大値を引き継ぐDP問題でした🪙
https://gist.github.com/maehrm/e074403df2588dace0516c99167055a3
#AtCoder #競技プログラミング
ABC339-E「Smooth Subsequence」を解きました✅
セグメント木で「値vを末尾とする最長部分列長」を管理し、[v-D, v+D]の最大値+1をセットするだけのO(NlogN)解法。DPとSegTreeの組み合わせがスッキリしていて面白かったです🎶
https://gist.github.com/maehrm/495eeb8497b6add6dd704ff3455cb77c
#AtCoder #競技プログラミング
#皆既月食 観察しました。写真はイマイチです。
YMM727 @hyuki.net さんの初めての「縦書き」の新刊、読むのを楽しみにしています。Claude Desktopについてはだいぶ使い慣れてきたのですが、Claude Codeについてはまだまだという状況ですので、楽しい補完機能、早くあやかりたいですね。
ABC312-C「Invisible Hand」を解きました✅
3次元DPで頭が疲れたので軽めの問題に😅 売り手・買い手の人数をbisectで求めて二分探索する実装でスッキリ解けました。
https://gist.github.com/maehrm/95a4b877f0c45afb4983f1f572a6269e
#AtCoder #競技プログラミング
ABC244-E「King Bombee」を解きました✅
dp[移動回数][X通過の偶奇][現在地]の3次元DP。頂点Xを通るたびにparityを反転させるだけでシンプルに実装できました👑
https://gist.github.com/maehrm/0d2fb5aee09d97412c07c07f63a3ce97
#AtCoder #競技プログラミング
解説を読むと、ハッシュ法の手法に基づいているとのこと。学生時代、チェイン法については、ポインタの演習があったのを覚えていますが、オープンアドレス法については、衝突したら次へ位の理解しかありませんでした。考えてみれば、空いているところを効率よく見つける手法って大切ですよね。
ABC228-D「Linear Probing」を解きました✅
埋まったスロットをUnionFindで次のスロットと結合することで、空きスロット探索をO(α(N))に高速化しました。UnionFindの応用が光る一問でした🔍
https://gist.github.com/maehrm/b1b79926094a076ac3a913504b1f656b
#AtCoder #競技プログラミング
ABC277-D「Takahashi's Solitaire」を解きました✅
ソートして連続グループをまとめ、最大グループ以外の合計が答え。M-1と0が繋がる循環ケースの処理がポイントでした🃏
https://gist.github.com/maehrm/ea42c3d958c895e6c3a5cb67c38bd3d3
#AtCoder #競技プログラミング
ABC412-D「Make 2-Regular Graph」を解きました✅
全頂点の次数が2になる辺の組合せを全探索し、既存辺との差分を最小化する問題です。Nが小さいので全探索が通るのがポイントでした🔗
https://gist.github.com/maehrm/543835045de7885e29c4f3f8e5591430
#AtCoder #競技プログラミング
ABC006-C「スフィンクスのなぞなぞ」を解きました✅
連立方程式を立てると変数が1つ残るので、取りうる範囲を絞り込んで全探索。条件整理で探索範囲が狭まり、割とスムーズに解けました🦁
https://gist.github.com/maehrm/83d72b0c5d64451ee29b332d9c5e8c80
#AtCoder #競技プログラミング
ABC432-E「Clamp」を解きました✅
公式解説を参考に、セグメント木で (count, sum) を管理する方針で実装。l未満・l〜r・r超の3区間に分けてクエリをO(logN)で処理しました🗜️
https://gist.github.com/maehrm/f58e90a7ae8338b6e8f6f26ccf9f803a
#AtCoder #競技プログラミング
ABC035-C「オセロ」を解きました✅
区間反転クエリをimos法で処理する問題です。各マスの反転回数を累積和で求めて、奇数回なら反転と判定するだけでO(N+Q)に収まりました🎲
https://gist.github.com/maehrm/20a977ccf28af4ce718d4d4494d911d8
#AtCoder #競技プログラミング
覆面算は過去にも取り組んだことがあって、そのときも"SEND MORE MONEY"に笑わせてもらったのでとても印象に残ってます。このときは、DFSによる解法でした。#Python maehrm.hatenablog.com/entry/2023/0...
ABC198-D「Send More Money」を解きました✅
文字の種類が最大10種類なので `permutations` で全探索。最初はDFSで挑もうとしましたが、シンプルな全探索の方がすっきり書けました🔢
https://gist.github.com/maehrm/44829f8b6f4eb8948cbf82af1fda2db0
#AtCoder #競技プログラミング
ABC297-E「Kth Takoyaki Set」を解きました✅
ヒープに0を積んでおき、取り出した値にA[i]を足して次の候補を追加、setで重複管理しながらK回繰り返す実装でした🐙
https://gist.github.com/maehrm/79b4a46b8dd898600c9398f55bf22e10
#AtCoder #競技プログラミング
