メモ@inudaisho

2017/06/24 はてなダイアリーから引越 / 君見ずや出版

SONY DPT-RP1 DPT-CP1の最新版

 去年買った文石科技(Onyx) の Boox Max2 はPDF閲覧用としてまたメモ用としてこの画像のように使いまくっている。

f:id:inudaisho:20181015164124j:plain
ちなみにこの画像の計算は間違えている

 京都の丸善に行ったときに安い万年筆を買ってから Max2 を脇に置いて万年筆ばかり使っていたが、消せないのでこういうふうに考えをまとめるのに使うには向いていない。それに安物でも万年筆は万年筆、しばらく空気に触れさせておくとペン先が乾燥してしまうのである。あと紙を用意しないといけないのだが、外でも使えるように計算用紙を用意するのが面倒くさい。ということで結局また前のように Boox Max2 をそういう用途に使っている。

 最近 Android 電子ペーパー端末が中国他の企業から続々と出ていて、筆記用大型電子ペーパーSony の影が薄いようにみえる。Sony の DPT-RP1/CP1 も中で動いているのは Android なので、これを公開すればいいだけなんだが、たぶん保守範囲が広がるので退職金の心配しかしてない大企業の50代のおっさんには無理な判断なんだろう。モノはほんとうにいいのに。

 とはいえ、正面からではないが挑戦の跡は見られる。たとえば、この電子ペーパー業界の事情通の Good eReader が持っているショップに行くと DPT-RP1/CP1 のAndroid が剥き出しになったものが売られている。

goodereader.com

goodereader.com

 Good eReader はカナダに本拠を持つ電子ペーパー関係の業者で、かなり早くから電子ペーパー機器をあつかいかつ情報を発信していたので、世界中の電子ペーパー業界関係者とつながりがあるようだ。そのわりに結構紹介している情報の細部が雑なところがあるのは情報入手が速すぎるか、知りすぎているので 逆に予断が多いんだろう。作成しているyoutube動画から判断すると、去年から日本の山梨あたりにも本拠を移動させたりしているようなので、あるいはもともとカナダの企業だったkoboとの繋がりが特に深いのかもしれない。さて、中国のあやしい業者が前から改造版DPT-RP1を売っていたのだが、Good eReader のように業界内でそれなりのつながりのあるところが堂々とこういうものを売っているという事は Sony 側の何らかの暗黙の了解があるはずだ。こういう形であれば Sony の「退職金のことしか考えてない50代」も自分達が何らかの責任を負わなくていいから認められるというところか。

 ところでDPT-RP1/CP1のサイトをみると、新機能が追加されていた。

f:id:inudaisho:20181015170227j:plain
Sony DPT-RP1 の商品紹介ページから引用

 スマホから通信できるようになるアプリが公開された。持ってないので使い勝手がどうなのかは知らないが、言えることは、こういうメモのための機械はメモした情報の引き出しが使い勝手を左右するのでなるべく壁を低くするように作るとよい。Sony の DPT-RP1/CP1 は専用機なのでそういう機能はすべて開発元が提供しないといけない。中には普通のスマホでは達成しにくいこともできるようにしておけば利用者をその使い勝手の虜にできるのだが、たぶんSony電子ペーパー部門の規模ではあまりこなせないんだろう。そのへん文石科技は開発陣がちょっと力不足のようだが、その代り Android を開放するという戦略で行ったのがうまく行った原因だろう。足りないところはユーザーにまかせて補わせる。まぁ日本のように戦後の高度成長~バブルでさんざん甘やかされて育ったためにモンスタークレーマーが跳梁跋扈するようになった魔界ではそういう判断は厳しいのかもしれない。もっとも汎用機戦略に入ると今の文石科技のように、あとから続々と中国のより技術力の高い企業が似たようなものを出してきて市場を食われるという難点もあるかもしれないが、それでも狭い市場なので高見の見物というわけにもいかない。中国のレッドーオーシャンでの共食いで皆死ぬ、よりも激しい競争を勝ちぬいてきた勝者に打ち倒されるのがありそうなオチだ。スマホのことを忘れたのか? あ でもソニースマホはまだ生きのこってるな。ただこの業界の特異なところは電子ペーパーのパネル自体が eInk 社(台湾 元太科技)の独占提供というところで、そこがこの業界最大のネックかもしれないな。

SONY DPT-CP1 デジタルペーパー

SONY DPT-CP1 デジタルペーパー

ソニー デジタルペーパー dpt-rp1

ソニー デジタルペーパー dpt-rp1

AtCoder AGC028 0完 なぜかつらくない

 ついにやりました0完。A は完全に解法わかったとはいうもの、実装が雑だったせいで1waを出し二回ほど出しなおしたものの、失敗。これはドツボにハマるパターンだと思ったのでそこでやめてBに移り、そこで思いついた解法がそこそこいけそうだったので固執してしまい最後まで入力例2入力例3すらきれいに解けず。ううーん。ということでドツボを避けてドツボにハマりこの通りレーティングまで下げてしまった。

f:id:inudaisho:20181014062347j:plain

A

 Aについて。雑というのはこんな感じ。先頭の文字と、そこから最大公約数で割った商おきの文字が衝突するのでそこが揃っているとOKだろうということで、こんな感じに実装したものの、このループ部分の出来がわるかった模様。まぁ見通し悪い実装はどっかおかしいことが多いもので、これもその例にもれず。

def fgcd(a,b):
    if b :
        return fgcd(b,a%b)
    else:
        return a

if sS[0] != sT[0]:
    print("-1")
    exit()
elif fgcd(iN,iM) == 1:
    print(iN*iM)
    exit()
else:
#iLX = iN * iM // fgcd(iN,iM)  の倍数
    iD = fgcd(iN,iM)
    i = 1
    while True:
        if iN -1  <  i * iM //iD   or iM -1  <  i*iN//iD :
            break
        if sS[i*iN//iD ] != sT[i*iM//iD  ] :
            print("-1")
            exit()
        i += 1
    print(iN*iM//iD)

 Python みたいな便利言語にはそういうときにつかえる便利処理があってそれは大いに活用するべきだった。何のために Python で参加してるのか。たとえばリストから一定の間隔で要素を抜くには [開始:終わり:間隔]という記法があってそれを書くだけで今回の処理は終わっていた。こんな感じ。

iD = fgcd(iN,iM)

if sS[0::iN//iD] == sT[0::iM//iD]:
    print(iN*iM//iD)
else:
    print("-1")

 今からおもうと、iN//iDみたいに書いたのを何度もそのままつっこんでいるあたり、余裕がなかった証拠なので、手詰まりになったときに一息置いて変数の整理からやっていった方がよかったのだろう。

 どんくさいために一問落としたのだが、当然手が遅いのも間が抜けているのも実力のうちなので、今回0完なのも実力が反映してるんだな。精進精進( 精進とか言ってる年じゃないかもしれんが死ぬまで精進)

B

 さてBだが、解法の方をみると確率で解くことになっている。自分が思いついたやりかたで結局できなかった事を書いとく。読み物だ。

  • ブロックをひとつづつとりのぞくとき「連結」したブロックの合計の重さがコストとしてかかる。全組み合わせの全コストを計算せよ

f:id:inudaisho:20181014065657p:plain

 入力例2の組み合わせだが、図示するとこんな感じになる。問題でいうところの連結したブロックというのが最初は全部になるなら当然1試行目の重さは全重量* 4! (全組み合わせ)だろう。ということは2試行目は結局このブロック全部どれかさわるのだから4パターンに対しブロック3本分で計算できるのではないか?3段目は6パターンに対し3本分で計算できるのでは? というふうにかなり安直に考えた。

 今こうして書いてるとこの方向であっても、連結した部分を選ぶ試行の頻度が高くなるのでその分の重みが出てくるのだが、雑に式変形したのがなまじ近い計算結果を出したのでそこに固執してしまって堂々巡りに陥り、finishを迎えてしまった。図の2で考えると 1 段目は 24/4 の 6 通り来るのだが、ここではどれをえらんでもコスト 3 かかるので 3 x 6 、その下の2段目は 1 と 2 だが 1 x 2 + 2 x 4 というふうにやっていくととりあえず入力例2の正解が出る。完全に間違えた解に固執していたことになる。

 ここまでわかってようやくこのあたりの親切な解説がわかるというわけだ。今回はなぜかBについてたくさんの人が親切な解説を書いてくれている。ありがたやありがたや。

emtubasa.hateblo.jp

banboooo.hatenablog.com

 となると解法にある確率もいきなり見るとこれは?? この数字は何を割るんだ?となるが、これらの解説にあるようにAiは何回出てくるんだろうということと同じことを言ってるわけで、どうもこのあたりの勘所(問題意識)がなかなかつかめなかった。その確率がいわゆる期待値ということで、うーむ。確率のことを全然わかっていないことがわかる。

beta.atcoder.jp

 つーことで答え合わせのために投げてACしておいた。中に解説めいたこと書いたけどn-iをn-1にしてしまった

結語

 0完とはいえ、何が自分の課題か見えてきたのでよかったような気がする。こりずに次もがんばるぞ。(今回はなぜかつらくない)

今回の教訓

  • 手詰まりのときは変数整理でもやって一回キレイにするといいことがあるかも。ラッキーアイテムはリストのステップ。

  • 雑式変形よくない

 

AtCoder の Python3 の最速実行コード (附) ハンガリアン記法

 なんか Python3 でAtCoderの過去問をやってると案外簡単にPython3 の枠内での最速実行コードが取れることが多い。たぶんゴリゴリやる人は c++ に行くせいだろうなとはおもいつつ、それでもなかなかやるなと自分で思っていたところ、こんなツイートをみつけてしまった。

 うーむ。単にサーバの処理能力が上がっただけか...

 Python3 は競技プログラミングではどうしても遅い結果が出てしまうが、遅すぎるわけではなくギリギリなんとかできるのでむしろこういうので遊ぶには丁度よいのではないかとおもう。ただ、昼間はあんまり速度出ない気がするのだが、AtCoderAWSの上で動いてるのでAWSが昼間混んでるからだろうか。意外と夜の方が出る気がするのはAWS、業務用途で使ってる人が多いからか...とおもったがそもそも AWS は世界中の人が使ってるので混む時間帯は複数ある事に気付いてしまった。ま、参考程度というところか。

 全然関係ないが、AtCoder 、最近よく見てるので背景の白さが目に来る。久し振りにアドオンをいじって背景を黒くした。それからハンガリアン記法は00年代末~10年代頭くらいに槍玉に上げられるようになって、C#マイクロソフトが推奨しなくなったのもあってあまり使われなくなったらしい。そーかー、まぁ00年代の真ん中くらいに覚えた技術だから時代遅れになってもしかたない とは思いつつも、そんならと a b x y ss みたいなのに全部変えてみるとこれはこれで読みづらい。かといってphp 的に this_variable_is_mine みたいなのはよけいに冗長になる。ハンガリアン記法的なものにしてると予約語とあまり被らないのと、バグとりのとき探しやすい。 x y i j 的な頻用変数とハンガリアン的な折衷謎記法でいいかという気になってきた。なお、変数名に漢字ひらがなも使えるのでこんなこともできる。

f:id:inudaisho:20181013075749j:plain

 まぁそもそも AtCoder で書く規模のものなら a b c x y z 程度で十分なのでいちいちこんな妙なものを入れなくてもいいようにはおもうが、コーディング規約とかないところで勝手にやってるんだから勝手にさせてくれ。ハンガリアン記法に対する反発の中にエディタにマウスあてたら中身分かるとか書いてるのもいるんだが、あいかわらず黒いターミナルの上の vim でシコシコ書いてるので、どこの世界の話だろうという気にもなる。

 ちなみに投げるのも入力例も出力例も全部コピペでやってる。さすがにローカルに置いたときは自動でテストできるようにはしてるが。いちいちコピペしてるからAB2問を10分に解くのはなかなかきつい。特にこのノートパソコンはタッチパッドの左クリックの接触がわるいのでなかなかつらい。

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

リーダブルコード ―より良いコードを書くためのシンプルで実践的なテクニック (Theory in practice)

チャールダーシュ - ハンガリアン・ジプシー・ミュージック

チャールダーシュ - ハンガリアン・ジプシー・ミュージック

海信A6(Hisense A6) と YOTA3+ の進捗

海信A6 (Hisense A6)

 微博みてると海信(ハイセンス)公式がスマホ部門に「いつA6出るの?残業できないわけじゃないよね」みたいなこと言ってるのをみつけた。国慶節の大型連休中である。なかなか酷なことを言う。

海信
10月2日 22:00 来自 微博 weibo.com
世界,不止一面;海信说,手机也是。
可是,@海信手机 你们的双屏A6怎么还没上市?难道不能加加班吗

 もうそろそろ出てるんだろうとおもっていたのだがどうもまだ揃ってないようだ。となると、中国の工場では連休後にはたいてい工員が減るのでさらに遅れるかもしれない。まぁ連休も明けたのでいろいろと動きがあるだろう。

YOTA3+ と YOTA

 それから再三とりあげた YOTA3+ であるが、ながらく動静のなかったYOTAの微博アカウントが YOTA3+について公式に情報を出した。

YOTA双面屏手机
10月10日 20:00 来自 微博 weibo.com
失踪人口回来啦~
YOTA3+ 国际版,了解一下?[憧憬][憧憬][太开心][笑而不语]#YOTA直通车# 戳这里试试O网页链接

 これはどう見たものか。公式が発表しないと疑われるからか。 実はYOTA3の発表のときにもどっかの代理店志望が勝手に決めた値段・情報などをネットで先行公開して、各媒体でもとりあげられたことがあった。それでいきなりネットに情報を出すのはちょっとケチがついてしまっているのかもしれない。そもそも海信A6がそろそろ出るという時期にYOTA3の値段が暴落したり、YOTA3+を発表したりするのも、対抗上しかたないといえばしかたないのだが、同じことを海信A2のときにもやっていたので、そういう戦略的な行動が見透されているのかもしれない。ただ一番強いのはYOTA3のアプリ背面投影機能を殺してしまったことで恨まれているんだろうか。否定的なコメントや罵倒がついている。それに、ハードについてはYOTA3とまったく同じなのだから、自慢したがりの中国人にとってはあまりよい商品ではないということだろう。

 それからYOTA関係者の人もYOTA3+について発信している。

threedak
10月10日 18:32 来自 荣耀Note10 大屏旗舰
YOTA3+ 国际版香港发售。 全新基于android8.1的YETI OS8.1.0,支持直接投屏。

 うーむ。YETI OS8.1とか書いてるんだがなんか国外向けに英語で出てるのとちがうな。この人の勘違いなんだろうか。「Android8.1」であること、それからアプリの背面への投影をサポートしてることが明記されている。コメントへの返事に国内向けには売らないということなので、国内で売らないものの情報を国内向けの微博でわざわざ発信したということは ​​​​、自分のように疑い深い人間しか興味を寄せていないということだろうか。

 ところで香港の電脳ショップの方をみると、こちらは「預售」と書かれている。予約である。あれ?メールで9月末に「明日店に並ぶ」とか書いてなかったっけ? 在庫処分だとおもってたのでなんか意外な展開になってきた。これから作るわけではないだろうし。

(20181013 ついにTadakossiの元へ発送された模様。国慶節の連休で Yota が休んでただけのようだ。となると、かなり中国側のハンドルが強いことになり、英語のサイトの記述で勘違いしたような「YotaPhone2の後継機」ではないかもしれない )

【宝力优特科技(深圳)有限公司2018招聘信息】-猎聘网

 ここにYOTAの人材募集があるのだが、Android 技術者などで、一ヶ月くらい前から出ている。人手不足なんだろうか。まぁこういうのは常に出てるものかもしれん。他にもいろんなサイトで募集してる。

YOTA の新機種の謎の電子ペーパースマホについて

重磅消息!首批潼南制造YOTA墨水屏学习机即将投产

 これからYOTAが出す新機種の情報がある。重慶の潼南区のローカルニュースだが、新機種である「学習機」が10月から生産開始するとある。

inudaisho.hatenablog.com

 これで紹介した謎の電子ペーパースマホのことだろう。電子ペーパー面しかないスマホで、そういうのは過去に文石科技が一度出しただけだ。記事をみると潼南工場はこれの生産に当てるように書いてある。工場操業の手始めに安い商品で慣れるということだろうか。しかし人材募集などみると勤務先が深圳であることが多い。開発を深圳でやって生産を重慶の方でやるということか? ま、こういうの売り出すということはまだ潰れないということだろうから、待ってればそのうち発表があるだろう。中国の簡単スマホはなかなかおもしろいかもしれない。

SONY DPT-CP1 デジタルペーパー

SONY DPT-CP1 デジタルペーパー

AtCoder ABC044 C 高橋君とカード 動的計画法

 前にも書いたように最初まったくわからず解法にあった問題を尋ねて遠まわりしてたがようやくできたので書く

問題

  • 数列から選んだ合計の平均がAになる組はいくらあるか。 数列の規模50以下。数列は50以下の正の整数。

迷宮入り

 お、これは組み合わせだな?ということで、早速数列から平均値を引いたリストをつくって、とりあえず辞書につっこんで数字別に数えあげたものの、そこから先がよくわからない。はて。そこから0を挟んで対称となる組み合わせと0の組み合わせをかけていけばよさそうだが、さてどうやってそれを出せばいいのか。うぅーむ.... わからん。

f:id:inudaisho:20181011155434p:plain

 長考してもわからないのでとりあえず解法をみてみると解法1として bit演算とか書いてある。で、それの参考になるというので遡って解いたりしたあげくグラフの初歩にひっかかったのだが、それをとりあえずなんとかしてからまた戻ってきた。ためしにビット演算でやってみるとPython3では例4を手元で計算させるだけでもTLEする。これはやってもしかたない。そこで解法2,解法3をみると、どうもこちらはよく聞く動的計画法らしい。

動的計画法

 しばらく眺めてこれでどうして組み合わせがでてくるのかよくわからず、いろいろいじっているうちに、sum(k=1→n) nCk が2n -1 と等しいらしいということを見付けた。例4がそれだったのはたぶんそれもわかる人にわかるようにしてあるヒントなんだろう。まぁ自分はみただけではちっともわからなかったが。それである程度は積算していったら何かそれらしいものが出るらしいことがわかったが、ではこういうふうにする漸化式をどうやってひねり出すのか。

 動的計画法はリチャード・ベルマン(アメリカ)が1953年発表したものらしい。なんか詳しい本がありそうだったが夜だったので待てずにネットでなんとかした。幸いなことに Wikipedia がわりと詳しく書いてあった。 ちなみに動的計画法 - Wikipediaではない。これはプログラム屋が動的計画法として知られているプログラム技法を紹介しているだけなので、専門の穴にハマっている(井戸の底から見る空は狭い)。大枠を知った後で読むものだ。最初に読むべきはこっちだ。

 このベルマン方程式の解説で役に立つのが、「動的計画法の考え方」だ。目標を数式化した目的関数。表現するための状態変数・制御変数。コントロールする政策関数。それらに別軸で評価をつける価値関数。この価値関数の最適化が動的計画法でやることらしい。それらが最善手で進むという前提で最適化の漸化式と初期値を立てるとあとは決まるということらしい。ベルマン方程式の下の方をみるとマルコフ過程とか書いてある。あ、そういうのの基礎か。

R. ベルマンと動的計画法あらがき - 日本オペレーションズ・リサーチ学会

 これは1985年(昭和60)のベルマン追悼記事だが、その中で動的計画法についてこんなふうにまとめてある。

特に重要なことは多くの場合DPの手法は古典的手法のような数学的訓練を必要とせぬという事実である。さらに古典的理論の大部分は数値計算に適するようには作られていない。しかしコンピュータが発達したので、コンピュータの能力にもとづいた新しい数学が創られつつある。まさにDPは今世紀が生んだ嫡子である。

DPの本質は政策の概念であり、それはシステムの状態の項から作った決定を語る法則である。

政策の思想は実験による学習の概念に通じている。

高水準の意思決定過程の理論はこれまでの動的計画法を含み、しかもこれから出現する高性能のコンピュータに相応ずる理論でなければならない。

 なるほど、この単純な漸化式によるミニ試行が、複雑な問題に答えを出してしまうことが、今のAI大流行のような事態を導いたわけだな。動的計画法の単純な升目がたぶん当時の人には今のニューラルネットワークブラックボックスみたいに見えたんだろうな。競技プログラミングをやると強くなるかどうかは別にして、今現在進行中の技術の基礎を押さえれるわけだ。なるほど。

 それからWikipediaのベルマンの項に逸話のようにして引いてある「次元の呪い」、これは結局機械でぶんまわすといっても要素が多いとつらくなるということらしい。

解法1

 なんだ結局場合の数は出せず試行で足しあわせて出すのか、とおもいながら動的計画法にとりかかる。ちなみにこういう問題は動的計画法の典型的な問題らしい。

 解法1のDPは縦N(数列j番目)横N(k枚)高さN*X (Xは数列とAの最大値)(そのときの合計)の場合の数を入れる立方体の箱をつくり、k枚のときKAとなる場合の数を合計するということで、自分が最初考えていて詰まった解法よりも原始的である。計算量がものすごいというのはわかるが、まだよくわからず、とりあえず解法にあるとおりにループを組んでみると、手元ではたしかに見事に解ける。なるほど。感心してからAtCoder の方に投げてみるとTLE。式をみなおして無駄な処理を減らしてもTLEだったので Python3 はこういうことするための言語じゃないなとおもいながら解法2に移った。

 ちなみにいろいろやってかなり飲みこんできてから、後で見直したのだが、

dp[0][0][0] = 1
for j in range(1,iN+1):
#   for k in range(0,iN+1):
    for k in range(0,j+1):
#       for s in range(0,iN*iMX + 1):
        for s in range(0,j*iMX + 1):
            if  s < aX[j-1]:

 こうやって立方体を斜めに二回切り取ることができる。そうすると解法1の愚直な for ループでも通る。

解法2

 解法2は最初自分が思いついたように差分をとって座標を0に持ってくるやりかただ。まぁよくある手だから当然だが、そこから二次元の表を作って全部計算するのは違う。縦N(J枚目)横2NX(t-NXのt)。0を中心にしたのはいいが、結局正と負の二面作戦になるので両面にNXが必要になるらしい。真ん中に0を持ってくるために t-NXという小細工をしたわけだ。

f:id:inudaisho:20181011151842p:plain

 最後の結果をdp[N][NX]でとるというのはつまりそこに結果0の場合の数が集まっているからだ。(真ん中の0の列がdpのNXの列)同様に最下段には-NX...-2,-1,1,2,...NXのときの場合の数が入っている(一枚も選ばなかった場合も含んでいるので答えを出すときは1引く)ので自分の思いついた解法にも応用できるが、このまま使うと当然遅くなるのでこのままの応用はしなかった。適当に実装するといきなり300msくらいで計算できた。実は実装するのは簡単で、なぜこれで答えが出るのかわからず、結局dpのリストに何が入っているのか出力させてみてようやくイメージがつかめたのだが、それはさておき。他の人の解答をみると、2桁msの速さで計算させている人たちがいる。その中身をみると collections の Counter をつかっている。これはつっこんだリストの要素を数えてハッシュの形で保持してくれるもので、便利な性質として、無い要素はエラーではなく0で返してくれる事と、辞書(ハッシュ、連想配列)で渡すとキーを合わせて足し算してくれる事の二つがある。Pythonはリストをぶんまわすのが遅いので動的計画法でも表の最後の行だけ使う今回のようなものであればそういう仕組みで足し算していってもいいわけだ。なるほど賢い。とはおもったが解法2をそのまま python のライブラリつかって高速化してもおもしろくないので、今回は最初に思いついたロジックを実装することにした。

応用篇:オレ解法

 最初に書いた通り、ゼロだけ分けて組み合わせを計算し、正と負の数列に分けて正負同じ結果になる組み合わせを探すというやりかたについてだが、これに動的計画法が適用できそうだ。解法だけ見ても結局自分の頭を使って応用しないと身につかない。ということで早速応用篇になる。

 正と負に分けるとその上限が正なり負なりのそれぞれの合計の小さい方だということがわかるので正負に分けると必要な計算量がものすごく減る。1以上の数字を足し合わせて行くだけだから、リミットを越えた数字は無視してよい。ということで、縦を正負いずれかの数列、横をさきほどの合計の大きい方で取る。これ箱の大きさだけは大きい方を採用したのは小さいのだと1になることがあってエラーが出る。

 漸化式は 求めたい合計よりも数列の数字が小さければ前の数列のときの場合の数を取り、大きければ、前の数列のとき(不採用のとき)に加えて前回が今求めたい合計より数列の数字分引いた合計のとき(採用のとき)の場合の数を足す。それを順次やっていくのだが重要なのは合計0の箱に1をいれておくことで、それが最初にその数字が出てきた場合の種になる。

        for j in range(1,iLenPlus):
            for k in range(iUlim + 1):
                if k < aPlus[j] :
                    dp1[j][k] = dp1[j-1][k]
                else:
                    dp1[j][k] = dp1[j-1][k] + dp1[j-1][k-aPlus[j]]

 つくったdpの表の中身を出してみるとこうなる。(入力例3)

#--aPlus
[1, 3, 2, 1, 4]
#-dp1-
# 0,1,2, 3, 4, 5
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 1 -> 0と1に1
[1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0] # 3 -> 3と4に1 (0+3 , 1+3
[1, 1, 1, 2, 1, 1, 0, 0, 0, 0, 0, 0] # 2 ->という具合
[1, 2, 2, 3, 3, 2, 0, 0, 0, 0, 0, 0] # 1
[1, 2, 2, 3, 4, 4, 0, 0, 0, 0, 0, 0] # 4
#-aMinus-
[2, 3]
#-dp2-
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0]

 このそれぞれの最後の行の数字と0の場合の数(0の場合のときを考えて1足す)をかけて0の時の場合の数を足したら答が出る。ABCの方のPython3でこのやりかたで最速(25ms)を取ったのでちょっと自慢したくてこんなの書いたのだが、ARCの方も同じ問題出てるのに気付いてそっちを確認してみると普通にもっと速く書いてる人がいた。うぅーむ。

 とくにこのへん。

提出 #1780666 - AtCoder Regular Contest 060

提出 #1389625 - AtCoder Regular Contest 060

    dp = {0:1}
    for n in a:
        for k, v in dp.copy().items():
            dp[k+n] = dp.get(k+n, 0) + v

 すげー Counter とかいらんかったんや!

  • python3 の dict のgetはキーがないときエラーではなく、第2引数を返してくれる
  • copy()を挟むことによって辞書サイズ変更エラーがなくなる

 このテクをパク.....応用することによってARC/ABCを併せての最速(19ms)出しました(厚顔無恥

 ちなみにこれを応用するとどんなループになるかはこちら参照。上のリストと比較するとわかりやすいとおもいます。上のリストが上限切ってそれ以上計算していない以外は一緒ですね。

iX: 1
 k,v: 0 1 |k+iX: 1
iX: 3
 k,v: 0 1 |k+iX: 3
 k,v: 1 1 |k+iX: 4
iX: 2
 k,v: 0 1 |k+iX: 2
 k,v: 1 1 |k+iX: 3
 k,v: 3 1 |k+iX: 5
 k,v: 4 1 |k+iX: 6
iX: 1
 k,v: 0 1 |k+iX: 1
 k,v: 1 1 |k+iX: 2
 k,v: 3 2 |k+iX: 4
 k,v: 4 1 |k+iX: 5
 k,v: 2 1 |k+iX: 3
 k,v: 5 1 |k+iX: 6
 k,v: 6 1 |k+iX: 7
iX: 4
 k,v: 0 1 |k+iX: 4
 k,v: 1 2 |k+iX: 5
 k,v: 3 3 |k+iX: 7
 k,v: 4 3 |k+iX: 8
 k,v: 2 2 |k+iX: 6
 k,v: 5 2 |k+iX: 9
 k,v: 6 2 |k+iX: 10
 k,v: 7 1 |k+iX: 11

(この数字の羅列を貼ったときにそういえばこれで枝刈りしたらどうなるんだろうとおもって上限切ってみたら19msとれたのでそう書きなおしました)

非線形最適制御入門 (システム制御工学シリーズ)

非線形最適制御入門 (システム制御工学シリーズ)

動的計画法 POD版 (数学ライブラリー)

動的計画法 POD版 (数学ライブラリー)