この記事はCCS Advent Calendar 2020の11日目の記事として作成されました。前の記事： note.com nullです。今回は素数判定や素因数分解を行うアルゴリズムについて色々書きます。 整数 の素数判定 最も初歩的なものとしては、 以上 以下の整数が を割り切る…

yukicoderのAdvent Calendar Contest 2020のD問題を作問しました。 問題 yukicoder.me 解法 解説を見てください。（おわり） 余談 自分の中ではド典型だと思ってたので没にするか迷いましたが、Testerに後押しされたので出題することとなりました。大正解だ…

先日のABC184でついに入黄しました！ AtCoder黄色になりました！！ pic.twitter.com/VMPiKQFLvo — stoq (@stoq_) 2020年11月22日 青になってから約1年のタイミングで色変できてうれしいです。慣例に倣って色変までにやったことを書きます。 アルゴリズムやデ…

ICPC国内予選に参加したので参加記を書きます。メンバーははにゅさん、ももはらさん、僕(stoq)のチームharaharaです。（いつもの） 開始前 方眼ノートを買ったり、ネットの海からライブラリを拝借したり、三度寝したりしました。 コンテスト 最初問題が見れ…

今更ですが、ARC106-D Powers の簡単な解説を書きます。 問題リンク： atcoder.jp 問題概要： 長さ の数列 がある。 それぞれについて、 を求めよ。 解法： 対称性から なので、これを求めます。（こちらの方が後の計算が楽です。） まず括弧の中を展開する…

いつも通りstoq, momohara, hanyuのチームharaharaで模擬国内2020に参加しました。 覚えてる範囲で書きます。 開始前 30分前に起床する（すいません）。ごはんを食べ損ねる。TLを見るとももはらさんも同じことやってた。 A～Cの割り振りを決める。いつも大体…

秋分コンテストに参加しました！13位という高成績を残せて満足です。癖の強い問題が多くてとても楽しめました。 記憶に残ってる問題について書きます。 B : Self Introduction そのまま"I am stoq"で出したらAC。ユーザー名が入ってればACになるっぽい？ C :…

注意 内輪ネタです。 1053とは： mattyan1053.hatenablog.com 概要 「1053」という数の性質を列挙しただけの記事です。 自明な性質 ・実数である。 ・整数である。 ・奇数である。 ・。 ・2進法で表すと10000011101。 ・。 非自明な性質 OEISからの引用が多…

（初心者向けの記事です） 競プロでたまに見るC++のテクニカルな表記をメモ程度にまとめておきます。 自分自身はあまりこのような表記は使わないのですが、他の人のコード、特にライブラリ化している部分においてはよく使われている気がします。他の人のコー…

yukicoder contest 247のwriterのstoqです。初めての作問なので至らない点もあったと思いますが、全体的にいい感じにできた気がします。 コンテストリンク： https://yukicoder.me/contests/262 yukicoder.me 注意したこと ・assertで制約外のテストケースが…

先日のABC165-Cが難しかったようなので、おすすめの実装法を紹介してみます。 この問題に限らず、愚直にやるとn重ループを書きたくなってしまう全探索問題全般に適用できるのでオススメです。問題リンク： atcoder.jpとりあえずコードを乗せます。 #include <iostream></iostream>…

「 頂点の木において、 を根としたときの○○をそれぞれ求めよ」というタイプの問題では、全方位木DP(ReRooting)が有効に働く場合が多いです。 根を1つ固定したときにこの問題が高速に解けるならば、全方位木DPを用いることで同じ計算量で全ての根についての問…