西懸

農家やったり開発したり/AtCoder 水黄/PAST上級/FE,AP,SC(未登録)/将棋ウォーズ(四段)/ポケモンチャンピオンズはじめました
@kiyonematsunaga

[西懸 @nishigake]

凡人が約5年かけて青コーダーになった話
https://t.co/zOXQE2bpGZ

人もすなる色変記事というものを書きました

[西懸 @nishigake]

ABCDE遅め5完
体調不良で途中トイレ行ったのを踏まえてもEが遅い

[西懸 @nishigake]

ABC462 47:36+1ペナ5完
AB: はい
C: 何故かSortedSetに突っ込んでbisectしたけど単にmaxでいい（典型）
D: 一目imos
→入退室を管理だと駄目そう
→犯行可否をimosすればいい
E: 2回移動ごとに偶奇が戻る（自明）
→min(2*A,2*B)<=A+Bなので斜めでok
→ジグザクで実質縦横移動が可能(3*Aが漏れて1ペナ)

[西懸 @nishigake]

長さH,W想定のセグ木（prodで閾値指定ができないので棄却）→SortedSet→SortedDict
の順に着想したけど結局クエリ番号がキーにしたし普通に考えて長さQのセグ木2個でいい（遅い）

F: 激遅5完≒ABCE4完と判断してDに戻らずやったけど解けず

[西懸 @nishigake]

ABC461、45minABCE4完
AB: やる
C: SortedList使った
D: 2秒でニ次元累積和が浮かぶ
→前計算後、ループしながらcounts[H*W]で個数管理しても右側がヒットするし面倒だなこれ。。。
→列ごとに個数持つのは500^3で無理(Python並感想)
で飛ばしたんだけど、解説チラ見したら想定解500^3で😡😡😡

[西懸 @nishigake]

E: シミュレートすることを考えると、
まだ塗ったことない行or列の場合は個数が明確なので普通に更新
過去に塗ったことある場合は「塗った時点より後に上書きされた箇所を再度上書き」
なので、二分探索できて高速に更新できる何かしらを使えば良い。SortedDict初めて使った気がする

[西懸 @nishigake]

昨年同時期にキオクシアを触っていたこととを鑑みると途端に渋く感じるというか、1e6のオーダーでパチャパチャしとくくらいならあのときガチホしておけばという気分にならなくもないけど、まあ未だ過熱してるなんて全然予想してなかったしなあ

[西懸 @nishigake]

雑に利確した
これがAtCoder投資法ですか？

[西懸 @nishigake]

圃場内に見慣れない虫がいたけど灌水の片付けしてる間に見失った

遠目には細長くて尻尾がないタイコウチみたいな胴長のシルエット（大きさは数cm）で、ノロノロ鉄パイプの上を歩いてたけど何やったんやろ

[西懸 @nishigake]

去年主戦場だったSaaS系は死んでるし中東情勢よくわからんしで個別株だいぶ放置しており今年はプラマイゼロ〜保有のSaaS分で微減も覚悟してたけど、フィックスターズ株だけで全てが帳消しになりそう

[西懸 @nishigake]

concat(x, y) === x+y (mod M)

でyが寄与しないの、言われてみれば自明すぎる

[西懸 @nishigake]

D:
・`#`が疎な条件で実験をすると最初にある`#`からの距離の偶奇で縞模様に広がりそうなことがわかる
・密なときによくわからんことになったので、2回くらい愚直にシミュレートして`#`の塊を処分しておく
・距離を出すために多始点bfs

についてクソキモ実装を行う

[西懸 @nishigake]

ABC460 50分4完+1ペナ
全人類がE通してて渋い（数弱）

A: やるだけ
B: B問題に12分かかる寒色がいるらしい（数弱）
結局ggった関数をガチャガチャした
C: 貪欲だけどindexバグらせマンなのでSortedListで突っ込んで実際にpopした

[西懸 @nishigake]

B問題、フリック入力なのか。たしかに・・・
（コンテスト中はクソ問題やんけと思いながら左手で数字を、右手で `,` をリズム良く打ち込んでいた）

[西懸 @nishigake]

E: 枝から計算しつつ余った飴を親に移すだけ
解法自体はわりとすぐ思いついたけど、制約に合わせてnCrをループに書き直した際に普通の逆元と間違えて
ans *= inv_fact[i]
をforの内側に書いてしまいタイムロス

F: 初手天才やめてくれ
三分探索とかできないかな～とかガチャガチャやってたけど解けず

[西懸 @nishigake]

ABC459 56:24の5完

AB: やるだけ
C: O(N+Q)がパッと思いつかず、値をSortedListに放り込んでbisect_rightで個数数えた
D: 直感的には数が多いやつから貪欲でよさげ
Pythonの2.6e7はそこそこ怖いのでここでもSortedListを持ち出したけど意味があるのかは不明

[西懸 @nishigake]

断腸の思いでABCを優先（3Dライブ）

[西懸 @nishigake]

ABC458 9min4完
ガッツリ農作業をしていたので疲労のせいにしておく（カス）

ABCD: やるだけ
E: 再帰のdpをベースに対称性から1,3を入れ替えたりする方針が見えたけど、結局状態数が(1e6)^2なんだよなーとなっていた
Fもチラチラ見たりしつつ両方駄目（最近こんなんばっかやんけ）

[西懸 @nishigake]

F: なんかGの方が解かれてるので一旦飛ばしたけど、Gが普通に無理で戻ってきた

dpの気配はしてたけど全然時間が無いのでD=[1,1,1...]で雑に実験してOEISをしてみたが、A054091から進展せず（それはそう）

[西懸 @nishigake]

ABC457 冷えてはないけどペナ大量5完で水パフォ
青上位は狙えたので勿体ない

ABCD: やるだけ
E:
・L_i = [(r1,i1),(r2,i2),...]
・R_i = [(l1,i1),(l2,i2),...]
に対してL[S]、R[T]から二分探索で境界を探る方針がすぐ思いつくが、(S,T)+内側 みたいなペアがヒットしないので別途セグ木も用意

[西懸 @nishigake]

重複や境界値管理が怖いので候補を数個setに入れて雑にループしてチェックでokなんだけど、二分探索前のソートで

for i in range(N + 1):
L[i].sort()
R[i].sort()

をrange(N)って書いてたのに気づかず候補やセグ木の境界とかを弄りまくって無限にペナってしまった