Chess.comのRapidレート分布を取ってみた。
チェスのレート分布について書かれている日本語の記事だと下記の記事が一番わかりやすく丁寧にまとめられていると思います。
ただ一言にレートといってもプレイするサイトや持ち時間によって違ってきます。なんとか自分がプレイしている環境の分布が取れたので、備忘録として残すことにしました。今回取ったデータはchess.comのrapidです。
ここのページからデータを取ります。
まず、F12
を押してソース表示して、Ctrl + Shift + C
で見たい要素のところにカーソルを持ってきます。
画面右側か最下部に分布曲線が表示されているのでそこにカーソルを合わせてクリックすると、右側にそれっぽいデータが出てきます。
path("M
から始まるデータ群がなんかそれっぽいなあと思ったのでメモ帳に貼り付けます。
2値ごとにLという文字で区切られてるので文字を消去して改行したりなんなりしてエクセルに貼り付けます。
データを眺めるに、2項目(B列に貼り付けたデータ)が分布グラフの天井からの距離を表してそうだったので床からの高さになるようにして、いろいろ計算をすることで分布を出しました。
1400いけたら上位10%ということで、とりあえずそこを目指したいと思います。以上になります。
ここまでお読みいただきありがとうございました。
こちらの記事を参考にするに、今のレートから1400目指すのは水色から黄色を目指すようなものらしいので気長に頑張りたいですね。
「若い頃は怖いもの無しだったけど、みんなだんだんと大人になっていくんや」で説明される全ての事象、ただの学習性無力感じゃんか
タイトルで落ちてる。
学習性無力感(leaned helplessness)とは
「抵抗の効果が認められない状況が長く続くと、抵抗することすらしなくなってくる」というあれ
大人象だと壊せるが子供象だと壊せないくらいの強度の輪っかを足につけて木などに固定する。するとその子供象は、例え輪っかを壊せるくらい成長したとしても壊そうともしなくなってしまうという話。*1
やろうと思えば出来るのに過去に出来なかったという経験が起因して、やろうとすらしなくなってしまう。他にも犬に電気を流す実験や人に不快音を流す実験もある。(怖い)
実際に問題になっている例でいうと虐待やDVに遭っているけどそこから逃げ出す意志すら失ってしまっているというケース。今回はここらの話には触れず、自分で勝手に学習性無力感に陥ってしまっているケースについて取り扱う。
「若い頃は怖いもの無しだったけど、~」
「小中では成績トップだったけど高校で雲の上の存在に出会ってしまった」はよくある話で、これもタイトルで言ってることに当てはまる場合があると思う。
2つパターンがあって、1つはその高校や大学、Twitter上などで出会った存在に感化されて自分も追いつこうと必死になるパターン。もう一方が、圧倒的実力差に愕然として戦意を喪失するパターン。後者の場合、その状況が長く続いてしまうと「俺は誰よりも頭がいいんだ。あれもこれも俺はなんなく学習してみせるぜ」というおそらく昔は考えてたであろう、学習する際にはこの上なく良質なマインドセットを失ってしまう。
恋愛でもよくある。
誰かを好きになって始めのうちは声を掛けにいったりLINEをしてみたりするけど、あんまり良い反応が返ってこなくて無理そうやなぁ何も進展させられんなぁ感を味わう。一方的に片思いをするという期間が長くなってその状況に慣れてしまう。「今の状態が一番いいから」とかほざいたりもしてみる。人によっては、例え何か交流の機会を得られそうになっても「いや、俺はいいわ」とか言って遠慮したりする。ただ度胸がなくて踏み出せなかっただけなのに「スマートな対応をした」と自分の中で合理化する。想いは解消されていないのに、過去の経験から「自分のアプローチは上手くいかないだろう」と学習して、何もアクションを起こしたくなくなる。これも1つの学習性無力感だろうと思ってる。
「能力分布の中での自分の位置をしっかり把握出来ていて、冷静な応手を指せるようになった」と言えばかなり聞こえが良い。
どうしようか
もう何に対しても挑戦意欲が湧かず、特にしたいことも生まれず、コンテンツを消費して人生を溶かしていく。
勉強や恋愛の範囲内においてのみこの学習性無力感を感じている分にはきっとまだマシで、これが人生全体に対して感じてしまうようになるとかなり厳しい。人生の悪化具合が笑えないレベルになってきたとしても抵抗しない。
結果これになって死ぬ。
本当に困っている人というのは、「助けてくれ」は言いません。どうせ救われないと思い、気後れするので。餓死者の統計を取ったとき、殆どの餓死者が死ぬ前に知り合いのところへ行き、何でも無い雑談をして帰り、そしてその後のたうち回って死ぬ、というのは忘れてはならないことなんですよ。
— ぬまきち@デイズBOX9/25発売! (@obenkyounuma) 2020年10月23日
どうしようか(その2)
分からない。
結局自分の中での自分に対する評価が下がりすぎてる事が問題だから、じゃあ自分の評価(特に、これから行動をしようかとしている自分に対しての評価)を高めていこうかということが一番直接的な措置になると思う。
昔、「自己肯定感を回復させるには毎日取り組むべきことに取り組んでそれによる積み重ねからゆっくり回復させていくしかない(スポーツ漫画っぽい漫画の画像付き)」的なことを言ってるツイートがあって、「それはそうだなぁ」と思ったし、ある名言にトーマス・カーライルさん(雄弁は銀、沈黙は金の人)という人の
勤労はつねに、
人類を悩ます
あらゆる疾病と悲惨に対する、
最大の治療法である。
というのがあってこれも「それはそうだなぁ」と思っているので他人に頼ってもあんまり解決しなそうな感じがしている。1周回ってこういう本を読むしかないのだろうか分からない。
踊る
踊りはしないけど、結局このおっさんが言ってることが全てかなぁというのが現状の結論です。音楽を爆音でかけるなりカフェイン摂取したりで取り合えず無理やり精進の習慣をつけていくしかないんだ人生は。
【備忘録】vimでc++コードを実行する【Ubuntu】
まず色々アップデートとかしておこう定期
sudo apt update sudo apt upgrade
ターミナルは管理者権限で開きましょう.
vimとg++をインストールします.
g++は.cpp
ファイルをコンパイルします.
sudo apt install vim sudo apt install g++
次にtest.cppというファイルを作成します.
vim test.cpp
i
もしくはA
で編集モードに切り替えて適当なサンプルコードを打ち込みます.
まだコードが書けないという方がいましたら下記のコードをご参照ください.
#include<iostream> using namespace std; int main() { cout<<"Hello, World!"<<endl; return 0; }
esc
キーでノーマルモードに切り替えて,:wq
でファイルを保存&終了します.
次のコマンドでこのファイルをコンパイルして実行させます.
g++ test.cpp ./a.out
エラーがなくコードが実行できれば終了です.
上記のサンプルコードであればHello, Wolrdという1行が表示されるはずです.
一応自分が動かしたときのスクリーンショットも載せておきます.
※仮想環境での管理者権限でのターミナルの開き方がよく分からなかったのでところどころコマンドの頭にsudo
を置いて実行してみています.
※コマンドls
は今いるディレクトリの中のファイルたちを表示するコマンドです.コンパイルした後にa.outというファイルが生成されていることが分かりますね.
記事はここまでになります.ここまでお読みいただいた方ありがとうございました.
【osu!】オススメ譜面一覧 【star4-5】
私が気に入っている譜面の一部を紹介します。気になったものがあれば是非ダウンロードしてみてください。
quaver
ご存知quaverです。曲名の読み方がイマイチ分かっていません。クワベルでしょうか。
ジャンプが多く高ppが取りやすいです。譜面の数も23個あり初心者から上級者まで楽しめる譜面です。
また、この譜面を制作したSotarksさんはその他にもたくさんの譜面を制作されているのでチェックしてみるとよいかもです。
ILY
こちらも数千万回以上プレイされている定番譜面です。タイミングが取りやすくaccuracyの訓練にはもってこいです。
oyasumi
曲自体が短いため周回に向きます。ジャンプの練習にもなり高ppを取りやすいです。絵も綺麗で好きです。
Bass Slut (Original Mix)
こちらもジャンプ譜面です。難易度の割にはパスしやすい印象があります。普段star4.5~を触っている人であればstar6付近の譜面もクリアできるはずです。
Yuudachi no Ribbon
声が綺麗です。譜面自体はジャンプと短めのスライダーが続きます。3分半ほどある譜面なので1000コンボ以上を狙えます。
KAC 2012 ULTIMATE MEDLEY -HISTORIA SOUND VOLTEX-
サウンドボルテックスの曲です。とにかく曲がカッコイイです。こういう曲に出会うためにこのゲームをやっている節があります。この譜面のstar4.56でフルコンボを取ることがここ半年くらいの目標になっていますが未だに達成できていません。
Crack Traxxxx
こういう曲に出逢うためにこのゲームをやっている節があるシリーズの2曲目です。
Packet Hero
この曲もただただよいです。感情です。
DrunkenSteiN
この曲も圧倒的カッコよさがあります。ただ譜面構成自体はあまり好きではないです。
ANiMA
国民の9000%が認知していることでも有名なANiMAです。この曲を作曲されたXiさんに限った話ではないですが「かめりあ」さんや「M2U」さんなど有名作曲家さん方の名前でbeatmap検索をかけるとヒットすることが結構多いです。
Bonetrousle
アンダーテールに登場するサンズの弟パピルスの曲です。高難易度は用意されていませんが初心者がジャンプの練習をするにはかなり有用な譜面だと思います。DT,HDをつけてやると結構楽しいです。
Spider Dance
同じくアンダーテールより蜘蛛の姿をしたボス:マフェットの曲です。
asphyxia (TV edit)
続いて東京喰種よりasphyxiaです。細かくリズミカルな打鍵が要求され50点や100点が続くとコンボが続いていたとしてもfailになったりします。star1.59から6.01まで幅広く、10個の譜面があります。
Inochi ni Kirawarete Iru.
「命に嫌われている」です。声も綺麗だし絵も綺麗だし譜面も素直なのでやっていて楽しいです。
Putin's Boner
譜面的には先に紹介した「Yuudachi no Ribbon」をもう少しハイテンポにしたような譜面です。めちゃめちゃジャンプの練習になるし音楽も綺麗なのでかなりプレイ回数が多い譜面の1つです。
Akasha
綺麗なピアノの曲です。ストリームが多く苦戦させられましたがとにかく曲が綺麗なので楽しんでプレイできます。
Teo
最近チュウニズムにも追加されたボカロ曲です。star4や5あたりの譜面を触った感想としては、基本的には短いスライドが続く部分が多く集中力さえ保てていればコンボを稼ぐことは出来るが要所要所に短くない中程度の長さのストリームが続き体力設定も甘くされてないのでaccuracyが90%以上でも全然死ねるなあ。。。です。
Unknown Mother-Goose
かなりハイテンポな譜面です。ハイテンポではありますが、3つ以上の連打が少なかったりノーツ間の距離も短めであったりするので集中さえできればコンボが続きます。なのでプレイしている側からするとただ楽しいという感想を抱けます。女性の声も綺麗でよいです。
Snow Drive(01.23)
1つ前で紹介してるアンノウンマザーグースのテンポを少し落としてスライドを減らしたような譜面をしています。なので難所という難所はないのですがあまり体力ゲージの回復をさせてもらえないので小さいミスが重なってfailする事が多いです。
Lune
ストリーム譜面です。出来る人は出来るし出来ない人は出来ないです。ただとてつもなくピアノの演奏が綺麗な曲です。指の筋トレがてら挑み続けましょう。
ここまでが普段練習がてらスコアアタックがてら遊んでいる譜面たちです。
続いてRXモード専用の譜面を紹介していきます。RXモードとは打鍵が自動になりカーソルを合わせるだけの練習ができるようになるモードです。
Dead To Me (feat. Lox Chatterbox)
ar9の譜面と9.5の譜面と10の譜面が用意されています。(arとはapproaching rateでノーツの周りの円が近づくスピードです。数字が大きいと早いです。つまり画面に表示されてから打鍵しなければならないタイミングまでの時間が短くなるということです。)
実際にRXモードで練習している様子です。
プレイ自体は何度もしているのですが練習用のモードなのでスコアが記録されず、プレイ回数なども分からないのが残念なところです。(なのでよくリプレイを録画したりしています)
FREEDOM DiVE
star7.78の超高難易度譜面です。ほどよくジャンプが要求され、また長いストリームも多いためかなりよい練習曲です。長いコンボがつながったときの爽快感は全譜面の中でナンバーワンです。現時点ではaccuracy94%くらいが自己ベストです。xi最強。
Sound Chimera
star8.30の楽しい譜面です。かのwhitecatがスコア1位に君臨しています。単調さがない一方でカオスというわけでもないので、楽しくはないのですが(ついていくのに必死になるので)気持ちのいい汗をかける譜面であるかと思います。accuracyは8割を超えれば十分かと思います。
Walk This Way!
難易度設定の割にはジャンプ距離が短いので動体視力さえ頑張ってもらえればノーツは拾えるのかなという印象です。
werewolf howls. ["Growling" Long ver.]
star7.71
かめりあ先生のかっこいい曲が視聴できます。おまけとして高難易度特有の人間離れした速さ遠さのジャンプが練習できるそうです。85%を狙いたいです。
Enigma
変に間隔の空いた連続ノーツ列の練習になります。音楽自体のリズム感もトリッキーなのでそこも含めて練習になります。80%を狙いましょう。
Presenter*
star7.86を誇る高難易度であるにも関わらずこれといった特徴がないのが特徴かもしれません。RXモードで練習する際の入門譜面です。イーストブルーです。90%取れれば充分でしょう。
Hightechnological
star7以上の譜面が6つも用意されています。10分もあり長いです。しかも音楽も単調で退屈かもしれません。ただ譜面がとにかく飽きないです。ほどよい難易度が10分も続くので無理やり(osuへの)集中力を高めたい時とかに使います。やってみると分かりますが10分があっという間に過ぎます。
Grievous Lady
arcaeaよりGrievous Ladyです。曲が好きすぎるのでよく触りますがちょっと難しいので譜面自体の魅力がまだ十分に分かっていないです。
furioso melodia (2017 VIP)
star7.51
曲がいい。顔がいい。譜面は少し退屈かも。
Ooi [Game Edit]
star7.21
オーソドックスなストリームや長い距離のジャンプをゆっくりめに練習できる譜面。
Sukisuki Zecchoushou
star7.12
ただ曲が好き。
ANOMALY (Camellia's "MUTATION" Schranz Remix)
オブラートに包むと最悪の譜面。ノーツ配置の動機が見えない。めちゃくちゃ。カオス。でもプレイしちゃう。
私はただ筆を動かすだけのロボットです。二度と逆らいません。すいませんでした。という気持ちになれる。
Yoru ni Kakeru(5月18日追記)
star7.50
とても良い曲です。語彙力が乏しいばかりにこの曲の良さを文字のみで簡潔に記述するのは少し難しいです。とても良い曲です。今年出逢った曲の中で1番ハマっている曲です。
ここらへんが普段主に練習用として触っている譜面たちです。
またosuにはカーソルだけを自動で動かすapモードも用意されています。打鍵の練習にはもってこいです。そして自分の場合には下記の譜面で打鍵の練習をしています。
1日5分もやれば十分です。
最後にメモがてら現時点での自分のプレイ環境だけ残して終わりたいと思います。ここまでお読みいただいた方ありがとうございました。
pentab: Star G430S ペンタブ、板タブ|XP-PEN公式サイト
skin:
https://ux.getuploader.com/flandivahaku/download/76
pass:5555
(2020年5月11日追記)
new skin:
https://ux.getuploader.com/flandivahaku/download/77
pass:12345
フレームリミッター:カスタム(240)
FPSを表示する:オン
伸びるスライダー:オフ
ビデオを表示する:オフ
ストーリーボード:オフ
ヒットライティング:オフ
メインメニューに雪のビジュアルを表示する:オン
背景の明るさ:78%
スコアメーターの大きさ:2.93%
常にキーのカウンタを表示する:オン
音量:音楽20、効果100
付属ヒットサウンドを無効化:オン
譜面付属のスキンを使わない:オン
常にスキンのカーソルを使用:オン
カーソルサイズ:0.72x
自動カーソル調整:オン
プレイ中マウスボタンを無効化:オン
キー設定
Left Click:テンキーの5
Right Click:テンキーの6
Game Pause:テンキーの9
Skip Cutscene:テンキーの0
(2021年5月11日追記)
前回の追記からちょうど1年なのすごい。
ずっと使っているペンにテニスラケットのグリップ(?)を巻いてみました。
スポーツ用品店で数百円くらいで販売されていました。
あと、今日時点での戦績も貼り付けておきます。
ペンの使い心地も変わったしこっから上がるといいな!
owari!
E - Sum of gcd of Tuples (Hard) #AtCoder
問題概要
入力N、Kが与えられる。
1以上K以下の整数からなる長さNの数列Aについて、考えられる全てのAのgcd{A_1, A_2,...,A_N}の総和を求めさせる問題。
サンプル1
3 4
という入力であった場合(N=3、K=4)
数列は項数が3個で、各項は1or2or3or4となる。
例えば{1、1、2}や{2、3、1}や{4、4、3}が考えられる。
そして各数列に対して各項の最大公約数を求めたい。ということである。
まず考えうる全ての数列を列挙してみる。
1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 1 2 2 1 2 3 1 2 4 1 3 1 1 3 2 1 3 3 1 3 4 1 4 1 1 4 2 1 4 3 1 4 4 2 1 1 2 1 2 2 1 3 2 1 4 2 2 1 2 2 2 2 2 3 2 2 4 2 3 1 2 3 2 2 3 3 2 3 4 2 4 1 2 4 2 2 4 3 2 4 4 3 1 1 3 1 2 3 1 3 3 1 4 3 2 1 3 2 2 3 2 3 3 2 4 3 3 1 3 3 2 3 3 3 3 3 4 3 4 1 3 4 2 3 4 3 3 4 4 4 1 1 4 1 2 4 1 3 4 1 4 4 2 1 4 2 2 4 2 3 4 2 4 4 3 1 4 3 2 4 3 3 4 3 4 4 4 1 4 4 2 4 4 3 4 4 4
そして各数列に対して各項の最大公約数を求めます。
1 1 1 -> 1 1 1 2 -> 1 1 1 3 -> 1 1 1 4 -> 1 1 2 1 -> 1 1 2 2 -> 1 1 2 3 -> 1 1 2 4 -> 1 1 3 1 -> 1 1 3 2 -> 1 1 3 3 -> 1 1 3 4 -> 1 1 4 1 -> 1 1 4 2 -> 1 1 4 3 -> 1 1 4 4 -> 1 2 1 1 -> 1 2 1 2 -> 1 2 1 3 -> 1 2 1 4 -> 1 2 2 1 -> 1 2 2 2 -> 2 2 2 3 -> 1 2 2 4 -> 2 2 3 1 -> 1 2 3 2 -> 1 2 3 3 -> 1 2 3 4 -> 1 2 4 1 -> 1 2 4 2 -> 2 2 4 3 -> 1 2 4 4 -> 2 3 1 1 -> 1 3 1 2 -> 1 3 1 3 -> 1 3 1 4 -> 1 3 2 1 -> 1 3 2 2 -> 1 3 2 3 -> 1 3 2 4 -> 1 3 3 1 -> 1 3 3 2 -> 1 3 3 3 -> 3 3 3 4 -> 1 3 4 1 -> 1 3 4 2 -> 1 3 4 3 -> 1 3 4 4 -> 1 4 1 1 -> 1 4 1 2 -> 1 4 1 3 -> 1 4 1 4 -> 1 4 2 1 -> 1 4 2 2 -> 2 4 2 3 -> 1 4 2 4 -> 2 4 3 1 -> 1 4 3 2 -> 1 4 3 3 -> 1 4 3 4 -> 1 4 4 1 -> 1 4 4 2 -> 2 4 4 3 -> 1 4 4 4 -> 4
これらの総和を取ります。
1 1 1 -> 1 sum = 1 1 1 2 -> 1 sum = 2 1 1 3 -> 1 sum = 3 1 1 4 -> 1 sum = 4 1 2 1 -> 1 sum = 5 1 2 2 -> 1 sum = 6 1 2 3 -> 1 sum = 7 1 2 4 -> 1 sum = 8 1 3 1 -> 1 sum = 9 1 3 2 -> 1 sum = 10 1 3 3 -> 1 sum = 11 1 3 4 -> 1 sum = 12 1 4 1 -> 1 sum = 13 1 4 2 -> 1 sum = 14 1 4 3 -> 1 sum = 15 1 4 4 -> 1 sum = 16 2 1 1 -> 1 sum = 17 2 1 2 -> 1 sum = 18 2 1 3 -> 1 sum = 19 2 1 4 -> 1 sum = 20 2 2 1 -> 1 sum = 21 2 2 2 -> 2 sum = 23 2 2 3 -> 1 sum = 24 2 2 4 -> 2 sum = 26 2 3 1 -> 1 sum = 27 2 3 2 -> 1 sum = 28 2 3 3 -> 1 sum = 29 2 3 4 -> 1 sum = 30 2 4 1 -> 1 sum = 31 2 4 2 -> 2 sum = 33 2 4 3 -> 1 sum = 34 2 4 4 -> 2 sum = 36 3 1 1 -> 1 sum = 37 3 1 2 -> 1 sum = 38 3 1 3 -> 1 sum = 39 3 1 4 -> 1 sum = 40 3 2 1 -> 1 sum = 41 3 2 2 -> 1 sum = 42 3 2 3 -> 1 sum = 43 3 2 4 -> 1 sum = 44 3 3 1 -> 1 sum = 45 3 3 2 -> 1 sum = 46 3 3 3 -> 3 sum = 49 3 3 4 -> 1 sum = 50 3 4 1 -> 1 sum = 51 3 4 2 -> 1 sum = 52 3 4 3 -> 1 sum = 53 3 4 4 -> 1 sum = 54 4 1 1 -> 1 sum = 55 4 1 2 -> 1 sum = 56 4 1 3 -> 1 sum = 57 4 1 4 -> 1 sum = 58 4 2 1 -> 1 sum = 59 4 2 2 -> 2 sum = 61 4 2 3 -> 1 sum = 62 4 2 4 -> 2 sum = 64 4 3 1 -> 1 sum = 65 4 3 2 -> 1 sum = 66 4 3 3 -> 1 sum = 67 4 3 4 -> 1 sum = 68 4 4 1 -> 1 sum = 69 4 4 2 -> 2 sum = 71 4 4 3 -> 1 sum = 72 4 4 4 -> 4 sum = 76 ans = 76
答えは76と求まりました。
ではここで少し観察として、最大公約数が2か4となっているものだけを抽出してみたいと思います。
2 2 2 -> 2 2 2 4 -> 2 2 4 2 -> 2 2 4 4 -> 2 4 2 2 -> 2 4 2 4 -> 2 4 4 2 -> 2 4 4 4 -> 4
当たり前ですが、各項は2の倍数のみで構成されています。
はい。ここで取り出したものは「最大公約数が2の倍数であるもの」たちです。
この「最大公約数が2の倍数であるもの」たちの個数は計算によって求められます。
前提として、各項は必ず2の倍数でないといけません。K(=4)以下で2の倍数となるものはK/2=4/2=2個です。3の倍数であるものを計算したいときはK/3=4/3=1個となってくれて、実装時にはint型でそのまま割り算してよいです。
項の候補が2通りしかないことが分かりましたので、構成されうる数列の数は2N=23=8個ということが分かります。
ここで「最大公約数が2の倍数」ではなく「最大公約数が2である」数列の個数を数える方法を考えます。
なぜなら、最大公約数がpである数列の個数が分かっているとその部分の総和は簡単に求められるようになるからです。
この部分が解説pdfで言っている
そこで、1≦X≦Kに対して「gcd(A1,...,AN)=Xとなる数列{Ai}がいくつあるか?」という問題を考えます。これが解ければ元の問題にも答えることが出来ます。
の部分にあたります。
では、「最大公約数が2である」数列の個数を考えましょう。
先の計算では「最大公約数が2の倍数」である数列の個数を簡単に求めることが出来ました。しかしこれは2の他にも最大公約数が4である数列も含まれています。
「2の倍数」を数えることが出来たので当然「4の倍数」の数も数えることができるはずです。
(K/4)N=(4/4)3=1より1個です。上でいう、{4,4,4}がそれに該当しますね。
この数を「2の倍数」から引くことで無事「最大公約数が2である」数列の個数が求まりました。
実装
まず、「最大公約数がiの倍数となる」数列の個数を数えます。
大きな数での計算になるので繰り返し二乗法を利用します。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; int N,K; long ans; //繰り返し二乗法 //a^n mod m を返す long power(long a, long n, long m) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % m) { if (n % 2 == 1) { ret = ret * a % m; } } return ret; } main() { cin>>N>>K; for(int i=1;i<=K;i++) { long cnt=(power(K/i,N,mod)%mod+mod)%mod;
main関数の中のfor文に注目してください。int i=1;i<=K;i++と小さい数から始めています。
しかしこれでは、例えば「2の倍数」の数を求めたとしても「4、6、8、、、の倍数」の個数が分かっていないので引き算のしようがなく「2のみ」の個数が求められません。
ここで解決策としてループを小さい数からではなく大きい数つまりi=Kから始めます。
先のサンプルの場合、
i=4から始めることとなります。
「最大公約数が4の倍数」となる個数は1個と簡単に計算できました。この時、引き算する分はあるでしょうかありません。なぜなら一番大きい数字だからです。4の倍数である8や12はここでは登場しません。つまりここで計算した「最大公約数が4の倍数」である個数はすなわち「最大公約数が4である」数列の個数であると言えるのです。引き算せずにこのままansに足してあげてよいです。
ですが、この4の約数である2は引き算する必要がありました。「4の倍数」分です。
なので、このi=4の時点でその約数である2に引き算する分を配列として残して置きましょう。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; int N,K; long ans; vector<long> X(100100); //引き算する分を保存する配列 //繰り返し二乗法 //a^n mod m を返す long power(long a, long n, long m) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % m) { if (n % 2 == 1) { ret = ret * a % m; } } return ret; } //nの約数をpush_backしたvectorを返す vector<long> divisor(long n) { vector<long> res; for(long i = 1; i * i <= n; i++) { if(n % i == 0) { res.push_back(i); if(i * i != n) res.push_back(n / i); } } sort(res.begin(), res.begin()); return res; } main() { cin>>N>>K; for(int i=K;i>0;i--) //Kからの降順にした { //X[i]が引き算する分 //i=Kでは当然X[i]=0 long cnt=((power(K/i,N,mod)-X[i])%mod+mod)%mod; //最大公約数がiである数列の個数がcnt個と分かった ans=(ans+i*cnt+mod)%mod; vector<long> d=divisor(i); //約数の子たちのために引き算する分を教えてあげている for(auto &it : d)X[it]=(X[it]+cnt+mod)%mod; } cout<<ans<<endl; }
配列としてvector
ここに例えばi=4の時にはその個数を約数2の部分に入れるということをします。
X[2]+=cnt
これが i-- されていってi=2となったときに引き算されるというわけです。
コード自体はとりあえずこれにて完成です。
ここまでお読み頂いた方ありがとうございました。
E - Sum of gcd of Tuples (Hard)
問題概要
入力N、Kが与えられる。
1以上K以下の整数からなる長さNの数列Aについて、考えられる全てのAのgcd{A_1, A_2,...,A_N}の総和を求めさせる問題。
サンプル1
3 4
という入力であった場合(N=3、K=4)
数列は項数が3個で、各項は1or2or3or4となる。
例えば{1、1、2}や{2、3、1}や{4、4、3}が考えられる。
そして各数列に対して各項の最大公約数を求めたい。
まず考えうる全ての数列を列挙してみる。
1 1 1 1 1 2 1 1 3 1 1 4 1 2 1 1 2 2 1 2 3 1 2 4 1 3 1 1 3 2 1 3 3 1 3 4 1 4 1 1 4 2 1 4 3 1 4 4 2 1 1 2 1 2 2 1 3 2 1 4 2 2 1 2 2 2 2 2 3 2 2 4 2 3 1 2 3 2 2 3 3 2 3 4 2 4 1 2 4 2 2 4 3 2 4 4 3 1 1 3 1 2 3 1 3 3 1 4 3 2 1 3 2 2 3 2 3 3 2 4 3 3 1 3 3 2 3 3 3 3 3 4 3 4 1 3 4 2 3 4 3 3 4 4 4 1 1 4 1 2 4 1 3 4 1 4 4 2 1 4 2 2 4 2 3 4 2 4 4 3 1 4 3 2 4 3 3 4 3 4 4 4 1 4 4 2 4 4 3 4 4 4
そして各数列に対して各項の最大公約数を求めます。
1 1 1 -> 1 1 1 2 -> 1 1 1 3 -> 1 1 1 4 -> 1 1 2 1 -> 1 1 2 2 -> 1 1 2 3 -> 1 1 2 4 -> 1 1 3 1 -> 1 1 3 2 -> 1 1 3 3 -> 1 1 3 4 -> 1 1 4 1 -> 1 1 4 2 -> 1 1 4 3 -> 1 1 4 4 -> 1 2 1 1 -> 1 2 1 2 -> 1 2 1 3 -> 1 2 1 4 -> 1 2 2 1 -> 1 2 2 2 -> 2 2 2 3 -> 1 2 2 4 -> 2 2 3 1 -> 1 2 3 2 -> 1 2 3 3 -> 1 2 3 4 -> 1 2 4 1 -> 1 2 4 2 -> 2 2 4 3 -> 1 2 4 4 -> 2 3 1 1 -> 1 3 1 2 -> 1 3 1 3 -> 1 3 1 4 -> 1 3 2 1 -> 1 3 2 2 -> 1 3 2 3 -> 1 3 2 4 -> 1 3 3 1 -> 1 3 3 2 -> 1 3 3 3 -> 3 3 3 4 -> 1 3 4 1 -> 1 3 4 2 -> 1 3 4 3 -> 1 3 4 4 -> 1 4 1 1 -> 1 4 1 2 -> 1 4 1 3 -> 1 4 1 4 -> 1 4 2 1 -> 1 4 2 2 -> 2 4 2 3 -> 1 4 2 4 -> 2 4 3 1 -> 1 4 3 2 -> 1 4 3 3 -> 1 4 3 4 -> 1 4 4 1 -> 1 4 4 2 -> 2 4 4 3 -> 1 4 4 4 -> 4
これらの総和を取ります。
1 1 1 -> 1 sum = 1 1 1 2 -> 1 sum = 2 1 1 3 -> 1 sum = 3 1 1 4 -> 1 sum = 4 1 2 1 -> 1 sum = 5 1 2 2 -> 1 sum = 6 1 2 3 -> 1 sum = 7 1 2 4 -> 1 sum = 8 1 3 1 -> 1 sum = 9 1 3 2 -> 1 sum = 10 1 3 3 -> 1 sum = 11 1 3 4 -> 1 sum = 12 1 4 1 -> 1 sum = 13 1 4 2 -> 1 sum = 14 1 4 3 -> 1 sum = 15 1 4 4 -> 1 sum = 16 2 1 1 -> 1 sum = 17 2 1 2 -> 1 sum = 18 2 1 3 -> 1 sum = 19 2 1 4 -> 1 sum = 20 2 2 1 -> 1 sum = 21 2 2 2 -> 2 sum = 23 2 2 3 -> 1 sum = 24 2 2 4 -> 2 sum = 26 2 3 1 -> 1 sum = 27 2 3 2 -> 1 sum = 28 2 3 3 -> 1 sum = 29 2 3 4 -> 1 sum = 30 2 4 1 -> 1 sum = 31 2 4 2 -> 2 sum = 33 2 4 3 -> 1 sum = 34 2 4 4 -> 2 sum = 36 3 1 1 -> 1 sum = 37 3 1 2 -> 1 sum = 38 3 1 3 -> 1 sum = 39 3 1 4 -> 1 sum = 40 3 2 1 -> 1 sum = 41 3 2 2 -> 1 sum = 42 3 2 3 -> 1 sum = 43 3 2 4 -> 1 sum = 44 3 3 1 -> 1 sum = 45 3 3 2 -> 1 sum = 46 3 3 3 -> 3 sum = 49 3 3 4 -> 1 sum = 50 3 4 1 -> 1 sum = 51 3 4 2 -> 1 sum = 52 3 4 3 -> 1 sum = 53 3 4 4 -> 1 sum = 54 4 1 1 -> 1 sum = 55 4 1 2 -> 1 sum = 56 4 1 3 -> 1 sum = 57 4 1 4 -> 1 sum = 58 4 2 1 -> 1 sum = 59 4 2 2 -> 2 sum = 61 4 2 3 -> 1 sum = 62 4 2 4 -> 2 sum = 64 4 3 1 -> 1 sum = 65 4 3 2 -> 1 sum = 66 4 3 3 -> 1 sum = 67 4 3 4 -> 1 sum = 68 4 4 1 -> 1 sum = 69 4 4 2 -> 2 sum = 71 4 4 3 -> 1 sum = 72 4 4 4 -> 4 sum = 76 ans = 76
答えは76と求まりました。
ではここで少し観察として、最大公約数が2か4となっているものだけを抽出してみたいと思います。
2 2 2 -> 2 2 2 4 -> 2 2 4 2 -> 2 2 4 4 -> 2 4 2 2 -> 2 4 2 4 -> 2 4 4 2 -> 2 4 4 4 -> 4
当たり前ですが、各項は2の倍数のみで構成されています。
はい。ここで取り出したものは「最大公約数が2の倍数であるもの」たちです。
この「最大公約数が2の倍数であるもの」たちの個数は計算によって求められます。
前提として、各項は必ず2の倍数でないといけません。K(=4)以下で2の倍数となるものはK/2=4/2=2個です。3の倍数であるものを計算したいときはK/3=4/3=1個となってくれて、実装時にはint型でそのまま割り算してよいです。
項の候補が2通りしかないことが分かりましたので、構成されうる数列の数は2N=23=8個ということが分かります。
ここで「最大公約数が2の倍数」ではなく「最大公約数が2である」数列の個数を数える方法を考えます。
なぜなら、最大公約数がpである数列の個数が分かっているとその部分の総和は簡単に求められるようになるからです。
この部分が解説pdfで言っている
そこで、1≦X≦Kに対して「gcd(A1,...,AN)=Xとなる数列{Ai}がいくつあるか?」という問題を考えます。これが解ければ元の問題にも答えることが出来ます。
の部分にあたります。
では、「最大公約数が2である」数列の個数を考えましょう。
先の計算では「最大公約数が2の倍数」である数列の個数を簡単に求めることが出来ました。しかしこれは2の他にも最大公約数が4である数列も含まれています。
「2の倍数」を数えることが出来たので当然「4の倍数」の数も数えることができるはずです。
(K/4)N=(4/4)3=1より1個です。上でいう、{4,4,4}がそれに該当しますね。
この数を「2の倍数」から引くことで無事「最大公約数が2である」数列の個数が求まりました。
実装
まず、「最大公約数がiの倍数となる」数列の個数を数えます。
大きな数での計算になるので繰り返し二乗法を利用します。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; int N,K; long ans; //繰り返し二乗法 //a^n mod m をO(logm)で返す long power(long a, long n, long m) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % m) { if (n % 2 == 1) { ret = ret * a % m; } } return ret; } main() { cin>>N>>K; for(int i=1;i<=K;i++) { long res=(power(K/i,N,mod)%mod+mod)%mod;
main関数の中のfor文に注目してください。int i=1;i<=K;i++と小さい数から始めています。
しかしこれでは、例えば「2の倍数」の数を求めたとしても「4、6、8、、、の倍数」の個数が分かっていないので引き算のしようがなく「2のみ」の個数が求められません。
ここで解決策としてループを小さい数からではなく大きい数つまりi=Kから始めます。
先のサンプルの場合、
i=4から始めることとなります。
「最大公約数が4の倍数」となる個数は1個と簡単に計算できました。この時、引き算する分はあるでしょうかありません。なぜなら一番大きい数字だからです。つまりここで計算した「最大公約数が4の倍数」である個数はすなわち「最大公約数が4である」数列の個数であると言えるのです。
ですが、この4の約数である2は引き算する必要がありました。「4の倍数」分です。
なので、このi=4の時点でその約数である2に引き算する分を配列として残して置きましょう。
#include<bits/stdc++.h> using namespace std; const int mod=1000000007; int N,K; long ans; vector<long> X(100100); //引き算する分を保存する配列 //繰り返し二乗法 //a^n mod m をO(logm)で返す long power(long a, long n, long m) { long ret = 1; for (; n > 0; n >>= 1, a = a * a % m) { if (n % 2 == 1) { ret = ret * a % m; } } return ret; } //nの約数をpush_backしたvectorを返す vector<long> divisor(long n) { vector<long> res; for(long i = 1; i * i <= n; i++) { if(n % i == 0) { res.push_back(i); if(i * i != n) res.push_back(n / i); } } sort(res.begin(), res.begin()); return res; } main() { cin>>N>>K; for(int i=K;i>0;i--) //Kからの降順にした { long res=((power(K/i,N,mod)-X[i])%mod+mod)%mod; ans=(ans+res*i+mod)%mod; vector<long> d=divisor(i); for(auto &it : d)X[it]=(X[it]+res+mod)%mod; //約数の子たちのために引き算する分を教えてあげる } cout<<ans<<endl; }
aaaa
D - Candy Distribution
こちらの問題です。
AtCoder Tagsのmap問題を埋めていてこの問題が難しかったので記事にしておきます。
問題概要
与えられた大きさNの数列Aのある範囲の総和を考えます。
この総和が自然数Mの倍数である範囲の取り方の個数を求めてください。
というような問題です。
制約
1≦N≦105
2≦M≦109
1≦A_i≦109
解法
愚直に全ての部分和を考えられれば一番楽ですが、その場合、O(n2)となるため間に合いません。累積和を考えます。
詰まります
今回のようなABC-D問題に挑戦するような人であれば累積和までの発想はそう難しくはないと思います。が、そこまでで自分は詰まりました。
参考URL
こういう時はだいたい「アルゴリズム けんちょん」で検索すると助かることが多いです。今回も「累積和 けんちょん」で検索しました。(けんちょんさんいつもありがとうございます。)
std::mapを使うことによって累積和問題の実装をより簡単にしています。
助かりませんでした
mapを使うところまではいいのですが、その先の実装までたどり着くことが出来ませんでした解説を読みます。
数列 A に対し、A の先頭 i 項の和を Bi とします。なお、便宜上 B0 = 0 としておきます。
いま、Al +...+Ar = Br −Bl−1 であり、Al +...+Ar が M の倍数であることは Br, Bl−1 を M で割ったあまりが等しいことと同値です。 よって、数えるべきは、Bi, Bj が mod M で等しいような 0 ≤ i < j ≤ Nの組の個数です。
解説では累積和配列をBとしています。
部分和が累積和配列の項の差で求められるのだから、部分和がMの倍数であるかどうかについては、累積和配列の各項のmod Mを求めて一致しているかを調べればよい、というわけです。
実装
//入力 int n,m; cin>>n>>m; vector<long> a(n); for(int i=0;i<n;i++)cin>>a[i]; //累積和 vector<long> b(n+1,0); for(int i=0;i<n;i++)b[i+1]=b[i]+a[i]; //累積和の各項のmodをとる vector<long> mod(n+1); for(int i=0;i<n+1;i++)mod[i]=b[i]%m;
これでmodが取れました。
入力例2を入れると下記のようになります。
13 17 //入力 29 7 5 7 9 51 7 13 8 55 42 9 81 //入力 0 29 36 41 48 57 108 115 128 136 191 233 242 323 //累積和の出力 0 12 2 7 14 6 6 13 9 0 4 12 4 0 //累積和のmod 17の出力
累積和のmodの配列第2項に注目します。
第2項は12です。また、mod 17が12となる項はもう1つありますので、こことの差を取ってやることで17の倍数となる部分和が作れそうです。ans++
できます。
mod 17が0となる場合にはどうでしょうか。3つあります。
第1、10、14項がそれにあたります。この時、1と10、10と14、14と1の累積和の差を取ってやることで部分和が作れることになります。ans+=3
です。
このように共通のmodの個数を数えてその個数からansに足していけばよいということが分かります。
いくつ足すかについてはこれはnC2つまりn*(n-1)/2を足してやればよいです。
これをstd::mapを使うことで実装します。
map<long,long> M; //小文字mだと入力と被る for(int i=0;i<n+1;i++)M[mod[i]]++; long ans=0; for(auto it : M)ans+=it.second*(it.second-1)/2; cout<<ans<<endl;
ここまでのコードをくってつければACします。
mapはかなり実用的なコンテナだとは思いますが、現状あまりスマートに使えた覚えがないのでもう少し勉強をしたいと思います。
ここまでお読みいただいた方ありがとうござました。