2022年4月11日
別に俺の中で流行っているわけではない。
貼ろうとした曲が貼れなかったため、おすすめみたいな漢字なところに出てきた曲を貼っておいた。
・。・
今週はいろんなことがありました。
月曜日
浜松にいた。 火曜日・水曜日に出かけることがわかっていたので、研究室に置き手紙をした。
— にぼし (@niboshi_wakai) April 4, 2022
火曜日
名古屋に行った。
というのも面接をするため。 企業の人にうなぎを食べさせてもらった。
社長は1800円の飯なのに俺は3000円だった。
内定ください。
ちなみに、うなぎは美味しいけどあまり美味しくなかった(こら) ちょっとだけ硬い部分があったので気になった。
水曜日
**に行った。
いい感じ
木曜日
ゼミ
金曜日
ゼミ
土曜日
ARCコンテスト ApeXをちょっとした
日曜日
さわやかハンバーグ。 ABCコンテスト
競プロの話
くそ雑
ARC138 A-Lerger Score
[添字を持った配列、優先度付きキュー、だんだん選べるものが増えていくタイプ,ソート]
スコアをS+1にすると誤読していた。 1点以上上げれば良いのだから、Aにある要素を一つだけそれより大きいものに変えてやれば良い。
Aの配列K個と、それより後ろの配列N-K個を別で考えてあげる。 Aの要素を1個ずつ、全部でK回見てやるんだけど、それぞれについて、N-K個のうち一番左にあるものと位置をっ交換してやるのがベスト。 そのようなのは、AのK個とN-K個をそれぞれ降順ソートしてやればキューを使ってうまい具合にゲットすることが出来る。
ARC138 B- 01 Generation
[0と1からなる数列の構築、構築、操作を逆に考える] 操作を逆に考えると、ヤル操作は、後ろの0を取るか、前の0を取ってFlipかの2通り。
後ろの0を取るのを優先してやって、空の文字列にできれば勝ち
ARC138 D-Differ by K bits
[XORの基底?] なんか頑張った気がするけど難しかった。よう復習。
ABC247 C- 1 2 1 3 1 2 1
[再帰、butilin_ctz, popcount]
naoyaさんのGCCのビルトイン関数メモが参考になりそう。
適当な再帰関数を書いてあげると通る。
f(n) = f(n-1) + n + f(n-1) f(1) = 1
後はなんか、頑張る
ABC247 D- Cylinder
[DはdequeueのD,何が何個あるかが大事]
5を5個追加ってとき、5,5,5,5,5って追加するなじゃなくて、(5,5)を追加する。 取り出すときは、(5,5)なら5個あるんだな。っていって、じゃ、3個だけもらいますね。みたいな感じ。 3個だけもらったら、2個は返して上げないといけない
ABC247 E- Max Min
[セグ木?うるせえよ。DP、状態を持つDP]
dp[i][mi][ji][ti]:=a[i]までをみたとき・最小Yである(1)/でない(0)・最大がXにである/でない・a[i]を取るなら1,取らないなら0
こんな感じ。X未満の値は採用しないし、Yより大きい値は採用しない。ti=1に遷移する。
こんな感じでヤルと、配列のサイズはN * 2 * 2 * 2なので間に合う
ABC247 F- Cards
[Lucas数、連続した2個のうち1個は取るやつ、リュカ数]
類題があった気がするけど忘れた。ブログを書こうね。
見たことがある感じ、カードの表裏は辺を貼るみたいなの典型なのかな?
UnionFindでくっつけて、みたいな感じなところは直感で出来たんだけど、島のサイズに対する答えの求め方がわからなかった。でもそれがLucas数ってやつになるらしい
注意点としては例えば5つに対して取る取らないを決める。ただし、連続して2回取らないをしちゃだめってトキ
xoxoxはNGです。みたいな感じな注意がある。でもそれもリュカ数で数えられちゃうらしい。すごい。