問題文のサンプル1はこういう意味である。
3 + 2x + 2x2 + ...
*7 + 0x + 4x2 + ...
=21 + 14x + 36x2 + ...
となる(2乗まで)。この係数の和(21+14+36
)は61である。
つまり、(3+2+2)*7 + (3+2)*0 + (3)*4を計算すれば良いことになる。各項の左側について最初に和を取り、後ろから順番に引いていけば良い。
問題文のサンプル1はこういう意味である。
3 + 2x + 2x2 + ...
* 7 + 0x + 4x2 + ...
= 21 + 14x + 36x2 + ...
となる(2乗まで)。この係数の和(21+14+36
)は61である。つまり、(3+2+2)*7 + (3+2)*0 + (3)*4を計算すれば良いことになる。各項の左側について最初に和を取り、後ろから順番に引いていけば良い。
チャンパーノウン定数自体は既出のネタ(例:Project Euler 40)なので、基本的には以下の方針で良い(CodeIQコード銀行「n番目の数字は?」(答案)のコメントより)。
1 2 3 4 5 6 7 8 |
|
これで、ビルトイン多倍長整数を使えば10**1000
程度まではACできる。ただし、今回は入力が非常に大きいため、下位から順番に処理すると多倍長演算が容易にTLEを招いてしまう(解答例のif false
の一部)。
まず、この1*1*9 + 2*10*9 + 3*100*9 + ...
を高速に求めることを考える。
1 2 3 4 |
|
といった変形により、Si = i*10**i - (10**i-1)/9
と定式化できる。これを用いて、digitsを2分探索するか上位から探索するかする。これでTLEを回避できる。
確か初日にプレイしたはず。当初はLv5ですら星5(90点)取れなかったんですよ…
Extra Stage専用楽曲、完走したら解禁可能とかえぐすぎませんか…全然できないんですが…当時はDRSの反応についてよくわかってなかった(反応が悪いとすら思ったこともあります)。
アンロックを進める中で、ようやくImpress易をクリアした(易を完走できれば解禁可能になり普も普通にプレイ可能になる)。 今でこそLv8の大半の曲は余裕だが、当時はLv7はかなりいっぱいいっぱいだった。がんばったわし。これでFLOWER(易がLv9)に挑戦可能になった。好きな曲だからね。 https://twitter.com/cielavenir/status/1006747633925287936
この頃は音源を聴き込んでおり、77点に乗せる。しかし、この記録が破られることは3ヶ月間ないのであった… https://twitter.com/cielavenir/status/1019926097524244480
あきらめつつも、全曲の解禁作業が終わり、全譜面星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
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の符号で違ったんだっけって少し混乱した^^;;
「不等式の評価」項はコンテスト後に追記したものです。ご迷惑おかけしました(このために星1.5に上がることとなりました)
備忘録です(なお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 |
|
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 |
|
https://yukicoder.me/problems/no/721
テスター当時はRuby版しか答案作ってませんでしたが解説のためにC版を急遽作りました。。
参加記というより反省会(あとで突っ込まれないように。。)
時間 | 言語 | 問題(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位でした。さすがに雑魚すぎました… |
拝見しました。山内さんちょくだいさんお疲れ様でした。
言語 | コメント |
---|---|
Ruby | 遷移式が少し間違っていて、1 2 2 LU SG が1ではなく3になっていたorzまあサンプルはそこまで強くなくても文句言えないけど… |
Ruby | 同じ行にSとGがあるときGを検出できていなかったorz |
Crystal | TLE |
Python | TLE |
C++ | AC |
なんでCrystalだといかんのだ。。