噴飯ちゃん

UnityとBlenderとVRとAtCoderにちょっときょうみがある存在

[噴飯ちゃん @FunPan_chan]

B：色々場合分けして、ax + by = cの解が分かれば良さそうに思えた。(x > 0 かつy > 0)でxを最大化できれば解けそうだと思ってる。拡張ユークリッドの互除法？の記事をずっと読んでいたものの、あまり理解できず・・・

[噴飯ちゃん @FunPan_chan]

ARC139は1完でした
A：
t[i-1] > t[i]なら、a[i] = a[i-1] + 1^t[i]
t[i-1] == t[i]なら、 a[i] = a[i-1] + 1^(t[i]+1)
t[i-1] < t[i]の時が難しい。
a[i-1]を2進数で左から見ていき、t[i]個の0が獲得できるまで+(1^x)していく。t[i]個より多く0が並んだら、+(1^t[i])してt[i]個目を1にする。

[噴飯ちゃん @FunPan_chan]

ARC138は2完でした。
A：前半部のある数字とそれより大きい後半部の数字をそれぞれk-1番目とk番目まで移動させてswapさせれば良さそう。それぞれsortしてから二重ループにならないようにいい感じにやる。

B：Aが{0}にできるか逆算する。

どちらもペナルティ貰ってから抜け穴に気付きました。

[噴飯ちゃん @FunPan_chan]

ABC241は3完でした。
A：言われたとおりにやる。
B：map
C：斜めには2種類ある。
D：すべて追加してから各クエリを処理した。二分探索を使ったものの、k番目を探す操作が重くてTLE

[噴飯ちゃん @FunPan_chan]

ARC135は1完でした
A：最終的に2か3になるまで分ける。同じ数はmapでまとめると計算量が落とせる。
B：全く脳味噌がうごかない。
C：行う操作は0回か1回でいい。1回の時、全ての数字でXORを取って全探索する。2進数の各桁の出現数をメモしておくと反転の操作は(n-出現数）でできる。

[噴飯ちゃん @FunPan_chan]

ABC238はABDの3完でした。
A：n > 2*log2(n) 　logも避けた方が良いのかな。式変形は毎回よくわからない。
B：(現在地＋A[i])%360 でメモしていく。ムズイ。
C：解けてないので考えます。
D：dif = s-a*2と置いて、dif >= 0 && (dif & a == 0) 。2進数を手で描いて分かりました。

[噴飯ちゃん @FunPan_chan]

ABC237は4完でした。
C：両端のaを消去してから回文判定。先頭の消したaの数が多い場合はNo(2敗）。
D：各数字の左隣と右隣の数を示すpairの配列を用意して、丁寧に更新していく。答えの配列はdequeで作る。
E：ダイクストラ

Eの提出が間に合いませんでしたが、解けたので気分がいいです。

[噴飯ちゃん @FunPan_chan]

ABC236は3完でした。
C：set
D：重複省いた選び方は16!/(2!*8*8!)≒10^7くらいだったので、通るかと思ってDFSを書きましたがTLEでした。vectorを使って無駄なく選ぶ実装ができていなかったかなぁ。setだとイテレータとかがちょっとﾑｽﾞｲ...
解説みます

[噴飯ちゃん @FunPan_chan]

ABC235は3完でした。
C：mapにkeyが出た番目を配列として保持する。
D：なんも分からんです。全通り試そうとするとサンプルケース4が計算量重くて通りませんでした。

[噴飯ちゃん @FunPan_chan]

ABC233は4完でした。
B：文字列を3つに分割していじった。
C：一段ごとにmapで考えられる積をメモしていった。計算量の計算苦手だ・・
D：累積和の配列sumを作る。sum[i]-sum[?] == k (?はi未満）があればその数だけ足していく。

[噴飯ちゃん @FunPan_chan]

ABC231は4完でした。
A：double型でx/100
B：map
C：二分探索
D：隣り合う数同士を辺で繋げていく。１つのノードから出る辺の数が3本を超えるか、閉路ができたらアウト

[噴飯ちゃん @FunPan_chan]

ARC130は2完でした。
A：連続する同じアルファベットから2つ選ぶ組み合わせを足してく。
B：後ろのクエリから

[噴飯ちゃん @FunPan_chan]

ABC228は4完でした。
A：for文を使ってシミュレーションしました。鬼ムズで心が...
B：while文で辿りました。
C：pairの配列を降順でsortする。k番目の人の得点-300以上ならYes。
D：t==1の時に計算量が重そう。現在-1を要素に持つ番目だけsetに保持してsetの二分探索をするといいかんじになる。

[噴飯ちゃん @FunPan_chan]

ABC227は3完でした。
A：(a-2+k)%n+1　難しかった。
B：三重ループ　難しかった。
C：a,bで二重ループして条件を満たすcの個数の和を求める。for文の中の条件式が難しかったり、cを二分探索で求めたりして計算量が落ちなくてめちゃめちゃ苦戦しました。(普通にn/(a*b)で求められる。）

[噴飯ちゃん @FunPan_chan]

E：手で沢山描いて、各集合で頂点の数と辺の数が一致することが条件だと思った。これはUnion_Findを使った。
条件を満たしたら2^集合の数が答え。(順と逆順の2通り）
初めてEまで通せたので嬉し～～です。

[噴飯ちゃん @FunPan_chan]

ABC226は5完(!)でした。
A：後ろから4番目で必ず小数点にアクセスできる。
C：難しかった。queueを使って後ろから処理。BFSみたいなかんじ。
D：魔法(a,b)を最大公約数で割って管理する。

[噴飯ちゃん @FunPan_chan]

ABC225は4完でした。
C:余りからj、商+1からiが分かる。余りが0の時にj=7,i=商になることになかなか気が付かなかった。
D:特に工夫しないで変数child,parentを持つ構造体を作った。制約を見ると優しい。出力する配列はdequeで。

[噴飯ちゃん @FunPan_chan]

ABC223は3完でした。
B：2つ繋げて全探索。計算量は間に合う。
C：めちゃめちゃ苦戦した。各点において右端からかかる時間と左端からかかる時間を求めて大小が入れ替わる点を探した。

[噴飯ちゃん @FunPan_chan]

ARC128は2完でした。
A：要するに単調増加する連続部分列と単調減少する連続部分列が交互に現れると考えてそれぞれの最後のiで交換する。
B：どれか2つをおんなじ数にできればいい。差が3の倍数のペアがあれば後は回数をいい感じに計算する（苦戦した）。なければ－1。

[噴飯ちゃん @FunPan_chan]

ABC222は4完でした。
C：制約が緩いので問題文の通りに実装した。C++なら｛-1*(勝利数)、何番目の人｝のpairの配列でsortしたらいい感じになる。
D：dp。重ね塗りしていく感じ。各iについてa[i]～b[i]の範囲を考える。例えばi = 0 の時、a[i]以上の数を+1,a[i]+1以上の...b[i]以上の数を+1する。