問題ページ。 nagai1mojiretsu 公式解説では後ろからやっていますが、前から解いたので書いておきます。 計算量は公式解説より少し悪化しています。 解法 いままで出力した文字数を y とします（初期値は 0）。 下記のように、順にシミュレートしていきなが…

特に Advent Calendar は関係ない 12 月 13 日の記事です。 これの解説です。 atcoder.jp 以下の二つを参考にしながら考えたことをまとめます。 ACL の floor_sum のコード (特に x_max まわり) が何やってるかわからなくて自分で考え直してたら、x_max が必…

夢地区参加記 2 は これ。 今回は設定が特に謎なのですが、夢なのでそういうものだと思います。 一度ボツにしたものの、変にハードルが上がるとよくないので書きます。 起きた後に軽くメモをしているとはいえ、いくらか日が経っているので正確でない記述があ…

セグ木は知っているとします。 知らない人は えびちゃんのスライド なり適当な記事なりを読んでください。 セグ木上のにぶたんも上のスライドに載っていますが、もう少し解説したいかなと思います。 上のスライドにある図を見るとイメージが湧きやすいかもし…

↓ 勉強し直しました ↓ rsk0315.hatenablog.com union-find の計算量解析で出てくる \(\alpha(n)\) というのがありますね。 Ackermann 関数の逆関数として知られるやつです。 競プロ er の多くは、次のような認識をしていると思います。 計算量に \(\alpha(n)…

考えていたことなどを書きます。 tl; dr 94 点と申します......— えびちゃん (@rsk0315_h4x) 2020年11月8日 受検前 有料期間中に受けるかどうか考えました。 前提として、既にエキスパートの認定証を持っているので、以下のような葛藤が生じます。 エキスパ…

これは夢日記ではありません*1。 夢日記は これ と これ。 チームメイトは夢日記と同様、monkukui と TAB とえびちゃんです。 チーム名は tsutaj で、これは去年までチームメイトだった先輩に由来します。 tsutaj 抜きのチームに tsutaj と名付けるの、余因…

参加記 1 は これ。 意外と好評でした。 辛そうにしてるの笑うのはなあと思いつつも内容が面白くてめちゃくちゃ笑っちゃった— olphe (@_olphe) 2020年11月2日 おもしろかった シリーズ化してほしい— そすうさᕱᕱ（素数うさぎ） (@wk1080id) 2020年11月3日 シ…

夢の中で ICPC に出てた、参加記書くか迷う— えびちゃん (@rsk0315_h4x) 2020年11月2日 ICPC に夢の中で参加してきました。せっかくなので参加記を書きます。 見たい— olphe (@_olphe) 2020年11月2日 期待しないでね。 チームメンバーは monkukui と TAB と…

競プロをしていて、一時的に値を決めておくけれども、提出時には直したいということがあるかもしれません。何らかの理由で。 int m = 10; // to be edited 実際には m は入力によって変えるべきだけれども、手元のデバッグなどの都合では定数の方が楽、とか…

コンテスト中に見に来た人へ：コンテスト後、この記事にある方法以外についても復習しておくのをおすすめします。 自然数（\(0\) を含むよ）の集合において、mex というのは、minimum excludant (minimum excluded) の略で、それに含まれない最小の自然数の…

自分が楽に作れるようになると忘れがちなんですが、どうやらこれを書くのに疲弊する人がまだいるようです。 size_t n1, n2, n3; // ↑入力を受け取るとかして、値が入るとする vector<vector<vector<int>>> v(n1, vector<vector<int>>(n2, vector<int>(n3, x))); みたいに書くのはさすがに大変だと</int></vector<int></vector<vector<int>…

「バグったたすけてー」と言っている初心者の人のコードを見たとします。 バグを見つけてあげるのは（多くの場合）簡単ですが、それを伝えただけでは成長につながらないかなぁとも思います。 「こういうところをこうやって確認したよ」「そしたらこうなった…

C++ を使うのが悪くて、Rust を使えばいいんじゃないですか？ これ系の記事を乱立させていて申し訳ないです（これこれの話ってどの記事？となりそうなので）が、罠が多い C++ 側に責任があるので、えびちゃんは悪くありません。 それに、一つ長い記事を書い…

興味のある人だけ見てくれたらいいです*1。 えびちゃんが最近なにをしているかを書きます。 まず、競プロをほぼしていません。 ABC に出るくらいはして、下位層の人にはまだ勝てますが、半引退みたいな状態になっています。 お勉強はしています。 Rust を始…

off-by-one エラーとか呼ばれるやつです。「1 ズレてたせいでこわれた」というやつですね。 バグらせやすい書き方をするのがよくないです。書き方を改めるのがよいでしょう。 ここでは、えびちゃんがよくやっている書き方を紹介しますが、別にこれが絶対とい…

std::sort(a.rbegin(), a.rend()); みたいなやつです。 便宜上 std::vector のようなものを考えますが、std::set とかについても同様です（random-access モノは除く）。 普通のイテレータ まず普通のイテレータに触れましょう。 [0][1][2]...[n-1][-] ^ a.b…

まず、セグ木自体は難しいものではないので、変な先入観は無くしましょう。 以下は、再帰の知識がなくても読めるように心がけます。 「何から始めたらいいかわからない」という人は、とりあえず最初に述べるセグ木を理解するところから始めるといいと思いま…

tl;dr AtCoderJobs 最高！ 一番好きな就活サイトです 個人的には「M1になるまでは競プロを楽しくやってて、M1になってさすがに就活やべえってなった時に競プロ経由で色々らくできてラッキー！」くらいの距離感が一番すきｗhttps://t.co/DGbzKSk3pu— chokudai…

これに出てくる (*'-')b この子です。 つくりかた この子の挙動は次の通りです。 直前のコマンドが空なら何もしない 直前のコマンドが空でないなら、実行ステータスに応じて話す まず、現在の状態を示す変数 state を用意します。 この変数は次のように値が…

長いこと Bash を使い続けていました。 逆張り癖が災いしすぎた気がします。 Bash は man ページを一通り読むくらいには愛着を持っていたり、あれこれ触ったりしていました。 Zsh の導入自体は何度か挑戦しようとしていたのですが、（多くは勉強不足で）合わ…

今までいろんな人に何回も説明した内容は、これからも何回も説明することになりそうなので、記事としてまとめておいてみます。 自分としてもこの記事へのリンクを貼ればよい上、読んだ人が（辞書で隣の単語もまとめて覚えるみたいな感じで）別のことも知れた…

PAST #1 の記事 に続いて、今回も解説記事を書きます。 公式の解説 がもう上がってた。早いね。 問題へのリンク。 A - エレベーター 1F, 2F, 3F, ... を渡すと 1, 2, 3, ... に、B1, B2, B3, ... を渡すと 0, -1, -2, ... にしてくれる関数を考えます。 int …

プロフィールページでリロードをたくさんしました。 というのも、レート変動を待たずに寝ちゃう人は知らないかもなんですが、色が変わるタイミングで数分間（15 分くらい？）だけ表示が変になるタイミングがあります。 間違い探しです。 これが見たくて待ち…

これ、蟻本とかにも書かれているので常識かなと思ってたんですが、最近よくハマっている人を見かけるので、記事として書いておくことにします。 ↓ 追記 ↓ この記事と別の手法についても書きました。競プロの範囲ではどちらの手法でも困らない気もしますが、…

問題設定 たかだか \(n\) 次式 \(f(x) = \sum_{i=0}^n a_i x^i\) がありますが、与えられません。 \(n+1\) 個の点 \(x_0, x_1, \dots, x_n\) と、それらの点での \(f\) の値 \(y_0, y_1, \dots, y_n\) が与えられます。 すなわち、\(y_i = f(x_i)\) (\(i=0, …

問題設定 多項式 \(f(x) = \sum_{i=0}^n a_i x^i\) と、\(m\) 個の異なる点 \(x_0, x_1, \dots, x_{m -1}\) が与えられます。 これらの点での値 \(f(x_0), f(x_1), \dots, f(x_{m -1})\) を求めてください。 ただし、各計算は \(998244353 = 119\cdot 2^{23}…

一年くらい前に、いろんな日本語記事を読み漁ったものの、あまりわからず挫折して放置していました。 昨日、いつもの に書かれているのを見つけて、読むとわかった気になって、実装できました。 うまい例と、図などを用いながら動作を説明してくれるので、わ…

まず黄色になります。 rsk0315.hatenablog.com 次に青になります。 えびちゃん青コーダーになりました！！ pic.twitter.com/s0j9LQYToa— えびちゃん (@rsk0315_h4x) August 17, 2019 （なんでここから半年かかってるんですかね...？） 以下、黄色になる (2) …

年明けから 1 月が経ったらしいので今年の目標を書きます。 年明けくらいに立てていた目標 今年中には TDPC うめたいなぁ。→ うめました ARC-B をうめたいなぁ。→ あと二問 さすがにこれじゃ一年かからなさそう。 いま考えている目標 数値的にわかるやつ ARC…