E [1,2],[1,3],...,[1,n]を聞く。全部0ならIMPOSSIBLE。一番はじめに1と返ってきたものから、左端の様子が分かる。
— titia (@titia_til) November 17, 2024
F 答え二分探索。判定は、どの範囲に自分の位置があれば良いか? がn個でてくるので、平面走査みたいにやる。
G 素因数ごとに包除するDP。2^素因数の個数の計算量は必要な気がした。
2024年11月19日火曜日
Codeforces Round 988 (Div. 3)
2024年11月18日月曜日
AtCoder Regular Contest 187
AtCoder Regular Contest 187 AB両方を見てBを中心に考えていたが解けず、その後なんとかAをAC。
— titia (@titia_til) November 17, 2024
A N>=3ならYesだと気付くのが重要。
B 段々になるので、段を数えていけばいいはず→数えられず終了。
B - Sum of CC
C - 1 Loop Bubble Sort
2024年11月17日日曜日
AtCoder Beginner Contest 380
G K個の部分、その前、その後の三つに分ける。K個の部分の転倒数は平均でK*(K-1)/2/2。ずらしたときどうなるかはBITで差分計算できると思う(が、サンプルが合わなかった)。
— titia (@titia_til) November 16, 2024
G - Another Shuffle Window
2024年11月14日木曜日
Codeforces Round 971 (Div. 4)
F c回シフトしたときの[l,r]の和を計算できるようにしておく。あとは、l,rをmod n で0になるところまで持っていき、周回数*SUMを足す。
— titia (@titia_til) September 3, 2024
G1 B[i]=A[i]-iとしたとき、[l,r]での最頻値の出現回数。検索したらMoと言われて、https://t.co/5mOOOLsyNq からお借りしてしまったけど、別の解き方ありそう。
G1. Yunli's Subarray Queries (easy version)
G2. Yunli's Subarray Queries (hard version)
2024年11月12日火曜日
Refact.ai Match 1 (Codeforces Round 985)
D まずできるだけ辺を消す。次数2以上の頂点があれば、それを構成する三角形を消し、辺を減らす。すると森になるのでつないでいく。
— titia (@titia_til) November 9, 2024
次数2以上の頂点xに一回辺を減らす操作をしたら、そこはもう操作しなくていいと勘違いしてはまった。ランダムテストでなんとか気付けて良かった。
F. Palindrome Everywhere
2024年11月11日月曜日
Codeforces Round 986 (Div. 2)
D 頭がこんがらがるけど、ある数字を取ったときq,j,kのどの数字まで使えるか遷移を考えれば良い。SortedSetをお借りしたけど、dequeで良かったかも?
— titia (@titia_til) November 10, 2024
E 一本道の場合、1,n-1/n,n-2/n,...,1/n,0となることを利用する。一番近い葉までの距離が分かればいけると思ったけど、実装間に合わなかった。
E. Alice's Adventures in the Rabbit Hole
THIRD プログラミングコンテスト2024(AtCoder Heuristic Contest 039)
・盤面を40*40に圧縮
— titia (@titia_til) November 10, 2024
・良さそうな長方形を一つ探す。(初期状態)
・そこから、長さの条件を満たしたまま、一マス加えたり一マス減らしたりする山登り。
三番目の実装(線を伸ばしたり縮めたり)は、https://t.co/w0nbkNdTBz
でやったことを流用した。別の方法を色々検討したんだけど思いつかず。
トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)
F 自分より大きい次のindexを探すのはO(N)でできる。それを使ってDP。Cと違って制約が優しく、同じ高さのビルがない。
— titia (@titia_til) November 9, 2024
G 一行ずつ3^WをもってDPを実装したがTLE。3^W全て持たなくても良いことは気付いていたけど、実装する時間がなかった。
G - Count Grid 3-coloring
2024年11月9日土曜日
yukicoder contest 452
No.2953 Maximum Right Triangle
No.2954 Calculation of Exponentiation
No.2955 Pizza Delivery Plan
No.2956 Substitute with Average
2024年11月5日火曜日
yukicoder contest 261
D 各文字により点数がどれだけ加算されるか、を慎重に計算。そのために、i文字までで、各文字で終わる部分列の個数を持っておく。
— titia (@titia_til) August 14, 2020
No.1172 Add Recursive Sequence
2024年11月4日月曜日
Codeforces Round 984 (Div. 3)
G. Library of Magic
2024年10月31日木曜日
Codeforces Global Round 27
Codeforces Global Round 27 DもEも解けなくて、過去最悪くらい酷い出来。ARCは調子良さそうだったんだけど……。
— titia (@titia_til) October 27, 2024
C 上位bitから順に処理。
D dequeでいいようにできそう→WA。後ろにA[i]をそのままおくか、今までの2達を全部もってくるかくらいしかない気がしたけどWA。
E 適当に探索してWA。
D. Yet Another Real Number Problem
E. Monster
2024年10月30日水曜日
Educational Codeforces Round 171 (Rated for Div. 2)
Educational Codeforces Round 171 (Rated for Div. 2) Dまで時間がかかり、Eが分からない。
— titia (@titia_til) October 28, 2024
A 悩んで分からないまま投げた。正方形の対角線。
B nを偶奇に分け、奇数のときは左右から累積max
C 後ろから見て、0でindexが大きいもの→1でindexが小さいものを優先的にペアにする。
D 累積和で頑張る。
E. Best Subsequence
2024年10月29日火曜日
yukicoder contest 449
No.2914 正閉路検出
No.2915 辺更新価値最大化
No.2916 累進コスト最小化
2024年10月27日日曜日
yukicoder contest 293
No.1492 01文字列と転倒
トヨタシステムズプログラミングコンテスト2024(AtCoder Beginner Contest 377)
トヨタシステムズプログラミングコンテスト2024(AtCoder Beginner Contest 377) Fが解けず。
— titia (@titia_til) October 26, 2024
C 置けないマスをsetで。
D 平面走査っぽい考え方。
E 一回操作すると、通常の操作(i→P[i])の2ステップ分動くとみなせる。
G Trie木
F - Avoid Queen Attack
2024年10月21日月曜日
yukicoder contest 450
No.2940 Sigma Sigma Div Floor Problem
No.2942 Sigma Music Game Level Problem
No.2943 Sigma String of String Score Problem
No.2944 Sigma Partition Problem
2024年10月20日日曜日
AtCoder Beginner Contest 376(Promotion of AtCoder Career Design DAY)
F DP[次の位置が決まっていない方の位置]=最小コストとする。片方しか動かさない場合は、Bと同じところから、左右に+1していけば良い(ただし、別のものの位置は追い越せない)。両方動かす場合は、ギリギリまで動かす一個だけもてば良い。
— titia (@titia_til) October 19, 2024
……で良いと思ったが22/37ACで終了。
F - Hands on Ring (Hard)
G - Treasure Hunting
Codeforces Round 979 (Div. 2)
E. MEXimize the Score
2024年10月17日木曜日
AtCoder Regular Contest 185
B A[i]が今までのMINより小さいなら、A[i]をMINまで増やし、そこでとっておく値(POと呼ぶ)は後で使い切りたい。A[i]がMINより大きいときは、まず使っていないPOを使い(その次にPO2を使い)、足りなければMINを上昇させて対応。そこで余った値(PO2)は適宜使う。最終的にPO=0にときYes
— titia (@titia_til) October 13, 2024
C - Sum of Three Integers
D - Random Walk on Tree
E - Adjacent GCD
2024年10月14日月曜日
パナソニックグループ プログラミングコンテスト2024(AtCoder Beginner Contest 375)
F クエリを後ろから見て、ダイクストラ風に。(x,y)を基準に、xから一歩進む or yから一歩進むを更新。
— titia (@titia_til) October 12, 2024
G スタートとゴールからダイクストラして必要な可能性がある辺を求めたら、あとは何度も歩かせてみたら良いんじゃないか? と思ったがWAが出るので何か間違っているよう。
E - 3 Team Division
G - Road Blocked 2
2024年10月11日金曜日
丸紅プログラミングコンテスト2024(AtCoder Regular Contest 183)
丸紅プログラミングコンテスト2024(AtCoder Regular Contest 183) AB二完。
— titia (@titia_til) August 25, 2024
A 真ん中の数字→一つ小さい数字を一つ→大きい数字から埋める。
B 実験したら、K>=2なら同じ数字がKの範囲にあるといけると分かった。BにAにない数字が登場している場合や、A=Bの場合を忘れてペナ。
C - Not Argmax
2024年10月7日月曜日
キーエンスプログラミングコンテスト2024(AtCoder Beginner Contest 374)
F DP[ind][time]をあるT[i]までをtime日に出荷し終えたときの不満度、としてダイクストラっぽく計算したら4TLE→ChatGPTでRUSTに直してもらいAC。
— titia (@titia_til) October 5, 2024
G SCCしてUnion-findでごちゃごちゃやったらサンプルは合ったが半分くらいWA。
G - Only One Product Name
2024年10月4日金曜日
Codeforces Round 974 (Div. 3)
F 木DP。詰めるのに凄い時間がかかった。子たちのうち、使った場合の値-使わない場合の値でソートし、メリットが高い順に何個使えばベストかを試す。
— titia (@titia_til) September 21, 2024
H Aをrandomな数におきかえ、xorのセグ木で判定した。でも今考えたら累積xorで良いね。
G. Milky Days
2024年9月30日月曜日
Codeforces Round 976 (Div. 2) and Divide By Zero 9.0
D. Connect the Dots
AtCoder Grand Contest 068
AtCoder Grand Contest 068 0完
— titia (@titia_til) September 29, 2024
ずっとBを考えていたが、愚直っぽい構築が上手くいく気がしていて、それが勘違いだと終了間際に気付いた。何も分からず終了。
B - 01 Graph Construction
2024年9月29日日曜日
AtCoder Beginner Contest 373
F CHTを使いそうだと思ったが分からず。ペナルティも含めて(v,w)を並べて、v/wが大きい順に並べた上位10000個に含まれるもの(それを1個でオーバーするなら1個は持つ)だけ使ったらACした。
— titia (@titia_til) September 28, 2024
G - No Cross Matching
2024年9月28日土曜日
Codeforces Round 973 (Div. 2)
D. Minimize the Difference
E. Prefix GCD
yukicoder contest 448
No.2902 ZERO!!
2024年9月26日木曜日
AtCoder Regular Contest 184
AtCoder Regular Contest 184 Aしか解けず。
— titia (@titia_til) September 22, 2024
A 二枚ずつに分ける→一致しているものをマージしていき、12個になったら正しいコイン、他はダメなコイン! という操作を続ける。最後に、正しいコインと分かっているものを使い、最初に一致しなかったものをチェック。
B - 123 Set
C - Mountain and Valley Folds
2024年9月25日水曜日
日立ヴァンタラプログラミングコンテスト2024(AtCoder Beginner Contest 368)
G セグ木二本使う。Bについてはmaxを、Aについては和をもつ。Bで1が連続するようなら、セグ木上の二分探索で次の1でない値を探し、そこまでのAの和を加算。
— titia (@titia_til) August 24, 2024
E - Train Delay
2024年9月21日土曜日
yukicoder contest 447 オムニバス
No.2896 Monotonic Prime Factors
No.2897 2集合間距離
2024年9月18日水曜日
RECRUIT 日本橋ハーフマラソン 2024夏(AtCoder Heuristic Contest 036)
RECRUIT 日本橋ハーフマラソン 2024夏(AtCoder Heuristic Contest 036)
— titia (@titia_til) September 2, 2024
最後まで提出を迷っていたのですが、明らかな点数の改善は見込めなそうなので提出を見送って終了。暫定71位。19:01にその提出を出したところ、元の点数53389点→53311点でした。WAじゃないけど、あまり変わらなかった。
前半四日くらい
最終日まで
最終日
気になっていたこと
2024年9月17日火曜日
第11回 Asprova プログラミングコンテスト(AtCoder Heuristic Contest 037)
第11回 Asprova プログラミングコンテスト(AtCoder Heuristic Contest 037)141位
— titia (@titia_til) September 15, 2024
x+yが大きい方から順に、
・z<=x,w<=yなる(z,w)から(x,y)を作る
・minx=min(x,z),miny=(y,w)とし、(minx,miny)から(x,y)と(z,w)を作り(minx,miny)を挿入
を全ての(z,w)について調べ、コストが一番低いものを選択。
AtCoder Beginner Contest 371
AtCoder Beginner Contest 371 Eまで。最初に手をつけたCに20分かかった。
— titia (@titia_til) September 14, 2024
A 高い方に+1低い方に-1して、合計が0のもの。
B どの家で太郎とつけたか記録しておく。
C 対応する点をどうするか全部試す。
D 座標圧縮して累積和
E ある数字をこの前つかったのがいつだったかを覚えていれば計算できる。
F - Takahashi in Narrow Road
G - Lexicographically Smallest Permutation
2024年9月14日土曜日
yukicoder contest 446
No.2891 Mint
2024年9月13日金曜日
Codeforces Round 958 (Div. 2)
Codeforces Round 958 (Div. 2) Dまで。
— titia (@titia_til) July 15, 2024
A k-1個ずつ増やせる
B 複数の0を一つに圧縮した後、1の個数>0の個数
C 立っているbit一個を削ったものたちで構成
D 使う回数の最大値が分かれば木DPできる。6回だとWA、大きくするとTLE→20回にしてChatGPTにC++に直してもらったらAC。
E. Range Minimum Sum
2024年9月9日月曜日
トヨタ自動車プログラミングコンテスト2024#9(AtCoder Beginner Contest 370)
E 累積和Sを取り、S[i+K]以外の箇所に現在の場合の数を加算。累積和を使って加算する個数は処理できる。減産についても累積和を考え、dict Dを使ってD[i+K]-=(現在の場合の数)のようにする。
— titia (@titia_til) September 7, 2024
F - Cake Division
2024年9月8日日曜日
yukicoder contest 444
No.2871 Universal Serial Bus
No.2872 Depth of the Parentheses
No.2873 Kendall's Tau
2024年9月7日土曜日
yukicoder contest 443
No.2864 String of yuusaan
No.2865 Base 10 Subsets 2
No.2866 yuusaan's Knapsack
No.2867 NOT FOUND 404 Again
2024年9月1日日曜日
AtCoder Beginner Contest 369
E クエリごとにbit DPしながらダイクストラでいいと勘違い。予め全頂点間の移動時間を前計算して、橋の渡り方を全探索すると間に合う。
— titia (@titia_til) August 31, 2024
F セグ木DPを復元する感じかと思ったが、上手くいかないまま終了。
F - Gather Coins
G - As far as possible
2024年8月25日日曜日
yukicoder contest 441
No.2844 Birthday Party Decoration
No.2845 Birthday Pattern in Two Different Calendars
No.2846 Birthday Cake
2024年8月20日火曜日
AtCoder Grand Contest 067
AtCoder Grand Contest 067 Aしか解けず。
— titia (@titia_til) August 18, 2024
A 二つのクリークで、全ての頂点をどちらかに入れられるものを取れれば良さそう。計算量が自信なかったけどそれっぽいことを書いたらAC。
C indexの素数倍それぞれについて、Aにおいて何倍になるか割り当てる……みたいなことを考えていたがまとまらない。
C - Divisibility Homomorphism
2024年8月18日日曜日
EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2)
F1 pを素数として、(p-1,p)にはたどりつける。素数と素数の区間は200くらいなので、そこを基準にDFSすれば間に合う。PyPyでsetを使ってdfsしたため結構時間制限が危ない。
— titia (@titia_til) August 11, 2024
F2. Court Blue (Hard Version)
2024年8月17日土曜日
Educational Codeforces Round 169 (Rated for Div. 2)
D xとyでかぶった色がない場合、indexの近い別の色のものを二分探索で探し、そこを経由した行き方が答え。
— titia (@titia_til) August 15, 2024
E 実験したらGrundy数がエラトステネスの篩で求まると分かった。
F. Make a Palindrome
2024年8月15日木曜日
Codeforces Round 966 (Div. 3)
F (a,b)に対して、コストいくつでスコアがいくつ取れるかを調べた上でDP。スコアは高々kまで調べれば良い。
— titia (@titia_til) August 13, 2024
G 中継地点全探索とか色々考えてしまったが、後ろからダイクストラすれば一発。
H SortedSetでAを管理し、セグ木で間の値を管理すれば良いと思ったがWA on test 2が取れず。
C. Numeric String Template
H. Ksyusha and the Loaded Set
2024年8月12日月曜日
AtCoder Beginner Contest 366
AtCoder Beginner Contest 366 EもFも解けない失敗。
— titia (@titia_til) August 10, 2024
A N/2と比較
C Counter
D 三次元累積和
E 最初45度回転したら長方形領域になると勘違い→x,y独立に計算できると気付きxを全探索する方針に変更したが答が合わない。
F 何かでソートすることを疑ったが分からずビームサーチを書いてWA
E - Manhattan Multifocal Ellipse
F - Maximum Composition
2024年8月10日土曜日
yukicoder contest 440
No.2836 Comment Out
No.2838 Diagonals
2024年8月8日木曜日
Codeforces Round 964 (Div. 4)
Codeforces Round 964 (Div. 4) 最近のDiv.4は難しいのが多かった気がする。Div.4は今回くらいの難易度で良いのでは? しかし、CやGでペナ出したのは良くない。
— titia (@titia_til) August 6, 2024
D "?"には貪欲にTの文字を入れていく。
E まず最小の数を0にする。
F 0を何個選べば良いか全探索
G 三分探索
2024年8月5日月曜日
AtCoder Regular Contest 181
AtCoder Regular Contest 181 AC二完でした。
— titia (@titia_til) August 4, 2024
A 三回では可能。一回でできるかはBITとか使ってチェック。二回でできないのは、N,...,1のとき。
B Tの長さは分かったが、Tの長さが大きいとき処理できなかった。
C P,Qの逆順列を取り、その和がNより大きいかで1を入れるか0を入れるか決める。
B - Annoying String Problem
D - Prefix Bubble Sort
2024年8月3日土曜日
yukicoder contest 439
No.2828 Remainder Game
No.2829 GCD Divination
2024年8月2日金曜日
日本レジストリサービス(JPRS)プログラミングコンテスト2024#2(AtCoder Beginner Contest 364)
F costが小さい方から見る。[L,R,C]が来たら、その後は、Lの後Rまで飛ばして良い。RIGHT[x]を管理し、RIGHT[L]=max(RIGHT[L],R)と更新していく。
— titia (@titia_til) July 27, 2024
G ダイクストラで全頂点から全頂点への最短距離を求めて色々するかと思ったが、全然違ったらしい。
G - Last Major City
Educational Codeforces Round 168 (Rated for Div. 2)
E どのindexでレベルアップするかをkごとに記録。SortedSetを使ったらTLEしてしまったけれど、SortedSetを使ってACしている人もいるようなので、実装が下手。まあ、調和級数のlogとSortedSetのルートがつくので計算量的にも結構厳しそうではあるんだよね。
— titia (@titia_til) July 30, 2024
E. Level Up
2024年7月31日水曜日
AtCoder Beginner Contest 322
AtCoder Beginner Contest 322 Eまで。Fの方針は分かっても実装が間に合わない。
— titia (@titia_til) September 30, 2023
C 尺取り。
D 実装がんばる。
E DP。Pを5で固定で解いてしまい2ペナ。
F 左側の連続個数, 右側の連続個数,連続する0の最大長さ,連続する1の最大長さを持てば遅延セグ木/平方分割でいけるとは思ったが実装終わらず。
F - Vacation Query
2024年7月28日日曜日
Codeforces Round 962 (Div. 3)
(Eの続き)右からのindexの累積和を持っておいて、左から足していく。
— titia (@titia_til) July 26, 2024
F いくつの数字以上を使うかを二分探索→等差数列の和で計算し、余った個数を引く。
G https://t.co/JMooQptkIG これ知らないと難しいと思うんだけど、結構解かれているね。
2024年7月27日土曜日
yukicoder contest 438
No.2820 Non-Preferred IUPAC Nomenclature
2024年7月25日木曜日
Codeforces Round 961 (Div. 2)
Codeforces Round 961 (Div. 2) B2が分からず、D高速化できず。
— titia (@titia_til) July 23, 2024
A [n,n-1,n-1,...,2,2,1,1]の累積和。
B1 xとx+1を使う合計回数を全探索
B2 回数はm/xの周囲だけで良さそう→WA
C 前回の操作回数が30回を超えていたら、前回-30回は少なくとも行う、としたら通ったが誤差とか自信ない(logで処理)。
B2. Bouquet (Hard Version)
2024年7月23日火曜日
ユニークビジョンプログラミングコンテスト2024 夏(AtCoder Beginner Contest 359)
ユニークビジョンプログラミングコンテスト2024 夏(AtCoder Beginner Contest 359) Fまで。
— titia (@titia_til) June 22, 2024
C 斜めに移動してから横に移動
D bit DPなのはすぐ分かったが実装に苦戦。
E stackを使って、単調減少な板を残しておく。
F heapqを二個用意して受け渡す。
G - Sum of Tree Distance
2024年7月22日月曜日
AtCoder Beginner Contest 363
E heapqでAの最も小さいものを取っていく実装だとTLE。最初にソートし、水に面しているか? 水面以下の高さか? を別に管理してlogを外したらACした。
— titia (@titia_til) July 20, 2024
F 中央の数を全探索し残りをbit全探索する解法を終了6分後に書き終わったがTLEでした。
C - Avoid K Palindrome 2
F - Palindromic Expression
2024年7月20日土曜日
yukicoder contest 437 ('09 Contest 002 day2)
No.2812 Plus Minus Blackboard
No.2816 At Most Two Moves
Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)
E sizeだけ考えればOK。最上位ビットを大きい方から見ていき、最上位bitが同じものが二つあればそれ以下全て1にできる。一つなら、xor 最上位bitを加える。
— titia (@titia_til) July 18, 2024
F NPCが立っている分についての次数を考え、NPCが立っていないものを使って次数を偶数にできるか? が解けなかった。
F. Stardew Valley
G. Minecraft
2024年7月15日月曜日
yukicoder contest 436 ('09 Contest 002 day1)
No.2804 Fixer And Ratism
No.2805 Go to School
No.2806 Cornflake Man
No.2807 Have Another Go (Easy)
No.2809 Sort Query
2024年7月14日日曜日
トヨタ自動車プログラミングコンテスト2024#7(AtCoder Beginner Contest 362)
トヨタ自動車プログラミングコンテスト2024#7(AtCoder Beginner Contest 362) F飛ばして六完
— titia (@titia_til) July 13, 2024
C 最小からの差を考える。
D ダイクストラ。Cより簡単。
E (長さ、公差、次の数)を持ってDP
G aho-corasick。ライブラリを改造したりChatGPTにC++に直してもらったりしてたらたくさんの人に解かれていた
F - Perfect Matching on a Tree
G - Count Substring Query
2024年7月13日土曜日
Codeforces Round 957 (Div. 3)
E. Novice's Mistake
G. Ultra-Meow
2024年7月10日水曜日
Codeforces Round #956 (Div. 2) and ByteRace 2024
D. Swap Dilemma
E. I Love Balls
2024年6月24日月曜日
2024年6月19日水曜日
CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)
G Eより楽に感じた。最後はある場所にとどまり続けるのが最適。DPテーブルをたくさん更新した後、ずっとそこにいるときの値を計算。
— titia (@titia_til) June 15, 2024
F - Easiest Maze
2024年6月15日土曜日
yukicoder contest 433
No.2783 4-33 Easy
No.2784 繰り上がりなし十進和
No.2785 四乗足す四の末尾の0
2024年6月13日木曜日
Codeforces Round 952 (Div. 4)
G 9/k以下の数字しか使ってはダメ。等比数列の和。
— titia (@titia_til) June 11, 2024
H1 Union findして、各行・各列においたとき、どの連結成分が加わるかを見る。
H2 (x,y)を中心とする十字に置いたとき、何個プラスになるか? を連結成分ごとにimos法して求める。
H2. Maximize the Largest Component (Hard Version)
2024年6月9日日曜日
サントリープログラミングコンテスト2024(AtCoder Beginner Contest 357)
サントリープログラミングコンテスト2024(AtCoder Beginner Contest 357) Eまで。F遅延セグ木に乗るよね?→実装できずに終わる。ひどい……。(実装が下手なだけでなく、立式もおかしかった)
— titia (@titia_til) June 8, 2024
C 再帰で実装
D 等比数列の和の公式
E SCCしてごにょごにょ。
F - Two Sequence Queries
2024年6月7日金曜日
yukicoder contest 432
yukicoder contest 432
— titia (@titia_til) June 7, 2024
B 二分探索
C 大きい方から消費
E,F Counter
G 左右から、len(A[:i])!=len(set(A[:i]))となる場所を探して、その間
H SCCしてごにょごにょ。最初に人1の手に渡ったというのを読み落として30分以上惑っていた。
Codeforces Round 951 (Div. 2)
E (x+y,x-y)と座標変換して、各xについてのリストを作る。ある(x,y)について、x+kやx-kに二個k離れたものが[y-k,y+k]についてあれば良い。これは尺取りでできる。y座標についても同様にする。
— titia (@titia_til) June 6, 2024
……で良いと思っているけどどうだろうか。(最初WAを出したときはミスがあった)
E. Manhattan Triangle
2024年6月5日水曜日
Codeforces Round 950 (Div. 3)
E {sorted(A[i])}がsetとして一致。列についても一致。
— titia (@titia_til) June 3, 2024
F1 あるmまでのnの最大値を持つ。
F2 F1で1になったものそれぞれについて、使わなかった場合との差分を計算。その計算する箇所は、一つ前に1だった場所~一つ後に1だった場所の間だけで良いはず。
F2. Field Division (hard version)
G. Yasya and the Mysterious Tree
2024年6月3日月曜日
AtCoder Beginner Contest 356
AtCoder Beginner Contest 356 Eまで。F分からず困った。
— titia (@titia_til) June 1, 2024
C bit全探索
D 各桁ごとに
E 頑張ると調和級数の計算量へ帰着できる。
F 平方分割とかを疑っていたが分からず終了。
F - Distance Component Size Query
2024年6月1日土曜日
Educational Codeforces Round 166 (Rated for Div. 2)
D (で+1、)で-1とした配列をAとすると、A[l]=A[r]が必須。また、l~rでA[l]*2を超えるものがあってはダメ。セグ木二分探索の後、二分探索。
— titia (@titia_til) May 30, 2024
E (q+1)*(q+2)*...がどの数字をどこへでも置けるときの答えで、そこからいくつか削る方針で考えていた。
E. Splittable Permutations
F. Remove Bridges
yukicoder contest 431
No.2767 Add to Divide
No.2768 Password Crack
No.2770 Coupon Optimization
2024年5月31日金曜日
AtCoder Regular Contest 177
AtCoder Regular Contest 177 Cまで。
— titia (@titia_til) May 12, 2024
A 値段の高い硬貨を優先して使う。
B 右端から処理
C 赤・青両方に得ということはないので、二回BFSして和を取ればOK。
D 全く解けていない。連結成分ごとに分けて考えて良いと気付いたのが終了五分前くらいだった。全然ダメ。
D - Earthquakes
2024年5月28日火曜日
Codeforces Round 946 (Div. 3)
(D続き) これでNOの処理も上手くいくはず。
— titia (@titia_til) May 20, 2024
E DP
F 行の降順・昇順、列の降順・昇順にソートしたものをそれぞれ持ち、setで管理しながら貪欲に使う。
G. Money Buys Less Happiness Now
2024年5月26日日曜日
東京海上日動プログラミングコンテスト2024(AtCoder Beginner Contest 355)
E 最小手数を再帰で実装しようとして実装に失敗。
— titia (@titia_til) May 25, 2024
F ChatGPTに聞いたらLink cut treeを使えと言われたが、Link cut treeを使ったことがないので後まわしにした(のにEが解けなかった)。
E - Guess the Sum
F - MST Query
2024年5月18日土曜日
yukicoder contest 430
No.2758 RDQ
No.2759 Take Pictures, Elements?
No.2760 not fair position game
2024年5月14日火曜日
AtCoder Beginner Contest 353
G 「等差数列を加算するセグ木」とかMonotone Minimaとか考えて時間を食ったけど、SortedSetで山の先を管理すればOK。
— titia (@titia_til) May 11, 2024
F - Tile Distance
Kotlin Heroes: Episode 10
E kそれぞれの場合の最小のものを埋め込み、長さnまで伸ばした。
— titia (@titia_til) May 13, 2024
F 連続i個で下にいけるようにしたい→その右上と左下に置く。これは二項係数で計算できる。0の場合は全体から引いた。
H. Composite Spells
2024年5月13日月曜日
Codeforces Round 944 (Div. 4)
H. ±1
2024年5月7日火曜日
yukicoder contest 291
No.1478 Simple Sugoroku
No.1479 Matrix Eraser
Educational Codeforces Round 165 (Rated for Div. 2)
D heapqを二つ使う。一つ目のheapqにある要素で儲けを出すとし、その要素を無料で与えるとしたときの損失を入れておく。二つ目のheapqにはA[i]の値を入れる。一つ目のheapqから二つ目のheapqへ入れ、二つ目のheapqの要素を常にkにするようにして、答えを計算。
— titia (@titia_til) April 29, 2024
E. Unique Array
2024年5月5日日曜日
AtCoder Beginner Contest 352
AtCoder Beginner Contest 352 Eまで。
— titia (@titia_til) May 4, 2024
A X<Z<Y or Y<Z<X
B 尺取り
C B-aが一番大きいものを最後に。
D SortedSetをお借りしました。
E Cの小さい順に。
F 2-SATで解けそう! と実装し始めたが上手くいかず終了。あれ、2-SATで解けないの?
F - Estimate Order
G - Socks 3
2024年5月4日土曜日
Codeforces Round 942 (Div. 1)
Codeforces Round 942 (Div. 1) B2まで。
— titia (@titia_til) April 30, 2024
A 少ない数字から増やす。最小の個数+1まで使ったときの和-(n-1)
B1 bを固定すると、aはb*b-bからb*bごと
B2 a+b=cとするとcが平方数のk倍でa:b=i:c-iとなるようなiがあればOK。
C 増え方が等差数列という間違った考察をしていた。
C. Fenwick Tree
Codeforces Round 943 (Div. 3)
F 累積xorを取りこれをXORとする。l~rのxorが0ならOK。違うときは、間に、XOR[r]と同じもの、XOR[l-1]が含まれれば良い。
— titia (@titia_til) May 2, 2024
G1 Z algorithmした後二分探索
G2 x文字をLCPに持つものは何個取れるか? を全探索しても、次の場所を二分探索していけば、二分探索のlogと調和級数のlogの二つで済む。
2024年4月28日日曜日
AtCoder Regular Contest 176 (Sponsored by Mynavi)
AtCoder Regular Contest 176 (Sponsored by Mynavi) Cまで三完。
— titia (@titia_til) April 21, 2024
A (j-i)%NをM個選び斜めにおいていく。
B M=K+1の場合は別に計算。N<Mなら答えは2^N。そうでないとき、K=0に帰着。2^N%(2^M+1)は2^(N-M)%(2^M+1)と一致する。
C Cが小さい方から見て頑張って場合分け(ABより考え方は楽だと思った)
D - Swap Permutation
E - Max Vector
2024年4月25日木曜日
Educational Codeforces Round 163 (Rated for Div. 2)
Educational Codeforces Round 163 (Rated for Div. 2) Eまで。
— titia (@titia_til) March 15, 2024
A AAとBBを繰り返し。
B 今までの最大値を管理。
C DPというかDFSした。
D 幅hでh個連続で一致していれば、答えをhにできる。
E たとえば頂点5k=5なら 4 5 1 2 3とすればクリークにできる。この繰り返し。
F. Rare Coins
2024年4月23日火曜日
Codeforces Round 940 (Div. 2) and CodeCraft-23
D A[i]の最上位bitがbだとすると、l~i+1の累積xorでbが立っている/立っていない個数、i+1~rの累積xorでbが立っている/立っていない個数を調べて、l~rの累積xorではbが立っていないような個数を掛け算して求める。方針が立ってから、添え字とかで非常に苦労した。
— titia (@titia_til) April 21, 2024
E. Carousel of Combinations
2024年4月22日月曜日
AtCoder Beginner Contest 350(Promotion of AtCoderJobs)
AtCoder Beginner Contest 350(Promotion of AtCoderJobs)Fまで
— titia (@titia_til) April 20, 2024
A ABC000はない!
C Aの逆関数を用意して頑張る
D Union-findで、各連結成分に含まれるノード数xに対してx*(x-1)/2の総和からMを引いた。
E 期待値DP。
F 構文解析。再帰でreturnして文字をつなげていくとTLE。dfsっぽく直してAC。