midri1784

競プロに関する備忘録アカウント．参加したコンテストの自分なりの解法・感想を主につぶやいています．正しいとは限らないのでご注意ください．なお，本アカウント名は競プロでのアカウント名とは異なります．
AtCoder: 青
CodeForces: 薄黄
TopCoder: 黄
follow/removeご自由にどうぞ．

[midri1784 @midri1784]

D: 操作によってAは10^9+7-Aに変化するので，区間に操作を適用したときには区間内のAの大小関係が逆転する．よって，(区間最小値，最小値のインデックスの最小値，区間最大値，区間最大値インデックスの最小値)を遅延評価セグメント木に持たせればよい．

[midri1784 @midri1784]

Meta Hacker Cup 2023 R1に参加．5ACでした．
A: N!=5なら左右両端にいる2人の位置の差の平均．N=5のときはサンプル参照．
B1,2:(数列の和，数列の積)->(この和と積を達成する最小要素数の数列) のテーブルを和が1から41まで事前計算．

[midri1784 @midri1784]

よって，ある状態からボタンbが押されたときのPの更新は「もしPにbが含まれていなければbを追加，含まれていればbを削除する」となるので，あとはそれぞれの問題の指示に従って答えを出力．

[midri1784 @midri1784]

F: A[i][j]の総和に対する寄与は，「S[i+1],S[i+2]...S[N]の要素のうちA[i][j]より小さいものの個数」+「j*(N-i)」 (細かい添字は間違ってるかも) GNUのpolicy based data structureで実装すると楽．

[midri1784 @midri1784]

トヨタ自動車プログラミングコンテスト2023#3(AtCoder Beginner Contest 306) 参加．6AC1WAでした．
ブランクでいろいろな知識が抜けてますね・・・
A,B: 問題文のとおり実装
C: fを求めてソート
D: DP
E: 大きい方からK個の集合と残りの集合を管理
参考: https://t.co/mb8RwyJXsC

[midri1784 @midri1784]

F: 隣接頂点に未訪問ものがあるときはその頂点，ないときは現頂点の直前の頂点に戻る，とするとDFS木のそれぞれの辺をたかだか2回移動するので制約を満たす範囲で任意の頂点に移動できます．
G: 行列累乗

[midri1784 @midri1784]

京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305) 参加．7AC0WAでした． #AtCoder #ABC305
およそ5ヶ月ぶりの参加になった割にはよい結果でした．競プロにあまり時間を割けない状況は今後も続きそうですが，ABCには無理のない範囲で出るようにしたい・・・

[midri1784 @midri1784]

E: 優先度付きキューを使って，頂点に警備員が到着したときの残り体力が大きい順に警備されている頂点を登録していけばよいです．計算量は詰められていないので嘘解法かも．

[midri1784 @midri1784]

F: DFS+畳み込みかと思いましたがTLEが取れず時間切れ．

[midri1784 @midri1784]

ユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287) 参加．5AC1WAでした． #AtCoder #ABC287
以前はABCでは最低6ACは達成できると思っていたのですが・・・思考能力が明らかに落ちていて，ブランクの大きさを感じました．
A: Forの人の数を数えて(N+1)/2以上ならYes

[midri1784 @midri1784]

E: Sをソートしておきます（答えの復元のためにインデックスは覚えておきます）．S[i]とのLCPが最大になる文字列はS[i-1]またはS[i+1]なので，LCPを愚直に計算すればよいです．
すべての文字はたかだか4回比較に関与するので計算量は全文字列の文字数の合計に対して線形です．

[midri1784 @midri1784]

いろいろあって競プロを長い期間お休みしてましたが，状況が変わってきたので少しずつ再開していこうと思います．
まずはリハビリとして今日のABCに参加してみます．果たしてどれくらい解けるのだろうか・・・

[midri1784 @midri1784]

久しぶりのツイートになります．
このアカウントは競プロ専用にしていたのですが，いろいろ状況が変わり，最近はほとんど競プロをしていないのでつぶやくこともなくなってました．しばらくはこの状況が続きそうですが，来年のどこかで復活できるかも・・・？
それでは皆様，良いお年をお迎えください．

[midri1784 @midri1784]

AtCoder ProblemsのStreakがついに600日に到達．青diffは完全に枯渇し水色diffも時間の問題になってきました．これ以上続けるなら高難易度の問題にも積極的に取り組まないといけないなあ...

[midri1784 @midri1784]

AtCoder Regular Contest 149 参加．3AC1WAでした． #AtCoder #ARC149
まったく分からない...
A: 総当り
B: 未証明．A or Bをソートするのが最適?
C: N=3,4,5の場合は乱択で作ってハードコード．N>=6のときは，左側に奇数，右側に偶数を固めて，3の倍数が境目にくるようにする．

[midri1784 @midri1784]

G: 行列累乗．D(i,j)="直前のアクセスがi時であったときに，次のアクセスがj時である確率"とすると，答えはD^Nの24列目のうち青木くんがアクセスする時間に対応する行の要素の和です．

[midri1784 @midri1784]

京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)参加．7AC0WAでした． #AtCoder #ABC271
A: %02X
B: a[s[k]-1][t[k]-1] "求めてください"と問題文にかかれていたので何か計算が必要なのかと思い戸惑いました．

[midri1784 @midri1784]

F: 半分全列挙．(1,1)から(i,N-i+1)に行くときのXORの値と，(N,N)から(i,N-i+1)に行くときのXORの値を全部列挙して（それぞれのXORの値の総数は2^Nなので十分間に合います），XORがA[i][N-i-1]と一致するようなペアの個数を求めればよいです．