atcoder.jp アレが出てきた…！ shakayami.hatenablog.com なんとかコンテスト中に通せたので良かった。 問題概要 $f(x,y)$を$x+y$の桁和とする。このときに$\sum_{i,j} f(A_i,A_j)$を解けるだろうか？ただし$O(N^2)$は間に合わないよ 解法 まず、以下の等式…

atcoder.jp これを頑張って計算すると以下の式（を998244353で割った余り）を出力すればいいことがわかります。 $$\sum_{M=0}^{N}\binom{N}{M}\cdot \binom{K+M+1}{N+1}$$ この式の導出方法はこの記事の本筋からそれるので省略します。解説参照！ さて、制約…

以下の2つの問題があります。それぞれどう解くでしょうか？ 問題1 $N$を正の整数とする。$0,\ldots,N-1$を並び替えた順列を$a_0,\ldots,a_{N-1}$とする。 このとき、以下の操作を行うことができる 操作：$0\leq i\lt N-1$を一つ選んで、$a_i$と$a_{i+1}$をス…

注意 はてなブログの仕様のため、タイトルはわざと全角文字にしています。 概要 タイトルの通り、pythonで「[0][0]」と入力すると0を出力する。 これは、[0]という長さ1の配列の0番目の値*1を出力するという意味なのでそうなる。 さらに、[[0][0]][[0][0]]も…

問題のリンク atcoder.jp 解法 まず、$a_k=a\alpha^k+b\beta^k$という形で書くことができる。$d_{n,m}$の値は$a_k=\alpha^k,\beta^k$の結果がわかればそれの線形結合で書けるので、$a_k=r^k$といった等比数列でこの問題が解ければOK。 $a_k=r^k$のときの答え…

概要 shakayami.hatenablog.com この記事で作問したいと言っていましたが、作問することができました。*1 というのも、実は京都大学プログラミングコンテスト2021の準備に関わってました。 atcoder.jp 競プロの作問について 数学の作問とは少し勝手が違いま…

公式解説と違う解き方をしたので書く 問題リンク atcoder.jp 解答 以降ではボールの番号として$1,\ldots,2N$がついていて、$i$番目のボールと$i+N$番目のボールを同一視することとする。 まずこれを見て最初に思い浮かぶのは写像十二相である。写像十二相に…

概要 atcoder.jp opt-cp.com これを見てバーンサイドの補題というものが気になったのでいろいろ試してみることにした。 問題 正多面体の各面に対して正の整数を定める方法で、全部の面の和が$S$になる方法は何通りか。ただし回転して一致するものは同じとみ…

ただしO(N^2)は間に合わないものとする。 基本的な攻略法 type0 明らかな場合 定数関数 f(x,y)=1 射影 f(x,y)=y type1 四則演算型 足し算 f(x,y)=x+y 引き算 f(x,y)=x-y 掛け算 f(x,y)=xy (ABC177-C) 割り算(有理数) f(x,y)=y/x 割り算（小数部分切り捨て） …

公式解説を少し補足したいと思います。 あと、コードは書きません。 問題のリンク atcoder.jp step 1 形式的べき級数を知ってますか？僕は知ってます。*1 1～mのサイコロを振ったとき、表がちょうど$N$回出る回数については、 $$\left[x^N\right]\prod_{i=1}…

問題リンク atcoder.jp 解法 焼きなまし法で通せる！！ 以下のソースコードを手元で実行すると10秒程度で実行が終わるため、出力をコピペしてtext(cat)で投げるとOK。 ソースコード (言語 : python3) import sys import random import math N=100 X=[] Y=[] …

人が書いている色変記事といふものを、自分も書いてみるとてするなり。 自己紹介 数学科 python勢 概要 青になれた！！！！ pic.twitter.com/qBFrJVztNa — しゃかやみ (@shakayami_) 2018年9月29日 ↓798日後（2年2ヶ月6日後）↓ こっちの垢でもツイートします…

AtCoder解説記事は初投稿ですあと、pythonで書きます。 問題 atcoder.jp ステップ0 入出力を書いてみる。現在はこうなっている。200003という数は意味ありげなので最初に書いておく。 N=int(input()) P=200003 a=[int(i) for i in input().split()] #なんや…