• https://yukicoder.me/problems/no/754

問題文のサンプル１はこういう意味である。

• 3 + 2x + 2x2 + ... * 7 + 0x + 4x2 + ... = 21 + 14x + 36x2 + ...となる(2乗まで)。この係数の和(21+14+36)は61である。

つまり、(3+2+2)*7 + (3+2)*0 + (3)*4を計算すれば良いことになる。各項の左側について最初に和を取り、後ろから順番に引いていけば良い。

• https://yukicoder.me/problems/no/756
• https://yukicoder.me/problems/no/757

チャンパーノウン定数自体は既出のネタ(例：Project Euler 40)なので、基本的には以下の方針で良い(CodeIQコード銀行「n番目の数字は？」(答案)のコメントより)。

1
2
3
4
5
6
7
8

例えば1から999までは以下の様な区間に分割できる。
1 + 0〜8
10 + 0〜89
100 + 0〜899
各区間に含まれる数字の個数は9、180、2700となる。
これを1*1*9、2*10*9、3*100*9と表現する(digits*expbase*9)。
入力値が入る区間が決まったら、それより下の和を入力値から引き(nとする)、
(digits)桁の数を並べた中のn桁目を求めれば良い。

これで、ビルトイン多倍長整数を使えば10**1000程度まではACできる。ただし、今回は入力が非常に大きいため、下位から順番に処理すると多倍長演算が容易にTLEを招いてしまう(解答例のif falseの一部)。 まず、この1*1*9 + 2*10*9 + 3*100*9 + ...を高速に求めることを考える。

1
2
3
4

Sn   = 1*1*9 2*10*9 3*100*9 4*1000*9
10Sn =       1*10*9 2*100*9 3*1000*9  4*10000*9
-9Sn = 1*1*9 1*10*9 1*100*9 1*1000*9 -4*10000*9
-9Sn = (10**4-1)                     -4*10000*9

といった変形により、Si = i*10**i - (10**i-1)/9と定式化できる。これを用いて、digitsを2分探索するか上位から探索するかする。これでTLEを回避できる。

• Crystal https://yukicoder.me/submissions/300755
• Ruby https://yukicoder.me/submissions/300934

2018/3/23

確か初日にプレイしたはず。当初はLv5ですら星5(90点)取れなかったんですよ…

2018/4/2*

Extra Stage専用楽曲、完走したら解禁可能とかえぐすぎませんか…全然できないんですが…当時はDRSの反応についてよくわかってなかった(反応が悪いとすら思ったこともあります)。

2018/6/13

アンロックを進める中で、ようやくImpress易をクリアした(易を完走できれば解禁可能になり普も普通にプレイ可能になる)。 今でこそLv8の大半の曲は余裕だが、当時はLv7はかなりいっぱいいっぱいだった。がんばったわし。これでFLOWER(易がLv9)に挑戦可能になった。好きな曲だからね。 https://twitter.com/cielavenir/status/1006747633925287936

2018/7/19

この頃は音源を聴き込んでおり、77点に乗せる。しかし、この記録が破られることは3ヶ月間ないのであった… https://twitter.com/cielavenir/status/1019926097524244480

2018/10/24

あきらめつつも、全曲の解禁作業が終わり、全譜面星5埋めが佳境に差し掛かった頃。 1曲目：Mandrake普(Lv8)。リズムの刻み方が独特で、Tap/Downが8分で交互に来る箇所がある関係上個人的にLv8最難だと思う。慌てずに着実に踏むことを意識して星5が取れた。 2曲目：Garuda易(Lv9)。いつもほとんど取れない8小節があるんですが、おちついて取ることができた。これも星5。 3曲目：調子が良い気がしたので、FLOWER易行くことにした。慌てずにステップを踏み、アウトロまでlife3残した。素晴らしい。が、ここで力が抜けてミスを出し残り1、最後の左足フリックは苦し紛れに入力できました。本当に良かった。もしこの入力ミスってたらどうなっていたの…。 しかもBad10とか。Tapのミスは9個なので、Downを1個落としていたのかな…。まあアンロックするのが重要なので。いいんじゃないでしょうか–;;;なにはともあれお疲れ様でした。 http://twitter.com/cielavenir/status/1055086630783016960

2018/11/29

FLOWERを解禁した私ならKACでもそこそこ戦えるはずだ！さあ予選行くぜ無理よぅこれorz https://twitter.com/cielavenir/status/1068135718751326208

こちらやこちらで触れられているとおり、エンジニアにとってアウトプットは重要である。

問題になるのは記事の質であろう。質をいつも保つことは難しい場合もあると思う。 私の場合は、例えばWIP 意図せぬMerge Hellを防ぐが未完のまま公開された記事の例である。[^1]

そういう場合、少なくとも自分の中で形にするまでは公開すべきでないという意見も聞くが、私としては、間違った情報でない限りは公開しても良いと思う。特に少ない情報の場合は断片だけでも助かる人はいると思うし、そこから話が広がる可能性もあるからだ。

[^1] 私事だが、(弊社にはモジュールのリポジトリの他にシステムとしての管理リポジトリがあるのだが)管理リポジトリに私の個人ブランチが3個も存在している。はっきり言って糞だが、解決策がまだ見つかっていない以上しかたがない。

https://yukicoder.me/problems/no/734

解法

本文を噛み砕くと、60ax>bx+3600cなので、「直線 y=(60a-b)x-3600c がx>0でx軸と交わるx座標のceil」を求めれば良いことになります。これは傾きが正の場合のみ成立します。

不等式の評価

上にceilと書かれていますが、プログラムを書く場合と書かない場合の合計時間が等しくて良いならceil、書く場合の合計時間が小さくならなければならないならfloor+1です。条件設定って難しいorz

コメンタリー

(60a-b)x>3600cについて60a-bで両辺割ったときの不等号の向きって60a-bの符号で違ったんだっけって少し混乱した^^;;

コメンタリー2

「不等式の評価」項はコンテスト後に追記したものです。ご迷惑おかけしました(このために星1.5に上がることとなりました)

背景等

• 紫稼働時に私のレーティングは9.74から9.22に下落することとなった。これはかなり私のモチベーションを削ることとなった(笑)
• それからというもの長らく遠ざかっていたが。オンゲキやチュウニズムのレート算出プログラムを書いたので、せっかくなのでmaimaiのプログラムも書くことにした(利用権延長するために今日久々にプレイした)。内部Lvは未入力だが傾向はわかるはずだ。
• で、できたものが https://docs.google.com/spreadsheets/d/1EcodNpPUgAtNFboMd1l-8fo9TJRYsbx8Ho-vVJV-5Fs/edit?usp=sharing だ。

考察

• 実はレートが落ちた主要因はS-AAAの壁ではなく、history枠の存在であることが判明した。
• 現在のhistory枠平均は3.36であり、これはざっくりと到達可能レーティングの95%程度しかいきませんよということを意味する。全体レーティングの0.5は大きい数字である。
• 今はまだ119曲しかレート7.5に到達していないが、これを520曲で行えばレーティングは9.6程度まで回復する。
• ただ、挑戦する難易度としては、Lv11以上に挑戦するか、7〜8をSSにするかが良いようだ。Masterを解禁するには9をSにする必要も生じるだろうが、効率がよくなさそうだ。キャンペーンでMasterが期間限定解禁されているタイミングを狙ったほうが得策かもしれない。

結論

• 未プレイ291曲…？ちょっとこれはきついですね…。結果的にはますますモチベを削ることになったようですorz
• 全埋めする以外に計る方法はなかったのでしょうか…。

備忘録です(なおTHANKSの会場はこれまですべてコワーキング・スペースMONOです)

事情により必要になるかもなので貼り付けとく

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Processor    : ARMv7 Processor rev 1 (v7l)
processor : 0
BogoMIPS  : 38.40

processor : 1
BogoMIPS  : 38.40

processor : 2
BogoMIPS  : 38.40

processor : 3
BogoMIPS  : 38.40

Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt 
CPU implementer   : 0x51
CPU architecture: 7
CPU variant   : 0x2
CPU part  : 0x06f
CPU revision  : 1

Hardware  : Qualcomm MSM8974PRO-AB

SHV38もついでに

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

processor    : 0
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 1
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 2
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 3
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 4
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 5
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 6
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

processor : 7
model name    : ARMv7 Processor rev 4 (v7l)
BogoMIPS  : 38.40
Features  : swp half thumb fastmult vfp edsp neon vfpv3 tls vfpv4 idiva idivt vfpd32 evtstrm 
CPU implementer   : 0x41
CPU architecture: 7
CPU variant   : 0x0
CPU part  : 0xd03
CPU revision  : 4

Hardware  : Qualcomm Technologies, Inc MSM8952

https://yukicoder.me/problems/no/721

解法

• mktimeとlocaltime_rを使います。
• C https://yukicoder.me/submissions/277099

余談

• AOJ0261 Mayan Crucial Prediction
• http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0261
• も同様のやり方で解けます。
• (64bit限定です。初期のAOJは32bitだったため通らないのですがご愛嬌)
• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=585882

余談2

テスター当時はRuby版しか答案作ってませんでしたが解説のためにC版を急遽作りました。。

参加記というより反省会(あとで突っ込まれないように。。)

昼

• ポケモンGo、フリーザーを25体撃破しLv37にした。あづい。

コンテスト

ライブ

拝見しました。山内さんちょくだいさんお疲れ様でした。

E問題その後

なんでCrystalだといかんのだ。。

まとめ

• 実装遅いのを()
• Crystalを–releaseでコンパイルしてほしい