背景等

  • 紫稼働時に私のレーティングは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です)

予選 本選会場 THANKS 決勝会場 開催セット
2013 コワーキング・スペースMONO(お台場) マサチューセッツ工科大学 本戦のみ(rproconとして開催)
2014 2回 3331 Arts Chiyoda(秋葉原) 2回 上海交通大学 本戦、エキシビジョン、あさプロ、リレー
2015 2回 泉ガーデンギャラリー(六本木) 1回 沖縄科学技術大学院大学 本戦、エキシビジョン、あさプロ、リレー
2016 3回 ベルサール汐留 マホロバ・マインズ三浦 本戦、エキシビジョン、トーナメント、リレー
2017 3回 秋葉原UDX 1回 本戦、エキシビジョン、トーナメント、リレー
2018 2回 秋葉原UDX 1回 本戦、リレー

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

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

解法

余談

余談2

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

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

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

コンテスト

時間 言語 問題(A-H) コメント
0:01 Ruby A AC 時間がかかったのはペナルティに気をつけるためです。
0:03 Ruby B AC
0:18 Ruby D 愚直な循環検出を書いたが、実行間に合わず。
0:29 C++ D C++に移植したがTLE 焦る。
0:46 Ruby C 下と右のマス数を掛け算。TLE (解説の方針と同じなんです)
1:12 Ruby/C++ D 申し訳ありません。C++の実行結果をzlib圧縮して埋め込みました。AC
1:17 Crystal C TLE
1:35 C++ C AC ところでvector transposeをライブラリとして持っていたから助かりましたが、持っていなかったらどうなっていたんでしょう。ぞっとします。
1:59 Ruby E コストテーブルを作って最短路という方針は思いつきましたが間に合いませんでした。heapqは以前私がAOJにてheapq.pyを移植したのをコピペしました。
(あとで確認したらRubyでは間に合わない感じでしたのでどうせ無駄でしたね…)
2:00 264位でした。さすがに雑魚すぎました…

ライブ

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

E問題その後

言語 コメント
Ruby 遷移式が少し間違っていて、1 2 2 LU SGが1ではなく3になっていたorz
まあサンプルはそこまで強くなくても文句言えないけど…
Ruby 同じ行にSとGがあるときGを検出できていなかったorz
Crystal TLE
Python TLE
C++ AC

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

まとめ

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

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1155

構文解析とは何だったのか(2回目)

解法

  • Ternaryクラスを用意してevalに投げ込みます。

解答例

感想

  • 知識の証明の時点ではPythonが公式に使えるようになっていたので、下手な構文解析を出すと言語機能で突破されかねませんよって話。この問題は当時Pythonが使えなかったから許されたんだと思う。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2883

構文解析とは何だったのか。

解法

  • 例として[+c[+a[^bd]]]O[c][O[a][X[b][d]]]に変換します。
  • O、A、Xはそれぞれ2引数を取りor、and、xorするProcで、カリー化されています。
  • 変換された文字列は正しいプログラムなので、evalでバッチリです^^

Python

  • Pythonはfunctools.partialはありますが演算子の形でカリー化することができないので、自前で関数をネストしてカリー化を行います。
  • なおPythonはRubyのProcで必要な特別扱いが必要ないので、括弧は丸括弧を使います。
  • (ところで答案内のtranslateのインポート方法に癖がありますが、Py2/3対応にするにはやむを得ないものです。)

解答例

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

解法

  • bitDPを使うのが一般的な解法ですが、計算量が増えるものの、next_partial_permutationを使うこともできます。
  • 標準関数ではありませんが、next_permutation(v.begin(), v.end())する直前にreverse(v.begin()+middle, v.end())するだけなので、(next_combinationと違って)インラインで組み込むのは簡単です。
  • v.begin()からv.begin()+middleまでを(middle P sizeの)部分順列として使います。
  • ただし、ループが回るたびに、v.begin()+middleからv.end()まではソートされていることが保証されています。この性質を利用することで、vからsize-middle個選んでから残りのmiddle個を総当たりしたのと同じことになるのです。
  • ループ回数は14P7 = 17297280回です。

解答例

チームを作ろう2

https://abc096.contest.atcoder.jp/tasks/abc096_d

出力

  • AGC001以降のAtCoderでは、区切りは空白区切り改行区切りのどちらでも構いません(trailing spaceも可)。
  • よってputs arr*' 'puts arr、ひいてはp *arrでokです。以下では後者を使います。

解法

  • 5で割ってあまりが1になる整数の集合から5個選んだ合計は5で割り切れます。
  • 素数を列挙していき、1の位が1であるものをN個拾えば良いです。
    • 実際には1の位は(統一していれば)1,3,7,9のいずれも大丈夫です。以下の答案では9を採用しています。
    • 64bytes
1
require'prime';p *Prime.each(1499).select{|e|e%5>3}[0,gets.to_i]
  • 1の位がX(奇数、以下の答案では3)である整数を全て列挙し、素数をN個拾うようにすると以下のようになります。
  • 62bytes
1
require'prime';p *3.step(1499,5).select(&:prime?)[0,gets.to_i]

フェルマーテスト

  • require'prime'をカットすることで字数の節約にはなりますが、Integer#prime?は使えなくなるので、別の素数判定が必要になります。そこで、フェルマーテストを用います。
  • [1]に載っている式、2**i%i==2を使います。なおこの素数判定の場合stepの初期値を1にすることはできなくなるので注意してください(3,7,9は可)。
  • 51bytes
1
p *3.step(1499,5).select{|i|2**i%i==2}[0,gets.to_i]

redo

  • [2]では、ループカウンタをインクリメントしないよう、条件を満たさない場合はredoを使っています。これはPerlだけでなくRubyでも有用なテクニックです。
  • https://abc096.contest.atcoder.jp/submissions/2470406 (最終答案)
  • 46bytes
1
i=3;gets.to_i.times{i+=5;2**i%i==2?(p i):redo}

discussion

  • フェルマーテストやredoの実践例を挙げることができました。どちらもゴルフには有用であると思われます。

reference

  1. cojnaさん https://abc096.contest.atcoder.jp/submissions/2465874
  2. %20さん https://abc096.contest.atcoder.jp/submissions/2467541