ayu
@ayutake.bsky.social
競プロ／AtCoder(C# A青H水)
https://atcoder.jp/users/ayutake
アイコン：れお様(https://www.pixiv.net/artworks/130549564)
https://atcoder.jp/users/ayutake
アイコン：れお様(https://www.pixiv.net/artworks/130549564)
Pinned
ayu
@ayutake.bsky.social
· Sep 21
競プロの備忘録用にBluesky始めました
ABC436 oooooox
A 腹痛で1分遅れ
B 問題文の通りに
C ブロックが置かれるマスは高々M*4個なので全部HashSetに入れていい
D なんか見覚えあるような… 同じ文字を使って2回以上ワープするのは無駄なので、各文字のワープは1回までとすると、行動パターン数を少なくできる
E 良いswapとダメなswapを色々試した結果、i→P[i]でグラフを作ったとき、同じサイクル内の2要素をswapすると大丈夫っぽい(未証明)
A 腹痛で1分遅れ
B 問題文の通りに
C ブロックが置かれるマスは高々M*4個なので全部HashSetに入れていい
D なんか見覚えあるような… 同じ文字を使って2回以上ワープするのは無駄なので、各文字のワープは1回までとすると、行動パターン数を少なくできる
E 良いswapとダメなswapを色々試した結果、i→P[i]でグラフを作ったとき、同じサイクル内の2要素をswapすると大丈夫っぽい(未証明)
December 13, 2025 at 1:47 PM
ABC436 oooooox
A 腹痛で1分遅れ
B 問題文の通りに
C ブロックが置かれるマスは高々M*4個なので全部HashSetに入れていい
D なんか見覚えあるような… 同じ文字を使って2回以上ワープするのは無駄なので、各文字のワープは1回までとすると、行動パターン数を少なくできる
E 良いswapとダメなswapを色々試した結果、i→P[i]でグラフを作ったとき、同じサイクル内の2要素をswapすると大丈夫っぽい(未証明)
A 腹痛で1分遅れ
B 問題文の通りに
C ブロックが置かれるマスは高々M*4個なので全部HashSetに入れていい
D なんか見覚えあるような… 同じ文字を使って2回以上ワープするのは無駄なので、各文字のワープは1回までとすると、行動パターン数を少なくできる
E 良いswapとダメなswapを色々試した結果、i→P[i]でグラフを作ったとき、同じサイクル内の2要素をswapすると大丈夫っぽい(未証明)
(強連結成分分解)やるんだな！？今(D問題)…！ここで！
になりかけたけど踏みとどまったし実際要らない
になりかけたけど踏みとどまったし実際要らない
December 6, 2025 at 1:48 PM
(強連結成分分解)やるんだな！？今(D問題)…！ここで！
になりかけたけど踏みとどまったし実際要らない
になりかけたけど踏みとどまったし実際要らない
ABC435 oooooo-
A RangeとSum
B そのまま
C ドミノを左から見ながら、倒れる一番右のドミノを二分探索で更新していく
D 「黒に到達可能」は「グラフを逆走して黒から到達可能」なので、辺を逆向きにしたグラフで黒頂点からBFSを行い、到達可能な頂点も全部黒頂点とみなしてしまう
E 黒く塗られたマスの区間を集合で管理して、クエリで与えられた区間とマージしていけばいいんだけど、実装が迷子になっていた(区間の右端のリストと、右端に対応する左端の辞書をもつと何とかなる)
F 再帰したら通ってしまった なんでこれで間に合うのか分かってない 懺悔
A RangeとSum
B そのまま
C ドミノを左から見ながら、倒れる一番右のドミノを二分探索で更新していく
D 「黒に到達可能」は「グラフを逆走して黒から到達可能」なので、辺を逆向きにしたグラフで黒頂点からBFSを行い、到達可能な頂点も全部黒頂点とみなしてしまう
E 黒く塗られたマスの区間を集合で管理して、クエリで与えられた区間とマージしていけばいいんだけど、実装が迷子になっていた(区間の右端のリストと、右端に対応する左端の辞書をもつと何とかなる)
F 再帰したら通ってしまった なんでこれで間に合うのか分かってない 懺悔
December 6, 2025 at 1:43 PM
ABC435 oooooo-
A RangeとSum
B そのまま
C ドミノを左から見ながら、倒れる一番右のドミノを二分探索で更新していく
D 「黒に到達可能」は「グラフを逆走して黒から到達可能」なので、辺を逆向きにしたグラフで黒頂点からBFSを行い、到達可能な頂点も全部黒頂点とみなしてしまう
E 黒く塗られたマスの区間を集合で管理して、クエリで与えられた区間とマージしていけばいいんだけど、実装が迷子になっていた(区間の右端のリストと、右端に対応する左端の辞書をもつと何とかなる)
F 再帰したら通ってしまった なんでこれで間に合うのか分かってない 懺悔
A RangeとSum
B そのまま
C ドミノを左から見ながら、倒れる一番右のドミノを二分探索で更新していく
D 「黒に到達可能」は「グラフを逆走して黒から到達可能」なので、辺を逆向きにしたグラフで黒頂点からBFSを行い、到達可能な頂点も全部黒頂点とみなしてしまう
E 黒く塗られたマスの区間を集合で管理して、クエリで与えられた区間とマージしていけばいいんだけど、実装が迷子になっていた(区間の右端のリストと、右端に対応する左端の辞書をもつと何とかなる)
F 再帰したら通ってしまった なんでこれで間に合うのか分かってない 懺悔
ABC434 ooooox-
A 風船を1個ずつ増やす
B Enumerable.Average
C 次の時刻まで急上昇と急降下だけ考えると有効な範囲が定まる
D 各マスについて覆っている雲の個数を計算して、その結果が「1」になるマスの個数を取得できる2次元累積和を前計算する
E ウサギのジャンプ先同士を結んだグラフでなもりグラフの閉路検出みたいなことをやるだけのはずなのに実装にめちゃくちゃ手こずった上にWAも出て最悪
F ワンチャンNextPermutationパンチが通るはずもなく
A 風船を1個ずつ増やす
B Enumerable.Average
C 次の時刻まで急上昇と急降下だけ考えると有効な範囲が定まる
D 各マスについて覆っている雲の個数を計算して、その結果が「1」になるマスの個数を取得できる2次元累積和を前計算する
E ウサギのジャンプ先同士を結んだグラフでなもりグラフの閉路検出みたいなことをやるだけのはずなのに実装にめちゃくちゃ手こずった上にWAも出て最悪
F ワンチャンNextPermutationパンチが通るはずもなく
November 29, 2025 at 1:47 PM
ABC434 ooooox-
A 風船を1個ずつ増やす
B Enumerable.Average
C 次の時刻まで急上昇と急降下だけ考えると有効な範囲が定まる
D 各マスについて覆っている雲の個数を計算して、その結果が「1」になるマスの個数を取得できる2次元累積和を前計算する
E ウサギのジャンプ先同士を結んだグラフでなもりグラフの閉路検出みたいなことをやるだけのはずなのに実装にめちゃくちゃ手こずった上にWAも出て最悪
F ワンチャンNextPermutationパンチが通るはずもなく
A 風船を1個ずつ増やす
B Enumerable.Average
C 次の時刻まで急上昇と急降下だけ考えると有効な範囲が定まる
D 各マスについて覆っている雲の個数を計算して、その結果が「1」になるマスの個数を取得できる2次元累積和を前計算する
E ウサギのジャンプ先同士を結んだグラフでなもりグラフの閉路検出みたいなことをやるだけのはずなのに実装にめちゃくちゃ手こずった上にWAも出て最悪
F ワンチャンNextPermutationパンチが通るはずもなく
AHC057
よく分かんなかったから適当にウニやMSTを作って終了
よく分かんなかったから適当にウニやMSTを作って終了
November 29, 2025 at 10:01 AM
AHC057
よく分かんなかったから適当にウニやMSTを作って終了
よく分かんなかったから適当にウニやMSTを作って終了
去年の7月に整備した競プロ用の入出力ライブラリにバグが見つかってテンション上がってる
November 23, 2025 at 2:32 AM
去年の7月に整備した競プロ用の入出力ライブラリにバグが見つかってテンション上がってる
ABC433 oooooo-
A 怖い 慎重に一次方程式
B 各人で全探索
C ランレングス圧縮で(文字,長さ)の列にして、(a,x),(a+1,y)がこの順で隣り合っていたらmin(x,y)を答えに加算
D A[i]*10^j mod M の辞書を作って集計
A 怖い 慎重に一次方程式
B 各人で全探索
C ランレングス圧縮で(文字,長さ)の列にして、(a,x),(a+1,y)がこの順で隣り合っていたらmin(x,y)を答えに加算
D A[i]*10^j mod M の辞書を作って集計
November 22, 2025 at 2:02 PM
ABC433 oooooo-
A 怖い 慎重に一次方程式
B 各人で全探索
C ランレングス圧縮で(文字,長さ)の列にして、(a,x),(a+1,y)がこの順で隣り合っていたらmin(x,y)を答えに加算
D A[i]*10^j mod M の辞書を作って集計
A 怖い 慎重に一次方程式
B 各人で全探索
C ランレングス圧縮で(文字,長さ)の列にして、(a,x),(a+1,y)がこの順で隣り合っていたらmin(x,y)を答えに加算
D A[i]*10^j mod M の辞書を作って集計
来週のAHCは11/29だから、ストーリーが「11月29日は『いい肉の日』です。」で始まって、肉を焼くときの配置を最適化する問題にならないかな
見覚えしかない設定だけど
見覚えしかない設定だけど
November 21, 2025 at 10:36 AM
来週のAHCは11/29だから、ストーリーが「11月29日は『いい肉の日』です。」で始まって、肉を焼くときの配置を最適化する問題にならないかな
見覚えしかない設定だけど
見覚えしかない設定だけど
明日ABCだけど11/22じゃん
終わった……
終わった……
November 21, 2025 at 10:11 AM
明日ABCだけど11/22じゃん
終わった……
終わった……
自分に「600点より上の問題が今の実力でコンテスト中に解けるわけないだろ」というバイアスがかかっている節があり、これは非常に良くない
November 16, 2025 at 2:17 PM
自分に「600点より上の問題が今の実力でコンテスト中に解けるわけないだろ」というバイアスがかかっている節があり、これは非常に良くない
ARC210(unrated) oox---
A 隣接要素の差分配列を(1,1,...,1)で初期化しておいて、各操作ではiq番目の差分にxq加える
このとき後半の数が大きくなりすぎないようにするために(iq+1)番目の差分からxq減らしていいけど、差分が0以下になってしまったら1に戻す
後は差分配列→操作後のA→操作前のAと復元する
A 隣接要素の差分配列を(1,1,...,1)で初期化しておいて、各操作ではiq番目の差分にxq加える
このとき後半の数が大きくなりすぎないようにするために(iq+1)番目の差分からxq減らしていいけど、差分が0以下になってしまったら1に戻す
後は差分配列→操作後のA→操作前のAと復元する
November 16, 2025 at 2:07 PM
ARC210(unrated) oox---
A 隣接要素の差分配列を(1,1,...,1)で初期化しておいて、各操作ではiq番目の差分にxq加える
このとき後半の数が大きくなりすぎないようにするために(iq+1)番目の差分からxq減らしていいけど、差分が0以下になってしまったら1に戻す
後は差分配列→操作後のA→操作前のAと復元する
A 隣接要素の差分配列を(1,1,...,1)で初期化しておいて、各操作ではiq番目の差分にxq加える
このとき後半の数が大きくなりすぎないようにするために(iq+1)番目の差分からxq減らしていいけど、差分が0以下になってしまったら1に戻す
後は差分配列→操作後のA→操作前のAと復元する
ABC432 oooooxx
A 実装にちょっと迷う
B 実装にちょっと迷う
C 個数が一番少ない子供に合わせるために、一旦全部大きい飴で配って、余剰分を小さい飴に交換して調整する
D 実装だるすぎ！大嵐によって長方形が分割されていくと考えると最終的に高々2^N個の長方形になるので(大嵐の内容から長方形が重なることはない)、頑張ってシミュレーションして長方形を列挙した後、頑張って長方形同士の隣接を判定して集計する
E なんでl>rも混ぜたの？セグ木で個数と総和を管理しながら、クエリ2ではl以下の個数とr以上の個数を使って計算する
A 実装にちょっと迷う
B 実装にちょっと迷う
C 個数が一番少ない子供に合わせるために、一旦全部大きい飴で配って、余剰分を小さい飴に交換して調整する
D 実装だるすぎ！大嵐によって長方形が分割されていくと考えると最終的に高々2^N個の長方形になるので(大嵐の内容から長方形が重なることはない)、頑張ってシミュレーションして長方形を列挙した後、頑張って長方形同士の隣接を判定して集計する
E なんでl>rも混ぜたの？セグ木で個数と総和を管理しながら、クエリ2ではl以下の個数とr以上の個数を使って計算する
November 15, 2025 at 1:56 PM
ABC432 oooooxx
A 実装にちょっと迷う
B 実装にちょっと迷う
C 個数が一番少ない子供に合わせるために、一旦全部大きい飴で配って、余剰分を小さい飴に交換して調整する
D 実装だるすぎ！大嵐によって長方形が分割されていくと考えると最終的に高々2^N個の長方形になるので(大嵐の内容から長方形が重なることはない)、頑張ってシミュレーションして長方形を列挙した後、頑張って長方形同士の隣接を判定して集計する
E なんでl>rも混ぜたの？セグ木で個数と総和を管理しながら、クエリ2ではl以下の個数とr以上の個数を使って計算する
A 実装にちょっと迷う
B 実装にちょっと迷う
C 個数が一番少ない子供に合わせるために、一旦全部大きい飴で配って、余剰分を小さい飴に交換して調整する
D 実装だるすぎ！大嵐によって長方形が分割されていくと考えると最終的に高々2^N個の長方形になるので(大嵐の内容から長方形が重なることはない)、頑張ってシミュレーションして長方形を列挙した後、頑張って長方形同士の隣接を判定して集計する
E なんでl>rも混ぜたの？セグ木で個数と総和を管理しながら、クエリ2ではl以下の個数とr以上の個数を使って計算する
最初BFSで書いていて後から01BFSに直すとなるとQueue→LinkedListの書き換えが必要で、それよりはダイクストラに直す方がQueue→PriorityQueueで楽だなって思っちゃう
November 8, 2025 at 2:21 PM
最初BFSで書いていて後から01BFSに直すとなるとQueue→LinkedListの書き換えが必要で、それよりはダイクストラに直す方がQueue→PriorityQueueで楽だなって思っちゃう
ABC431 oooooo-
A max(H-B,0)
B ついている部品を適当に管理
C 頭パーツの重さの昇順に、なるべく近い重さの体パーツを取っていく
D 制約にDPをしてくださいと書いてあった
E 「光が入ってきたマス」と「光が入ってきた方向」を1つのキーにして頑張ってダイクストラ(今思うと01BFSで良かった)
F Aをソートして、各A_{i}について「Bに既にA_{i+1},...,A_{N}が割り当てられている時、挿入できる位置の個数は？」を二分探索で計算した後、同じ値同士の並び替えを除外する
A max(H-B,0)
B ついている部品を適当に管理
C 頭パーツの重さの昇順に、なるべく近い重さの体パーツを取っていく
D 制約にDPをしてくださいと書いてあった
E 「光が入ってきたマス」と「光が入ってきた方向」を1つのキーにして頑張ってダイクストラ(今思うと01BFSで良かった)
F Aをソートして、各A_{i}について「Bに既にA_{i+1},...,A_{N}が割り当てられている時、挿入できる位置の個数は？」を二分探索で計算した後、同じ値同士の並び替えを除外する
November 8, 2025 at 2:00 PM
ABC431 oooooo-
A max(H-B,0)
B ついている部品を適当に管理
C 頭パーツの重さの昇順に、なるべく近い重さの体パーツを取っていく
D 制約にDPをしてくださいと書いてあった
E 「光が入ってきたマス」と「光が入ってきた方向」を1つのキーにして頑張ってダイクストラ(今思うと01BFSで良かった)
F Aをソートして、各A_{i}について「Bに既にA_{i+1},...,A_{N}が割り当てられている時、挿入できる位置の個数は？」を二分探索で計算した後、同じ値同士の並び替えを除外する
A max(H-B,0)
B ついている部品を適当に管理
C 頭パーツの重さの昇順に、なるべく近い重さの体パーツを取っていく
D 制約にDPをしてくださいと書いてあった
E 「光が入ってきたマス」と「光が入ってきた方向」を1つのキーにして頑張ってダイクストラ(今思うと01BFSで良かった)
F Aをソートして、各A_{i}について「Bに既にA_{i+1},...,A_{N}が割り当てられている時、挿入できる位置の個数は？」を二分探索で計算した後、同じ値同士の並び替えを除外する
問題文で急にC#について言及されてびっくりした
November 8, 2025 at 10:04 AM
問題文で急にC#について言及されてびっくりした
November 5, 2025 at 2:12 PM
EnqueueとDequeueを区別するときに「"出"ていくのが"De"queue」というアホな覚え方をしたのを思い出した
November 4, 2025 at 2:34 PM
EnqueueとDequeueを区別するときに「"出"ていくのが"De"queue」というアホな覚え方をしたのを思い出した
「Queue」はもちろん「キュー」で、「Enqueue」もちゃんと「エンキュー」なんだけど、「Dequeue」だけなぜか「でくえうえ」になってしまう
November 4, 2025 at 2:32 PM
「Queue」はもちろん「キュー」で、「Enqueue」もちゃんと「エンキュー」なんだけど、「Dequeue」だけなぜか「でくえうえ」になってしまう