かわわんの色々

気になったこと色々

Trinity fieldを弾きました

めっちゃかっこいいけど難しい．

動画と楽譜

ニコニコさん最近頑張ってるのでyoutube並みの画質が出てますねぇ．いいぞ．

MIDIはこれ．

Trinity_Field.pdf - Google ドライブ

楽譜はこれ．鍵盤楽器経験者デレステPは是非DLして弾いて遊んでみてください．

目次

アレンジ小話

この曲，大変難しかったですね...

まぁこのアレンジ作ったの僕なんですけども()

オーディオインターフェースの音量ミスった話

INPUTのつまみがほぼ最大で，そりゃ音割れするわｗ，って感じですよ．

せっかく割といいテイクが録れてたっていうのに...

イントロが一番難しい

最初の無伴奏のところ以外全部難しいんですけど，特に難しいのがイントロ．

f:id:kebobokawawan:20180527212321p:plain

13小節目から15小節目まで．

Prestoというのは音楽用語で「とても早く」という意味です．

BPMでいえば190くらいでしょうか．

さて上の画像の黄色の部分ですが，

ここは片手で弾かないといけないので1，2，3の指でこの和音を押さえます．

1，2，3の指とはすなわち親指，人差し指，中指のことです．

指の力が足りないと弾けない上に早く弾くと人差し指と中指の間が悲鳴を上げます．

あなたは人差し指と中指を8cm以上開くことができますか？

つまりそういうことです．

f:id:kebobokawawan:20180527213157p:plain

16小節目

ここはG#マイナーの和音の展開形を素早く弾く形になるのですが，

ここもかなり音を外しやすいですね．

あっ，ドのナチュラルではなくてシのシャープですね...．

f:id:kebobokawawan:20180527213819p:plain

20小節目ですが，ここの左手のG#はきちんと2拍お休みしましょう．ペダルも離しましょう．

だらだらと音が伸びてダサくなっちゃいます．

ここも，ドのナチュラルではなくてシのシャープですね...．

f:id:kebobokawawan:20180527214031p:plainf:id:kebobokawawan:20180527214103p:plain

24小節目から27小節目です．イントロで一番盛り上がるとこですね．MVでのここの部分のダンスがくねくねしててかわいいです．

何気なく音符が並んでいますが，左は10度のアルペジオが最初に二発あって，

二拍ごとにコードが変わる上に，右手の指使いも少し練習が必要です．

f:id:kebobokawawan:20180527215002p:plainf:id:kebobokawawan:20180527215007p:plain

28小節目から31小節目です．

黄色で塗ったところが左手で弾くところです．

ベースの全音符はペダルで伸ばします．

右手の8分音符のG#の音を強く弾いてはいけません．

ここは声部が4つに分かれていて，最も高いのは右手の8分音符の奇数番目の音です．

その次に高いのは右手の右手の8分音符の偶数番目の音です．G#です．

それより一つ低い声部が左の旋律です．

最も低いのが左手の全音符です．

サビ前

f:id:kebobokawawan:20180527220233p:plain

少し飛んで63小節目です．サビ直前のアルペジオです．

アルペジオをオクターブで弾いているので右腕が死にます．

特に最初の2音は11度，長さにして約23cmの跳躍です．

次に弾く鍵盤の位置をきちんと目視しましょう．

64小節目のミのナチュラルで転調します．ここも外しやすい音です．目視しましょう．

65小節目からサビです．ここの1拍目もちゃんと目視しないとミスります．

跳躍が多い時はちゃんと目で鍵盤を見ようって思いました．

サビ終わり

f:id:kebobokawawan:20180527220941p:plain

76小節目から80小節目まで．左手が跳躍しています．

ここもちゃんと目で鍵盤を見ましょう．

実際弾いてるときは左手ガン見ですが右手はほぼ視界に入っていなかったですね．

ラスト

f:id:kebobokawawan:20180527221357p:plainf:id:kebobokawawan:20180527221402p:plain

85小節目からラストまで．

右手がめっちゃ頑張るところです．

しかし，音の種類が少ないので慣れたら易しいです．右腕を円を描くようにすれば勝手に弾けます．

練習

全体的に難しいです．

跳躍が激しい所は次に弾く鍵盤をきちんと目視しましょう．

「ここ弾けねぇ」って部分はそこだけゆっくり練習するのです．

また通し練習は「テンポをゆっくりにしてでも絶対にミスらないように通す」ことを意識しましょう．(自戒)

成功体験が体に刻み込まれます．

感想

Trinity Field，よくこんな曲作れるよなぁ．すげえ．ありがとうございます．

次弾く曲はあれですね，何弾くかわかんないですけど，易しめのアレンジをしたい．

ABC096 C Grid Repainting2

競技プログラミング Python3

なんか似たようなやつRUPCでも解いたなぁとか思いました．

メモです．言語はPython3です．

問題概要

これみて

C - Grid Repainting 2

解法

まぁ#があるとこの上下左右のいずれかに#があればいいんですけど，どう実装すればいいのか分かんなかったですねー

実装

端っこどうしよっかなーつって悩んだんですが，他の皆さんのコードを見て勉強しました．

field = [] #ここに行列が入る
flag = "Yes"

"""中略"""

"""for文の中"""
if field[i][j] == "#":
    if i != 0 and field[i-1][j] == "#": continue  # 左見てる
    elif i != w-1 and field[i+1][j] == "#": continue  #右見てる
    elif j != 0 and field[i][j-1] == "#": continue  #上見てる
    elif j != h-1 and field[i][j+1] == "#":continue   #下見てる
    else: flag = "No"
"""for文終わり"""

print(flag)

問題によって端っこをどう処理するかは変わるとは思うんですけど，

こう書けばいいのか―と初心者的には勉強になったのでメモした次第です．

キラッ！満開スマイルを弾きました

音楽

こんにちは～．デレステのイベント曲「キラッ！満開スマイル」を弾きました！

 

 

今回は楽譜をMIDITrailというソフトを使って楽譜が読めない人でも分かるようにしました．

 

 

 目次

楽譜

キラッ！満開スマイル.pdf - Google ドライブ

今回も楽譜を用意しました．ご自由にDLしてください．

ピアノアレンジ的小話

左手の跳ねているリズム

その１

f:id:kebobokawawan:20180402163657p:plain 楽譜的には見た目あんまり難しくなさそうですけど，両手で弾くと結構しんどかったところです．曲的には前奏が終わってすぐのあたりですね．

リズムの取り方が分からなくなる時は口で実際にリズムを歌うとよいです．

この画像の黄色の部分は

「タッ　タタッ　タターン」

というリズムの繰り返しですね．裏打ちが多くて分かりにくい．

左手てで

「タン　タン　タン　タン」

とリズムを刻みながら

右手で

「タッ　タタッ　タターン」

とリズムを刻んでみると何やってるのかたぶん結構わかるんじゃないでしょうか．

その2

f:id:kebobokawawan:20180402164436p:plain ここはその１の直後ぐらいですね.

「(ﾊﾟﾊﾟﾔ)まだ風が冷たいね～♪」

とあんずちゃんが歌ってるあたりです．

普通なら全部８分音符にして

「ソ↓レソ↑レ　ソ↓レソ↑レ　ソ↓レソ↑レ　ソ↓レソ↑レ　　 ド↓ソド↑ソ　ド↓ソド↑ソ　ド↓ソド↑ソ　ド↓ソド↑ソ」

ってやればいいんですけど(伝われ)，

符点四分音符とか使って裏拍意識した感じにしてます．

リズムに乗って体が左右に揺れる感じです．

ピアノを習っている人なんかはよく「タテの流れとヨコの流れ」を意識して弾きなさいと言われるんですが，

ここは完全に「ヨコの流れ」を意識すべきところですね．

なんというか，歌(主旋律・メロディ)の滑らかさを意識して，まさしく「歌うように」弾きたいんですよね．

そんな時にベースが８分音符とかでごりごりにリズムを刻んでしまうと「いや～，きついっす」という感情がわいちゃいます．

その3

f:id:kebobokawawan:20180402165612p:plain

サビです．

ここも楽譜が真っ黒じゃないし全然難しくなさそうですが，１オクターブずつ計２オクターブの跳躍が８分のリズムであるので結構左手が忙しいです．

動画サビのところの左手を確認してもらえてら忙しそうにしてるのが分かると思います．

(カメラアングル的にわかりにくいかもですが)

サビなのでやはり盛り上げたいわけなのですが，そういときはオクターブめっちゃ使います．

オクターブだけでも派手なのにそれをぴょんぴょん跳躍させているのでもっと派手になります．

よってサビの力強いメロディーに合う伴奏になるなぁという感じです．

キラッ！のところ

f:id:kebobokawawan:20180402170252p:plain

ここ右手を素早く動かせばだれでも弾けるのですが，

こういうやつこそきちんとした拍の長さで弾かないとめっちゃダサくなります．

「タテの流れ」を意識しましょう．

すなわち，ちゃんと楽譜通りの拍の長さで鍵盤を押さえましょうという意味です．

また，「キラッ」の「ラッ」の音が弱く聞こえちゃいがちです．

これも超ダサいです．

指遣い的に薬指がこの「ラッ」の音を弾くんですが，この指はもともと力が弱く，

尻すぼみな音になりがちです．

練習法

右手は正直メロディをなぞっているだけなので難しいことはあまりないです．

左手は左手でリズムが独特ですが，片手だけでやるならそこまで難しくはないです(簡単ということではない)．

両手同時に弾くのが結構つらいです．

それぞれの手のリズムを体に叩き込んで，

「「「絶対に失敗しないくらいの超ゆっくりなテンポ」」」

で練習してみましょう．

RUPC2018に参加しました。

競技プログラミング その他

初参加でした。というか同じ大学の人間なのに春休みに入るまでRUPCの存在知らなかったです。

 

一日目

バイトの関係で出席してません。B問題がなんか難しかったと聞きましたがまだ見てないです。

 

二日目

A,C,F問題を書きました。

後で調べて初めて知ったんですがCみたいなやつをナップザック問題っていうんですねぇ。

 

Fはチームメイトの方に色々と教えてもらって、頑張って場合分けしました。

 

解説フェイズに入って聞いていたんですが「何言ってるのか全然分からねえ」となりました。

 

atcoderのC問題くらいなら通せるようになってきたしそろそろ基本的なアルゴリズムとかも学んで行きたいな〜、と。

 

次回もし参加できるなら、次は話について行けるように頑張って行きましょう。

 

懇親会は同大学の人たちと同じ席になったのであまり交流を広げられなかった感。

 

ミドリムシさんが同じ席だったけど年齢を知ってビビったりするなど。行動力高えなー。

 

三日目

nadareさんとbeetさんとチームでした。

 

A,Cを書きました。

 

Cはもうnadareさんにおんぶにだっこでした。

さらにPythonのcollectionモジュール便利だよと教えてもらいました。

 

beetさんからはDPの考え方について教えてもらって、チームメイトのお二方には圧倒的感謝という感じです。

 

感想

教えてもらってばっかですねぇ。ありがたみの深さがマリアナ海溝です。忘れないうちに復習しなきゃね。

 

次回も参加できそうなら参加したいなー。

 

 

 

夏休みと後期を振り返る会

その他

人間一年前のことは忘れていても半年前のことは案外覚えてる。(?)

 

後期テストも終わったので夏休みくらいから振り返りをば

 

8月

基礎論サマースクール

基礎論サマースクールに参加した。計算論に出会い「やっばこれめっちゃ面白いやん」となった。先輩の玲於奈さんのお家に泊めてもらった。ありがとうございます。そのついでに御茶ノ水で古本屋めぐったり秋葉原を観光したりした。

数学基礎論サマースクール2017

 

バイト

バイトが大量に入った。まあ、お勉強教えるバイトだし夏休みだしそうなるよね。(お仕事あるのはありがたい)

 

弾いてみた動画

ニコニコ動画、YouTubeに初めて演奏動画をアップロードした。とりあえず聞いてほしいです。ありがとうございます。

nico.ms

ピアノアレンジはまだまだストックがあるのでしばらくは投稿頑張れそうです。

tex勉強会

サークルで(la)texの勉強会をした。texの仕組みやlatexとの違いを述べて、実際にlatexの練習をしてもらった。今後も使えるいい感じの資料ができたのでは？

untitled-1.pdf - Google ドライブ

数物セミナー予習

それ以外は数物セミナーの予習をしていた。辛い辛いと言いながら予習を進めてたがこれがあったからこそ、今測度論を理解できていると言ってもいいくらい。

9月

数物セミナー

数物セミナーに参加した。

数物セミナー

班員みんなやさしくて楽しく議論できた。前回参加したときより周りの参加者が話してる内容についていけたし、ちゃんとセミナーもできたしルベーグ積分もだいぶ理解できたし実りの多いものになりました。もう感謝しかねえ。ちなみに場所は福島県の白河。ラーメンが有名らしく、ラーメン屋だらけだった。数物セミナー終わったあとは白河駅を探索して白河ラーメン食べました。

 ここで完全に夏休みの気力を使い果たした。

Remakers合宿

Remakers(立命館理系自主ゼミサークル)の合宿に参加した。集合論から始めて位相空間論のゼミをした。順序集合のことがあまり理解できていなかった気がしてたのでその辺りのことを発表した。しかし、予習もおざなりだったし微妙な感じに終わった。この合宿で『モテる男のための音楽理論講座入門』とかいうタイトルで発表した。どんな内容だったかはスライドおいておくので見てね♡

もておと.pdf - Google ドライブ

9月はこれ以外あんまり記憶がない。

10月

後期が始まった。

プログレセッション

プログレッシブロック限定のセッションライブイベントがあり、そこでELPのTarkusを演奏することに。どんな曲なのかは聞いてみて。


Tarkus - Emerson, Lake & Palmer [1971] (HD)

古い曲だし楽譜落ちてないかなと思って調べたら落ちてました。これでも助かってなくて、テクニック的に非常に難しい。僕が演奏を録音したものを置いておきます。「実はMIDI入力で後でうまく行くように編集した」とか言う甘いことはしてないです。生演奏です。 soundcloud.com

計算論の入門書

エフィーム・キンバー著の『計算論への入門』を読んだ。電車の中でのパラ読みでも雰囲気がつかめるいい本でした。

計算論への入門―オートマトン・言語理論・チューリング機械 (スタンダードテキスト)

計算論への入門―オートマトン・言語理論・チューリング機械 (スタンダードテキスト)

セミナー

数研で数理論理学セミナーと線形代数セミナーが始まった。数理論理学セミナーは鹿島先生の『数理論理学』を、線形代数セミナーは斉藤先生の『線形代数入門』を読んだ。

数理論理学 (現代基礎数学)

数理論理学 (現代基礎数学)

線型代数入門 (基礎数学1)

線型代数入門 (基礎数学1)

ディープラーニング

RCCでディープラーニング班に参加した。内容は『0からできる！(略)ディープラーニング』を輪読しながら実装しようというものだった。この本ではPythonが用いられていた。そこでPythonを勉強し始めたが、これが運命の出会いだった。

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

ゼロから作るDeep Learning ―Pythonで学ぶディープラーニングの理論と実装

暗号通貨

暗号通貨を始めた。Kindleでセールになっていた暗号通過について簡単にまとめられている本を読んだ。初めてbtcを買って数分待ってると20円分増えた。「これが投資ってやつか〜。いや、お金に対する考え方が変わりますねこれ」というのが第一の感想だった。

Atcoder

月末くらいに勧められてAtcoder(競技プログラミング)を始めた。プログラミングの勉強はとりあえずなにか作ってみよう！というのはよく聞きます。しかし、そういうので成功したためしがない自分にとってAtcoderはすごく合っていた。問題を解いていくことで勉強した証が残るのがモチベーションアップになった。さらに、問題を解いていくことでアルゴリズムの知識がつくし、なによりたくさんコードをかける。そして問題に正解すると純粋に嬉しい。そうして暇なときでネット環境とPCがあれば競プロをするようになった。

11月

pythonの勉強

pythonと運命の出会いを果たした僕はそのあまりのわかりやすさに涙を流しながらディープラーニング班、競技プログラミング、自分で購入した参考書、グーグル先生を使いつつ勉強した。 

Kindle

kindleの良さに気づいた。暗号通貨を始めたのでお金のことも勉強しようと思った。大きめのセールがあったのでKindleでいろいろ買ってみた。結論から言うと大正解だった。読書量が格段に増えることに気づいた。ただ、専門書や教科書はKindleに向いてないなーとも思った。

正課

遅刻…

学園祭

10月に読んだ計算論の本とその他ウェブサイトなどを参考に有限オートマトンに関するLTをした。

12月　

そろそろ記憶に新しい

Remakers機関誌

Remakersに記事を投稿するよう伝えられたので、今年かなり学んだルベーグ積分について書こうと思いました。しかし、手を付けてみると理解できていないことが多かったことに気付かされました。この記事執筆で自分の理解を整理することができたので、頭の中が大分スッキリしました。

遅刻

滋賀寒すぎだし神戸が最高すぎるのが悪い…

コンテスト初参加

atcoder beginner contestに初参加しました。この当時は過去問解いてる感じB問題がかろうじてできるくらいだったので、B問題を解くことを目標にしました。なんと無事達成しました。嬉しくないわけがありません。神は私に「競プロを続けなさい…」とお告げをしているのだと思いました。

冬休みとバイト

年末年始は日本の学生は冬休みなので、当然バイトも増えます。ありがたいですね。

大学行きたくない気持ちでいっぱいだったので、冬休みに入ると逆にタスクをたくさんこなせました。

ブログ

気づいたらブログ始めていました。

敗北の少年

投稿しました。うーん、もう少し早く投稿できたよね…？ぜひ聞いてみてください♥記事も読んでみてください♥

skbtkey.hatenablog.com

1月

膝を壊した

淡路島にサイクリングのテストランをしたら左膝を壊した。3週間はまともに階段の昇降ができなくなり、現在もまだ自転車に乗れない。非常に辛い。

TOEIC

645点でした。なんと英語を履修してた2回時点での得点が605点。しかし今回は英語を履修していない。にもかかわらずあの点数！

立命館理工学部英語は一体何なんだ…

AGC020-B Ice Rink Game

僕に競プロを勧めてくれた方が「AGCに参加しては？」と言ってくれたので参加しました。そしてB問題が解けそうで解けなかったのです。悔しかったので解説読んでより詳細な説明を記事にまとめました。すると、atcoder社長の高橋さんにツイッターで言及されて少しバズりました。

skbtkey.hatenablog.com

ブログってバズるとめっちゃたくさんの人に読んでもらえるしすげえなぁと言うのが率直な感想です。

セミナー終了

数理論理学は完全性定理の途中まで終了した。これはかなりいい復習になった。学んだ内容を俯瞰すことができた。線形代数学は一回生とのセミナーだったので、ツッコミが厳しめだった。いい復習にはなったけれど、固有値の話までたどり着きたかったかな〜…

テスト勉強

大学生だし、ま、多少はね？

btc200万オーバーしたので利確した

儲けで舟木先生の『確率論』を購入しました。

確率論 講座数学の考え方 (20)

確率論 講座数学の考え方 (20)

ルベーグ積分を学んだ人ならサクサク読めると思います．私は大学の講義を聞いていても確率変数の概念がわけわかめだったのですが，この本を読んでばっちり理解しました．  

感想

なんだかんだ色々やってますね...

色々と運命の出会いが多いと感じました(小並感)

AGC020 B Ice Rink Game

Python3 競技プログラミング

skbtkey.hatenablog.com

↑こちらも読んでみてください．

AGC020 B問題について書きます．

目次！

B : Ice Rink Game

B - Ice Rink Game

問題概要

  • 子供がN人いる．
  • Kラウンドからなる「n人組作って～♪」ゲームをする．
  • 「n人組」を作ると中にはあぶれちゃう子も出てしまう．そのような子は脱落する．
  • Kラウンド終了したとき，残った子供は二人だったという．
  • あなたはこのゲームを傍から見ていたので，「このゲームが何ラウンド行われたか(Kの値)」と「各ラウンドにおいて作る『n人組』のnの値」を知っている
  • あなたはこの情報からもともといた子供の数を推測してみたくなった

答えるべきもの

  • Nの最小値と最大値
  • Nとして適切なものがない場合は-1と出力

制約

  • 1\leq K\leq 10^{5}
  • 2 \leq A_{i} \leq 10^{9} ただし，A_iとは第iラウンドにおいて作る『n人組』のnの値

解説

僕がこの問題を解いたときの思考過程をなぞりながら書きます．

具体例で考える

まずこの問題文を読んだ時に思ったのが「よくわからん」だったので，例で確認してみました．

入力例1

  1. 4

  2. 3 4 3 2

全部で4ラウンドあり，『3人組』→『4人組』→『3人組』→『2人組』の順でグループを組んでいきます．

この時，出力が

出力

  1. 6 8

でした．実際に計算してみると，f:id:kebobokawawan:20180117145911p:plain となります．確かにあっていそうです．

求めるものはNなので今度はこの例を用いて6,8を出す作業をやってみようと思いました．

Nの最小値は6だったので，6を求める作業をしていきます．

この表は各ラウンドにおいて「ラウンド終了時の子供の人数」と「ラウンド開始時の子供人数」と「作る組の人数」を表にしたものです．

赤色の文字は与えられた数値です．ゲームを開始する前は第0ラウンドということにしました． f:id:kebobokawawan:20180116225242p:plain

最終ラウンドである4ラウンド終了時の子供の人数が2なので，4ラウンド開始時には子供は2人いるか3人います．

もし，4ラウンド開始時に子供が2人いたなら，それはすなわち3ラウンドの終了時に残った子供が2人ということです．

f:id:kebobokawawan:20180117145955p:plain

しかし，これはありえません．3ラウンド終了時に残った子供が2人だけという状況がありえないからです．

3ラウンドでは『3人組』を作れという指示だったので，少なくとも3人は子供が残ります．(後の重要な伏線)

では4ラウンド開始時に子供が3人いたとしましょう．

f:id:kebobokawawan:20180117150018p:plain

これは正しいです．

では次に3ラウンド開始時(2ラウンド終了時)の子供の人数を考えてみます．候補は3人，4人，5人のいずれかになります．

f:id:kebobokawawan:20180117150037p:plain

6人以上だとすると3ラウンド終了時に6人以上残ってしまいます．

6人以上はあり得ないf:id:kebobokawawan:20180117150057p:plain

今回の場合，4人の場合のみありえます．

2ラウンドでは『4人組』を作れという指示だったので，残る子供の数は4人以上ですし，必ず4の倍数になっていないといけません．

f:id:kebobokawawan:20180117150136p:plain

こんな感じで表の数字を埋めていくと次のようになりました．f:id:kebobokawawan:20180116231752p:plain

一般的に考えてみる

具体例でこの作業をしているとこのゲームの仕組みが分かってきました．一般的に論じてみます．

f:id:kebobokawawan:20180116232708p:plain

  • 第iラウンド終了時の子供の人数をx人とすれば，xはA_iの倍数である
  • 第i-1ラウンド終了時における子供の人数はx+p人である
  • 0\leq p \leq A_i -1である．pとはx+pをA_iで割ったときの余りである．
  • x+pはA_{i-1}の倍数である

ここまで整理すると解法が浮かびました．

各第[text:i]ラウンドの子供の人数xとA_iとA_{i-1}からx+p^{(i)}として適切なp^{(i)}を全てリストアップして，その中でも最小のものをp_{min}^{(i)}として最終的には 2 + p_{min}^{(K)} + p_{min}^{(K-1)} + \cdots + p_{min}^{(1)}を計算すれば，もともといた子供の最小値が求められます．

最大値は適切なp^{(i)}のなかで最大なものを考えていくだけです．

ただし，この解法は正しい答えが出せても時間制限という壁にぶつかります．

この解法だと，プログラムは二重ループになってしまうため答えをだす制限時間である2秒をいとも簡単に超えてしまいます．

コンテストに参加しているときはこのあたりまでわかったところで時間切れになりました．

pをループ無しで求めるには

解説のpdfに書かれているのはここからの話です．しかし，式だけ書かれている感じなのでここではそれをさらに詳しく書こうと思います．

https://img.atcoder.jp/agc020/editorial.pdf

再び具体例で考える

第iラウンド終了時における子供の数として考えられる値はいくつかあるはずです．そこで第iラウンド終了時における子供の数の最小値をX_iとし最大値をY_iとします

先ほどまでと文字の使い方は同じにして，X_{i}=4,Y_{i}=8,A_i = 4,A_{i-1}=2 としてみます．

L_{i}f:id:kebobokawawan:20180117150254p:plain R_{i}f:id:kebobokawawan:20180117150226p:plain

pの候補は0,1,2,3です．それぞれの場合においてX_{i}+pは4,5,6,7でありY_{i}+pは8,9,10,11です．よって，X_{i-1}は4でありY_{i-1}は10です．

具体例だと直観的にわかってしまいますがポイントは適切なpを考える前にまずはX_{i}+pおよびY_{i}+pのとりえる値を考えているということです．

X_{i}+pの最小値をL_{i-1}とし，Y_{i}+pの最大値をR_{i-1}と置きます．

区間[L_{i-1},R_{i-1}]というのはi-1ラウンド終了時においてあり得るかもしれない子供の数になります．この区間の値でA_{i-1}の倍数となっているものを見て，その中の最小のものと最大のものを選んでそれぞれX_{i-1}，Y_{i-1}とするのです．

一般で議論する

第iラウンド終了時において子供の数の最小値をX_{i}，最大値をY_{i}とします．再び述べますが，組の数がA_{i}であるとき，第i-1ラウンドにおいてありえるかもしれない子供の数は区間[L_{i-1},R_{i-1}]で表されます．この区間でA_{i-1}の倍数である最小の数と最大の数を見つけていきます．

したがって，区間[L_{i-1},R_{i-1}]内にA_{i-1}の倍数がなければ-1を出力しなければなりません．よって，まずはこれについて判定しなければならないのですがそれは後述します．

第i-1ラウンドにおけるあり得るかもしれない子供の数は先ほどの議論より[L_{i-1},R_{i-1}]でした．この区間の中でA_{i-1}の倍数の最小値がX_{i-1}であり最大値がY_{i-1}になります．

すなわち，

\displaystyle X_{i-1} = \lceil\frac{L_{i-1}}{A_{i-1}}\rceil \times A_{i-1}

\displaystyle Y_{i-1} = \lfloor\frac{R_{i-1}}{A_{i-1}}\rfloor \times A_{i-1}

となります．

L_{i-1},R_{i-1}を構成した方法と同様にするとL_{i-2},R_{i-2}はそれぞれ，

L_{i-2} = X_{i-1}

R_{i-2} = Y_{i-1} + A_{i-1} -1

すなわち，

L_{i-2} = \lceil\frac{L_{i-1}}{A_{i-1}}\rceil \times A_{i-1}

R_{i-2} = \lfloor\frac{R_{i-1}}{A_{i-1}}\rfloor \times A_{i-1} + A_{i-1} -1

となり，添え字をずらせば，

L_{i-1} = \lceil\frac{L_{i}}{A_{i}}\rceil \times A_{i}

R_{i-1} = \lfloor\frac{R_{i}}{A_{i}}\rfloor \times A_{i} + A_{i} -1

となり，解説pdf通りの式が完成します．

ゲーム開始時，すなわち第0ラウンドにおける子供数の最小値，最大値であるX_{0}，Y_{0}は必ずL_{0}R_{0}となります．

なぜなら，第0ラウンドではA_{0} =1とみることができるからです．

したがって，L_{i}，R_{i}に関する漸化式を1からKまで回せばよいことになります．

また，Kラウンドからさかのぼっていくため，各ラウンドにおける組のデータを入れた配列は逆順にソートしておくと扱いやすいと思います．

区間[Li,Ri]内にAiの倍数があることを判定する方法

区間[L_{i},R_{i}]内のすべての数字についてA_{i}で割り切れるかどうかをチェックしていけばよい

というのが，最初に思いついた方法ですが，これもfor文でループを作らないといけないため結局全体として2重ループになります．

区間[L_{i},R_{i}]とA_{i}が与えられた時，区間[L_{i},R_{i}]内のA_{i}の倍数の有無を判定する方法で繰り返し処理を用いないものを述べます．(自力で考え付いたので書きたい)

まず

L_{i} \verb|%| A_{i}\, != 0

であるかどうかを調べます．もし，上記がTrueならば次に

L_{i} + (A_{i} - ( L_{i} \verb|%| A_{i} )) \in [L_{i},R_{i}]

になっているかどうか，すなわち

L_{i} +(A_{i} - ( L_{i} \verb|%| A_{i} )) > R_{i}

になっているかどうかを調べます．もしこれがTrueならば，区間[L_{i},R_{i}]内にA_{i}の倍数はありません．

例f:id:kebobokawawan:20180117150437p:plain

提出

紆余曲折ありましたが，以上のような議論を踏まえて私は次のようなコードを提出しました．

Submission #1983745 - AtCoder Grand Contest 020

こういうブログ書いてる暇があるならもっと他の問題を解いていきたいなって思いました．