スナネコです。拡張GCDについての質問に答えます。問題： 以下のように実装された extgcdがある。 整数 が を満たし、extgcd(a, b) の返り値を としたとき、 が成り立つことを示せ。 def extgcd(a, b): # ax+by=gcd(x,y) を満たす (x,y) を返す if b == 0: r…
パークガイド「長くなったのでブログの方でお答えしました」https://t.co/5iCqTXMgkJ#マシュマロを投げ合おうhttps://t.co/2YaT6kUXWU pic.twitter.com/EDONHtZPHV— 競技プログラミングをするフレンズ (@kyopro_friends) August 25, 2023 Difficultyに関する…
パークガイド「気合を入れて書きました。是非読んでください」https://t.co/oPugj95QiL#マシュマロを投げ合おうhttps://t.co/BLH5Yfv3zp pic.twitter.com/axPvtf1Hor— 競技プログラミングをするフレンズ (@kyopro_friends) 2023年5月30日 パークガイドのミラ…
スナネコです。 競プロ界隈で"除原理"と呼ばれているものについて説明します。 この言葉は厳密な定義があるものではないので、これから説明することは単に「私はこうだと思っている」というお話として聞いてください。 定義 「 と が与えられるので、 を求め…
スナネコです。 Grundy数がxorで計算できることの説明をしてほしいとサーバルさんに頼まれたのでします。ざっと検索してみましたが、「Grundy数が0でないとき0にできる」くらいしか証明が書いてあるものは見つけられないですね。これではXORになることの説明…
パークガイドのミライです。ABCの解説の実装例について議論があるようなので、私たち競プロフレンズとしての見解を述べておきます。 本来であればアライさんを筆頭とした、精力的に競プロをされているアニマルガールの方々に説明をしてもらった方がよいこと…
スナネコです。yosupo judgeにある を解きました。 https://judge.yosupo.jp/problem/sum_of_exponential_times_polynomialyosupo judge の github を見ると参考文献が載ってます。 https://github.com/yosupo06/library-checker-problems/issues/98そういう…
サーバルだよ！ AGC051C『Flipper』の解説をするよ！ コンテスト中の考察 なんだかライツアウトっぽいね。 ライツアウトと同じようなことをすれば解けそう。 ライツアウトをmod2での連立方程式だと思って解く方法と同じプログラムを書いて、6×6や7×7で実験を…
スナネコです。 AtCoderのpractice contestのB問題を解いたので解説を書きます。問題ページにあるコード例を読むとわかりますが、この問題は「Q回以下の比較で、長さNの数列をソートせよ」と読み替えられます。 (N,Q)=(26,1000)のとき コード例に書いてある…
スナネコです。twitterで出した問題について解説します。問題その１： 高橋君は の倍数と 7 が好きです。 7,77,777,…という数列の中に初めて の倍数が登場するのは何項目ですか？ 存在しない場合は代わりに -1 を出力してください。制約： 解説： が 7 の倍…
スナネコです。 yosupo judgeのNim productを解きました。 問題よくわからないですが、Nimber product、Nimber multiplicationみたいな呼び方もあるみたいです。なんて読むんですかこれ？私に読める言葉で書かれたものが見つからなくて困ったので、丁寧めに…
スナネコです。yosupo judgeにある を解きました。 問題d=0の時はただの等比数列の和です。 d=1の時を計算する問題もときどき見ますね。例えば「1の目が出るまでサイコロを振るときの回数の期待値は？」とかです。 …………冗談です。まさかこの問題でそんな計算…
サーバルだよ！ 競プロの精進について書くよ。 精進の仕方や、精進に対する考え方はいろいろあるから、あくまで私の意見だと思って読んでね。 ■3行でまとめて ・復習が大事。解けた問題も解けなかった問題も、解説やいろんな子の実装を見てみる ・典型を身に…
EDPC解説目次へ戻るやー、フェネックだよー。 残りの6問はどれも難しいけど、解説していくよ。 実装例は省略するから自分で考えて書いてみてねー。 U問題 Grouping 羽のうさぎをいくつかのグループに分ける。 うさぎのペアについて、とが同じグループに属し…
EDPC解説目次へ戻るカラカルよ。M問題～T問題を解説するわ。 このあたりから計算量を気にして高速化をしないといけない問題が増えてきて大変だけど、ついてこれるかしら？ M問題 Candies 人の子供にちょうど個の飴を配る方法は何通りあるかで求めよ。 ただし…
EDPC解説目次へ戻るはいはーい、サーバルだよ！ F問題～L問題の解説をしていくよ！ よろしくね。 F問題 LCS 2つの文字列,が与えられる。 ,の共通部分列であって、最長のものを1つ求めよ。 制約： 解説 いきなり難しい問題だね……。 「求める文字列の長さ」だ…
EDPC解説目次へ戻るアライさんなのだ！ EDPCのA問題～E問題を解説するのだ！ A問題 Frog 1 ～の番号がついた足場がある。 足場からは足場かに移動でき、足場から足場に移動するコストはである。 足場から足場に移動するまでの最小コストを求めよ。 制約： 解…
みなさん、こんにちは。パークガイドのミライです。 先日行われた『DPまとめコンテスト/Educational DP Contest』、通称EDPCの解説を競プロフレンズのみなさんに書いていただきました。 個別の解説に入るまえに、解説の中で登場するコードについて注意をいく…
