かつかれーのメモ帳

実験ノートか勉強記録

PS2タイトルを自作USBコントローラーで遊ぶ

IIDX自作コントローラー記事のソフト編(その1)です。
CS弐寺*1を初期型PS3で遊ぶために、PS2エミュレータ*2上で自作コントローラーを動作させました。

自作コントローラーをPS3に認識させるには

PS3本体のファームウエアバージョンなんかにも依存していて難しいのですが、比較的新しいファームウエアでは適当に作ったHIDゲームパッドも認識されます。4軸+13ボタンで作れば、軸が左右のスティック(X, Y方向の動き*2つで4軸分です)に、ボタンが各ボタン(方向キーを除く)に対応します。
ただPSボタンだけは特殊で、対応する13番ボタン押下の信号を送っていても無視されてしまいます。どうやらエンドポイント0(=コントロール転送)におけるHID_GET_REPORTリクエストに特定のバイト列で応答するか本体側でチェックしているようです。簡単な認証が為されているという感じですね。
この事実は結構有名で、例えば
ps3-teensy-hid - USB hid device for the PlayStation3 using the Teensy platform
におけるmagic_init_bytesのような実装例が結構見つかります。逆に、これさえ実装していればPSボタンも正しく動作するようになります。めでたしめでたし…？

PS2タイトルの謎仕様

さっそく基板を試作し、ホーム画面・PS1タイトル・PS3タイトルの操作に成功したのですが、PS2タイトルだけは全く操作できないんですよね…なんで？(全ギレ)
PS2のソフトをやる時だけ「何故かコントローラーの接続が解除されてしまい、PSボタンを押してコントローラーを再接続する必要がある」という仕様、実機を触ったことがある方ならご存じだと思います。後でわかったのですが、実はこれってPS2の時だけコントローラーの認証が非常に厳しくなっているためで、非純正コンはここですべて振り落とされるようになっています。
オフィシャルに動作が保証されているのは標準の純正コントローラー、つまりDUALSHOCK 3とSIXAXISだけ。こいつらは機能がてんこ盛りなせいで動作が複雑で、認証をすり抜けられるほど高い再現度は達成されていません*3。さすがにDUALSHOCKの解析は大変そうなので、もっと単純なコントローラーで使えるものはないか調べてみました。
www.jp.playstation.com
…ありました。HORI製のRAPV3という格ゲーコンです。
格ゲー界隈はやはりコントローラーへのこだわりが強いようで、PS2タイトルでの動作報告が活発に上がっていたので助かりました。SIEの公式サイトで「オフィシャルライセンス商品」とされているコントローラーは新しめのファームウエアでサポートしているっぽいです。

RAPV3の解析

中古でコントローラーを手に入れ、パケットキャプチャによる解析を試みました。今回はコントローラーの接続先がPCではなくPS3なので、Wiresharkなどのアプリを立ち上げておくことができません。こういう時はUSBスニファを使います。
USBスニファとは、通ったUSBのパケットをすべて記録しつつ中継する装置です。beagleboard xMというシングルボードコンピュータ(Linuxが動くボード。ラズパイみたいなやつ。)を使いました。とりあえず写真を見てもらうのが早いと思います。
f:id:DSKK:20200529111819p:plain
PS3-スニファ-コントローラーという接続になっています。LANケーブルはパケットキャプチャそのものには関係ありません。
このボードはUSBのホスト側とデバイス側両方の口を持っているので、本来USBケーブルで直結されるPS3とコントローラーの間に挿入することができます。
f:id:DSKK:20200529112038j:plainf:id:DSKK:20200529112048j:plain
USB mini-Bがデバイスとして振舞える口。標準Aコネクタにはデバイス(今回の場合コントローラー)をぶら下げられます。
パケットは速やかに(かつ、変更を受けずに)スニファをパスするので、PS3やコントローラーは直結時と変わらない通信ができます。また、beagleboard xM自体の制御は他PCからのSSH接続で行えます(LANケーブルはこのためにつないでいます)。
github.com
今回焼くファームウエアとしては、これをそのままありがたく使わせてもらいます。作者はGIMXの管理人をしているMatlo氏*4。カーネルレベルでUSBパケットの中継を実装してくれているらしく、漏れや遅延が起こりにくそうです。./sniffコマンドでパケットをすべてdumpしてくれるのすごい。
さて、どんな認証が行われているのかとワクワクでdumpファイルを見たのですが…

特別なパケットは何もやり取りされていない

f:id:DSKK:20200529115408p:plain
PS2タイトル起動後にコントローラーを接続したときの挙動。デバイスディスクリプタ・コンフィギュレーションディスクリプタの要求のあと、セットコンフィギュレーションが行われデバイスが使用可能になっている。あとはひたすらインタラプト転送のpollとresponseが続く。
はい。いたって普通に通信しているようにしか見えませんでした。え、なにこれは…

うーん…では逆に、PS2で使えないコントローラーはどうなっているんでしょう？
今度はELECOM製のJC-U4013Sという、普通のゲームパッド(ホーム画面やPS3タイトルの操作は可能)をPS2タイトル起動後に接続したときの挙動を見てみました。

f:id:DSKK:20200529120412p:plain
セットコンフィギュレーションが来ていない！
デバイスディスクリプタとコンフィギュレーションディスクリプタを見た時点で通信をやめています。オフィシャルライセンス商品についてはこれらのディスクリプタをホワイトリスト形式で持っていて、合致しなければガン無視を決め込む仕様っぽいです*5。
これはなるほどという感じ。オリジナル要素のあるコントローラーが動かないわけだ。

自作コントローラーの仕様確定

要するに、

なら、PS2タイトルでもホーム画面でもフルで機能するってことですね。ディスクリプタ類は以下の通りです。

/* Device Descriptor */
 18,                // bLength
 1,                 // bDescriptorType
 0x00, 0x02,        // bcdUSB
 0,                 // bDeviceClass
 0,                 // bDeviceSubClass
 0,                 // bDeviceProtocol
 64,                // bMaxPacketSize0
 0x0d,              // idVendor[0]
 0x0f,              // idVendor[1]
 0x22,              // idProduct[0]
 0x00,              // idProduct[1]
 0x00, 0x10,        // bcdDevice (=version number)
 1,                 // iManufacturer
 2,                 // iProduct
 0,                 // iSerialNumber
 1                  // bNumConfigurations

/* Configuration Descriptor */
 9,                              // bLength;
 2,                              // bDescriptorType;
 0x29,
 0x00,                           // wTotalLength
 1,                              // bNumInterfaces
 1,                              // bConfigurationValue
 0,                              // iConfiguration
 0x80,                           // bmAttributes
 50,                             // bMaxPower
 // interface descriptor
 9,                              // bLength
 4,                              // bDescriptorType
 0,                              // bInterfaceNumber
 0,                              // bAlternateSetting
 2,                              // bNumEndpoints
 0x03,                           // bInterfaceClass (0x03 = HID)
 0x00,                           // bInterfaceSubClass (0x00 = No Boot)
 0x00,                           // bInterfaceProtocol (0x00 = No Protocol)
 0,                              // iInterface
 // HID interface descriptor
 9,                              // bLength
 0x21,                           // bDescriptorType
 0x11, 0x01,                     // bcdHID
 0,                              // bCountryCode
 1,                              // bNumDescriptors
 0x22,                           // bDescriptorType
 0x89,
 0x00,                           // wDescriptorLength
 // endpoint descriptor
 7,                              // bLength
 5,                              // bDescriptorType
 2,                              // bEndpointAddress (ep2,out)
 0x03,                           // bmAttributes (0x03=intr)
 64, 0,                          // wMaxPacketSize
 10,                              // bInterval
 // endpoint descriptor
 7,                              // bLength
 5,                              // bDescriptorType
 0x81,                           // bEndpointAddress (ep1,in)
 0x03,                           // bmAttributes (0x03=intr)
 64, 0,                          // wMaxPacketSize
 10                              // bInterval

/* Report Descriptor */
 0x05, 0x01,        // Usage Page (Generic Desktop Ctrls)
 0x09, 0x05,        // Usage (Game Pad)
 0xA1, 0x01,        // Collection (Application)
 0x15, 0x00,        //   Logical Minimum (0)
 0x25, 0x01,        //   Logical Maximum (1)
 0x35, 0x00,        //   Physical Minimum (0)
 0x45, 0x01,        //   Physical Maximum (1)
 0x75, 0x01,        //   Report Size (1)
 0x95, 0x0D,        //   Report Count (13)
 0x05, 0x09,        //   Usage Page (Button)
 0x19, 0x01,        //   Usage Minimum (0x01)
 0x29, 0x0D,        //   Usage Maximum (0x0D)
 0x81, 0x02,        //   Input (Data,Var,Abs)
 0x95, 0x03,        //   Report Count (3)
 0x81, 0x01,        //   Input (Const,Array,Abs)
 0x05, 0x01,        //   Usage Page (Generic Desktop Ctrls)
 0x25, 0x07,        //   Logical Maximum (7)
 0x46, 0x3B, 0x01,  //   Physical Maximum (315)
 0x75, 0x04,        //   Report Size (4)
 0x95, 0x01,        //   Report Count (1)
 0x65, 0x14,        //   Unit (System: English Rotation, Length: Centimeter)
 0x09, 0x39,        //   Usage (Hat switch)
 0x81, 0x42,        //   Input (Data,Var,Abs)
 0x65, 0x00,        //   Unit (None)
 0x95, 0x01,        //   Report Count (1)
 0x81, 0x01,        //   Input (Const,Array,Abs)
 0x26, 0xFF, 0x00,  //   Logical Maximum (255)
 0x46, 0xFF, 0x00,  //   Physical Maximum (255)
 0x09, 0x30,        //   Usage (X)
 0x09, 0x31,        //   Usage (Y)
 0x09, 0x32,        //   Usage (Z)
 0x09, 0x35,        //   Usage (Rz)
 0x75, 0x08,        //   Report Size (8)
 0x95, 0x04,        //   Report Count (4)
 0x81, 0x02,        //   Input (Data,Var,Abs)
 0x06, 0x00, 0xFF,  //   Usage Page (Vendor Defined 0xFF00)
 0x09, 0x20,        //   Usage (0x20)
 0x09, 0x21,        //   Usage (0x21)
 0x09, 0x22,        //   Usage (0x22)
 0x09, 0x23,        //   Usage (0x23)
 0x09, 0x24,        //   Usage (0x24)
 0x09, 0x25,        //   Usage (0x25)
 0x09, 0x26,        //   Usage (0x26)
 0x09, 0x27,        //   Usage (0x27)
 0x09, 0x28,        //   Usage (0x28)
 0x09, 0x29,        //   Usage (0x29)
 0x09, 0x2A,        //   Usage (0x2A)
 0x09, 0x2B,        //   Usage (0x2B)
 0x95, 0x0C,        //   Report Count (12)
 0x81, 0x02,        //   Input (Data,Var,Abs)
 0x0A, 0x21, 0x26,  //   Usage (0x2621)
 0x95, 0x08,        //   Report Count (8)
 0xB1, 0x02,        //   Feature (Data,Var,Abs)
 0x0A, 0x21, 0x26,  //   Usage (0x2621)
 0x91, 0x02,        //   Output (Data,Var,Abs)
 0x26, 0xFF, 0x03,  //   Logical Maximum (1023)
 0x46, 0xFF, 0x03,  //   Physical Maximum (1023)
 0x09, 0x2C,        //   Usage (0x2C)
 0x09, 0x2D,        //   Usage (0x2D)
 0x09, 0x2E,        //   Usage (0x2E)
 0x09, 0x2F,        //   Usage (0x2F)
 0x75, 0x10,        //   Report Size (16)
 0x95, 0x04,        //   Report Count (4)
 0x81, 0x02,        //   Input (Data,Var,Abs)
 0xC0               // End Collection

HIDレポートは27バイトありますが、初めの3バイトだけが変化します。ボタン等との対応は以下の通りです。後ろの24バイトはおそらくPS3の要求する仕様を満たすためにダミーを送っているのでしょう*6。

1バイト目:
  R2, L2, R1, L1, △, 〇, ×, □

2バイト目:
   -,  -,  -, PS, R3, L3, START, SELECT

3バイト目:
  ハットスイッチ(POV)。対応は以下の通り。
  0x00 = Up
  0x01 = Up+Right
  0x02 = Right
  0x03 = Down+Right
  0x04 = Down
  0x05 = Down+Left
  0x06 = Left
  0x07 = Up+Left
  0x0f = None

1バイト目、2バイト目は左のものほど上の位です。例えば△と□が押されていると1バイト目は0x09になります。
後ろの24バイトは以下の通り固定です。
0x80, 0x80, 0x80, 0x80, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02, 0x00, 0x02

また、弐寺の鍵盤とプレステのボタンの対応は

1: □
2: L1
3: ×
4: R1
5: 〇
6: L2
7: ←

のようになっています。あとはこれを実装すればOKです。

まとめ

内容が盛りだくさんになってしまいましたが、とにかくマネしたいコントローラーを見つけてその動作を丁寧に解析・実装するということに尽きます。次回はINFINITASに対応したファームウエアの仕様について同様に解説し、次々回でそれら2つのファームウエアを共存させる実装方法について述べていくので、具体的なソースコードの解説はその時に。
下のリンクからシェアやツイートなどしてもらえると大変執筆モチベが上がりありがたいです。良かったらぜひ。何か気になる点があったらコメントか
しありす (@cialis438) | Twitter
へのリプをお気軽にどうぞ。感想やコントローラー自作に関する雑談・質問なども歓迎です。

*1:beatmania IIDXのPS2移植版。いわゆる家庭用。これとか。

*2:PS3→PS2の後方互換機能で、最初に発売されたモデル(CECHAxxとCECHBxx。分厚くてつやつやしたやつ)にだけ搭載されている。

*3:世界最大の自作コントローラーコミュニティ、GIMXでも未解決でした。 2015年の投稿 で少しだけ話題に上がりましたが、作者が実機を持っておらず進展がないまま放置。ちなみに2020年の投稿は私によるものです。本記事のような知見をシェアして貢献できると良いなあ。

*4:コントローラー解析と実装のガチプロでGIMXと関連プロジェクトを素晴らしくメンテしているので尊敬している。いろいろなコメントに対する返答も丁寧なナイスガイ。

*5:余談ですが、HIDレポートディスクリプタはRAPV3と全く一緒でした。サードパーティーが別々にコントローラー開発したとして、1バイトも違わず偶然一致するものではないと思うのだけどいいのか…？

*6:レポートディスクリプタによれば軸が1バイト×4、vendor_definedが1バイト×12+2バイト×4。vendor_definedの前者は感圧センサ12ボタン分、後者は加速度センサ4軸分らしい。

beatmania IIDX コントローラーの製作

皆さま、自粛期間いかがお過ごしでしょうか。音ゲーマーにとってはゲーセンの閉店が一番きついかもしれませんね。
というわけで、beatmania IIDX(以下、弐寺)のコントローラー自作について書いていこうかと。初回は目次を兼ね、今後投稿する予定の記事のダイジェストみたいなものを投稿します。3～5記事くらいでしょうか。

はじめに

自作とはいいますが、正確には「ごく一部を残して大幅に改造」です。このコントローラーはもともとDAOコンでした。
現存する最も古い姿の写真です(非常に良い条件で譲って頂いて、ありがたい限りです…)
これでも機械的な部分のオーバーホール(ターンテーブル軸のベアリングのグリス交換、底面パネルのネジ山修整、断線したケーブルを新品でリプレース、ボルトとナットを全てステンレス製の新品に交換、アームレストの布張り替えなど…)が終わったところです。この辺楽しくないと思うのでブログ記事にはしません。写真を一枚だけ。
f:id:DSKK:20200424163527j:plain
全部剥きました。この後地味な作業を無限にやります。
このときついでに背面パネルも改造済みです。しかしまだまだ以下のような不満点があります。

  • ポーリングレートなど性能の決して高くない&ケーブル着脱式にするのが難しいプレステ2コントローラーとして回路が作製されている
  • 基板設計が全体的にイケていない。コンバーターを噛ませない限りプレステ2にしか対応しないし、ボタンを光らせる必要がないときでも補助電源の接続が必要
  • ターンテーブルの表面処理がアーケードとかなり違ってちょっとダサい
  • 皿の感度が悪い
  • 最新のINFINITASコントローラーはファンクションキーが4つあるが、2つしか実装されていない

などなど。

とりあえず、一番困ったのは時代遅れなプレステ2コントローラーである点ですね。コンバーターの遅延を気にしながら音ゲーをするのはキツいので基板ごと入れ替えてしまいましょう。現在、このコントローラーが対応しなければならない用途は以下の3つです。

  • CS弐寺: プレステ2タイトルですね。
  • INFINITAS: コナミ公式が配布、運営するPCゲームです。
  • BMS: やねうらお氏が規格を制定したことで有名ですね。有志による実装が何種類かそれぞれPCゲーとして配布されています。

見ての通り、一番上がプレステ2で他がPCなわけですが、少し考えたらプレステ3初期型でプレステ2タイトルがプレーできることに思い至りました。これならUSB接続のみに絞ることが出来てハッピーです。
しかしPS3とINFINITASはコントローラーがオフィシャルなものかチェックされるため普通にコントローラーとして実装しても非公式品とバレてしまい動きません。コントローラーとしての仕様もそれぞれ異なるため適当な出来合いの基板ベースで作れない、困った…

マイコンプログラミング編

仕方がないのでUSB機能の載ったマイコンの勉強から始めましょう(は？)。全部自分で書いた方が早いです。ピン数が多くてUSBトランシーバーが内蔵されている、そんなに高くないマイコンとして個人的に一番オススメなのは
AT90USB646 - 8-bit AVR Microcontrollers
これですかね。チップ自体は500円ちょっと、48ピンもGPIOが引き出せます。

実装すべきファームウエアは実機のリバースエンジニアリングで得るよりほかありません。自作コントローラーの最大のコミュニティであるGIMXのadmin、matloさんがUSBスニファの使い方などを公開してくれているので、ありがたく使わせて頂きましょう。
github.com
USBのホスト側とゲスト側、両方のコネクタを持つBBBというミニPCをUSBの信号中継器のように使って、通ったパケットを全部dumpする感じですね。USBケーブルを使って通信している以上、原理上コントローラーの全ての動作が確認できます。ビューワにはWiresharkを使えて非常に便利です。[PS3]-[BBB]-[コントローラー]という構成でPS3との通信を監視します。結果から言うと特別なパケットのやり取りなどはしておらず(PS3のコントローラーって怪しいVendor definedのUsageをいくつか持っているので疑っていましたが…)、USB HID descriptorとDevice descriptorが同一であればPS3が「既知のコントローラー」として認識してくれるという感じみたいです。オフィシャルの、動くコントローラーからデバイスの情報をベタ書き移植すれば十分動きます。この点、実はGIMXコミュニティーでも知られていなかったようなのでフォーラムに投稿しましておきました。ニッチながら世界初です(？)

お次はマイコンプログラミングですが、5年位前から自作コン自体は作りたくて、マイコンの勉強ちまちましていて本当によかったです。450ページもあるデータシートとにらめっこしつつ、実装します。普段のC++を使ったプログラミングと比べて変わったところがあるとすればレジスタの扱いを強く意識しなければならないのと、ほとんどRAMがない(64kBとか)ってところでしょうか。小さめの簡単なデバイスから順に作って経験を積むうちに大抵扱えるようになりましたが、このマイコンが問題なく扱えるようになるまで年単位で時間がかかってしまいましたね。USB2.0の規格そのものの勉強(バイブル)も結構必要でしたし。
メモリも限られているためUSB HIDとしてのディスクリプタは通常定数としてハードコードしますが、複数のファームウエアを切り替えながら動作することを想定し、全てPROGMEMへのポインタという形で持っておき実行時に参照します。これでメモリを食わずにデカい定数をハードコードすることを避けられます。あとは起動時にポインタにアドレスをセットするようにすればUSB機器としてのファームウエアを切り替えることができます。このトリックについては後日また改めて記事にします。ともあれできたコードがこれ。
github.com
ついでに他機種にも対応可能な汎用性を持たせてみました。コントローラー製作の一番の推しポイントなので詳しめの記事に出来るよう頑張ります。

回路編

あとは基板を拵えます。どうせスイッチ繋ぐだけなので、回路は至ってシンプル。ほとんどワンチップで済んでいます。メンテ性を考慮してメインボードとコネクタボードを分け、それらをケーブルでつなぐことにしました。
f:id:DSKK:20200424170914p:plain
メインボード
f:id:DSKK:20200424170933p:plain
コネクタボード
元所属ラボの基板加工機を借りて生基板から手作りします。
f:id:DSKK:20200424171227j:plain
完成した基板。それぞれ表と裏。
はんだ付け、ファームウエア書き込みなど済ませて組み込みます。
f:id:DSKK:20200424175202j:plain
コントローラー内部。コネクタ同士のクリアランスが広がりメンテ性も向上。

残りいろいろ編　記事書くの飽きた

かなり手を入れたので詳細は個別記事に譲りますが、皿など各種パーツを自作し取り付けて完成！良い自粛ライフになりますように。
f:id:DSKK:20200424175322j:plain
完成したコントローラーの天面。
f:id:DSKK:20200424175353j:plain
こだわりの背面。すっきりした構成に。
f:id:DSKK:20200428141734j:plain
最強になりました
プレー動画もそのうち。というかYoutube等でたまに配信できるといいですね～

AtCoder Beginner Contest 104

真面目にやり始めて日が浅いので、得た学びは遡り切れるだろうと考えて遡る。忙しくはないけど院試などがあり、微妙に時間がなくて悲しい。これも出られていないけどDだけ解いた。
コンテストページ: AtCoder Beginner Contest 104 - AtCoder

D: We Love ABC

  • 'A','B','C','?'(ワイルドカード)のみから成る文字列が与えられる。
  • '?'をそれぞれ好きに'A','B','C'のどれかに置き換えると、'?'の個数を Qとして 3^Q通りの文字列ができる。
  • それぞれの文字列 Tについて部分列(連続していなくても良い)*1として"ABC"が取れる箇所を数え、その個数を足しあげよ。

という問題。
入力例1の"A??C"がわかりやすいが、 Tが"ABAC","ABBC","ABCC"のそれぞれのパターンにおいて、0,1,3文字目を取ったものがカウントされている。これを重複してカウントしないものだとしばらく誤読していた。Ratedならまあまあ悲しくなっていたと思うので、入力例をよく見る癖をつけるべき。

ただ、実はこの誤読した問題、すなわち

  • Tの部分列(連続していなくても良い)のうち、"ABC"となりうる箇所は何箇所あるか？

が解ければあとはそんなに難しくない。それぞれの「"ABC"となりうる箇所」は、 Tの残り |T|-3文字に'?'が R個含まれているとすると 3^R回重複して数えられており*2、この重みをつけて足し上げて行けばよいためである。'?'は全部で Q個なのだから、「"ABC"となりうる箇所」に含まれる'?'の数を S (0 \le S \le 3)としたとき R = Q - Sが成立し、この重み付けの係数は簡単に求まる。

「"ABC"となりうる箇所」として有り得る"???","??C","?B?","A??","?BC","A?C","AB?","ABC"の8通りについて Tから3文字選ぶような全探索を書くと O(|T|^3)で無理だが、後ろから"??","?C","B?","BC"の個数を数えていき、'A'または'?'に出会ったときにこの4通りについて処理をすれば O(|T|)。ひとまずこの方針で、以下に示すようなイケてないコードが出来上がり、通すことはできる。これではちょっとあんまりなので、よりまともな解法を検討していく。
Submission #3086889 - AtCoder Beginner Contest 104

mod = 1000000007
s = input()
n = len(s)
c = [0 for i in range(n)] #c[i]=(s[i:]に存在する'C'の個数)
d = [0 for i in range(n)] #d[i]=(s[i:]に存在する'?'の個数) 以降も、'd'は'?'に対応する
bc = [0 for i in range(n)] #bc[i]=(s[i:]に存在する"BC"の個数)
bd = [0 for i in range(n)] #上と同様、"B?"
dc = [0 for i in range(n)] #"?C"
dd = [0 for i in range(n)] #"??"


if s[-1] == "C":
    c[-1] = 1
if s[-1] == "?":
    d[-1] = 1
for i in range(-2, -n-1, -1): #後ろから2文字目～先頭を見る
    c[i] = c[i+1]
    d[i] = d[i+1]
    bc[i] = bc[i+1]
    bd[i] = bd[i+1]
    dc[i] = dc[i+1]
    dd[i] = dd[i+1]
    if s[i] == "B":
        bc[i] += c[i+1] #今見つけた'B'と、今までに見つけた'C'で"BC"をつくる。後に続くのも同様。
        bd[i] += d[i+1]
    elif s[i] == "C":
        c[i] += 1
    elif s[i] == "?":
        d[i] += 1
        dc[i] += c[i+1]
        dd[i] += d[i+1]

# d[0]は'?'の総数で、問題文中のQに対応する
if d[0] == 0: #d[0]が3に満たないときはバグるので別扱い
    mul = [0, 0, 0, 1]
elif d[0] == 1:
    mul = [0, 0, 1, 3]
elif d[0] == 2:
    mul = [0, 1, 3, 9]
else:
    mul = [1, 1, 1, 1] #以下の処理でmul=[3**(Q-3),3**(Q-2),3**(Q-1),3**Q]となる
    for i in range(d[0]-3): #3をQ-3乗
        mul[0] *= 3
        mul[0] %= mod
    for i in range(3): #あとは順に3倍
        mul[i+1] = (mul[i]*3) % mod

res = 0
for i in range(n-2): #一文字ずつ見ていって足し上げる
    if s[i] == "A":
        res += bc[i+1]*mul[3]+(dc[i+1]+bd[i+1])*mul[2]+dd[i+1]*mul[1]
    if s[i] == "?":
        res += bc[i+1]*mul[2]+(dc[i+1]+bd[i+1])*mul[1]+dd[i+1]*mul[0]
    res %= mod
print(res)

こちらhttps://www.hamayanhamayan.com/entry/2018/08/05/232127で取り上げられているように、最後の数え上げはもうちょっと楽に書ける定石があるらしい。 1\le i \le |T|として、前から i文字目までの'A'の個数 aと'?'の個数 l、後ろから i文字目までの'C'の個数 cと'?'の個数 rを初めに数えて持っておくと、改めて前から見ていって Tの j文字目が'B'のときに 3^Qa_{j-1}c_{j+1}+3^{Q-1}(l_{j-1}c_{j+1}+a_{j-1}r_{j+1})+3^{Q-2}l_{j-1}r_{j+1}個をカウントしていけば良いことになる( k文字目が'?'のときも同様だが、ワイルドカードが一個減るので指数を1つずつ減らす)。計算量は変わらないものの、これで素直に探索を書くことができるようになる。半分全列挙とかでもそうだが、端からではなく真ん中を決めてみると楽になることが結構ありそうなので、この感覚は身につけておきたい。

想定解はDP。全探索書かないならDPだろうなとは思うけど、解説の通りのスッキリしたDPテーブルを書ける感じがしないので、これくらいの問題で練習しておくと良い練習になりそう。勉強のために、ほぼ引き写しになるが書いておく。文字列を前後反転して処理すると簡単なので、想定解とはちょっとだけ表現やDPテーブルの対応が異なる。
dp_{i,j} (0 \le i \le |T|, 0 \le j \le 3)は「 Tの後ろから i文字目までの中から、"ABC"の後ろ j文字を選ぶ場合の数」とする。求めるのは dp_{|T|,3}。 Tの前後を反転させた文字列を改めて Tとして取り直すと、 dp_{i,j}が「 Tの前から i文字目までの中から、"CBA"の前 j文字を選ぶ場合の数」となり少し書きやすい。この場合も dp_{|T|,3}を求めればよい。
推移を考えていく。特に i+1文字目が'?'のときは

  • dp_{i+1,0}=3dp_{i,0}
  • dp_{i+1,1}=3dp_{i,1}+dp_{i,0}
  • dp_{i+1,2}=3dp_{i,2}+dp_{i,1}
  • dp_{i+1,3}=3dp_{i,3}+dp_{i,2}

となる(後ろ三行の右辺にある二項のうち、後者は'?'を"ABC"の列を伸ばすために使っているので1通りしか使い方がない一方、前者は何でもよい文字として使っているので3通り使い方がある)。
その他の場合、 i+1文字目を無視すれば dp_{i+1,j}は dp_{i,j}と等しくなるのでとりあえず前の値をコピーする。コピー後に i+1文字目が何だったかに着目して増分を足してやれば良くて、

  • 'C'のとき、 dp_{i+1,1}+=dp_{i,0}
  • 'B'のとき、 dp_{i+1,2}+=dp_{i,1}
  • 'A'のとき、 dp_{i+1,3}+=dp_{i,2}

となる。
やっていることは意外に全探索と変わりがないが、見通しが良いしインデックスがテーブルの推移にそのまま使えるので以下のようにコードが見やすくなる。
Submission #3086882 - AtCoder Beginner Contest 104

mod = 1000000007
s = input()[-1::-1] #入力のタイミングで文字列を反転してしまう
n = len(s)
dp = [[0]*4 for i in range(n+1)]
dp[0][0] = 1 #0文字から0文字選ぶ方法だけ1で初期化。他は0。
for i in range(n):
    for j in range(4):
        dp[i+1][j] = dp[i][j] % mod #とりあえず一つ前の値はコピー
    if s[i] == "?":
        #dp_{i+1,0}だけは一項少ないので別扱い。
        dp[i+1][0] += (2*dp[i][0]) % mod #コピーしたものに2倍を足せば合計3倍。
        for j in range(1, 4):
            dp[i+1][j] += (2*dp[i][j]+dp[i][j-1]) % mod
    else:
        index = "CBA".find(s[i])+1 #indexを1-originにするために1を加えている
        dp[i+1][index] += dp[i][index-1] % mod
print(dp[n][3] % mod)
所感

前半のアホみたいな解法はまあまずコーナーで落ちないのでその点ではよく、こどふぉやってると上手になってくる感じがある。
とはいえあんな解法ではアレなので(語彙力)、DP上手になりたい。

*1:数列だとこれを部分列と呼んでいる例を見たことあるけど、文字列でも言うのかな・・・"部分文字列"は連続していなければならない気がなんとなくする。

*2:この"ABC"3文字分だけ確定すると、残りの文字列の作り方は何通りあるか？という考え方。作りうる全ての文字列においてこの"ABC"はABC数に寄与している。

AtCoder Beginner Contest 105

競プロのカテゴリは、出て気づいたことや解法などメモしていく予定。まあABC105は出てないんだけど。
コンテストページ: AtCoder Beginner Contest 105 - AtCoder

C: Base -2 Number

「愚直 O(N^2)だけど考察すると O(N)、ただし今回は必要ありません」とかいうの300点くらいだとよくあるし、考察するよりも適当に当たりをつけて探索書いたほうが速いでしょ→解法1。
実は少しだけ考察すると簡単で速い解法がある→解法2。
どちらも想定解とは違ったようなので記しておく。コンテスト出てたら考察せずに解法1書いてた気がする。

解法1

最下位ビットから数えて偶数番目と奇数番目で符号が違うので、とりあえず分けてみる。

偶数番目: S_0(-2)^0+S_2(-2)^2+S_4(-2)^4+\dots=\sum S_{2i} 4^i

奇数番目: S_1(-2)^1+S_3(-2)^3+S_5(-2)^5+\dots=(-2)\sum S_{2i+1} 4^i

和を取るiの範囲はいずれも0から最上位まで。ここで、
m^+=\sum S_{2i} 4^i
m^- =\sum S_{2i+1} 4^i
とする。これらは4進数表記で各ビットに0か1しか立っていない数である*1。

Nは初めの2式の和であるから、 m^+,m^-の満たすべき関係は
m^+-2m^-=N

後で述べるように m^+,m^-の候補はさほど多くないので、有り得る組み合わせを順に試せば通る。ただし、候補数( Mとする)は 10^5のオーダーなので、有り得る M^2個の組み合わせを全て試しているとTLEする。 m^+を仮決めしてから \frac{N-m^+}{(-2)}を候補から二分探索し、適切な m^-が存在するか判定することで O(M\log M)に改善するなどの工夫が必要。

Submission #3011214 - AtCoder Beginner Contest 105

import bisect


def put(a, b):  # 結果の表示
    l = max(len(a), len(b))  # aとbの長さが違うときに壊れるので以下で十分な長さの0を結合しておく
    a = "0" * l + a
    b = "0" * l + b
    s = ""
    for i in range(-1, -l-1, -1):  # 長さの偶奇を考えたくないので逆順に生成してあとで反転
        s += a[i] + b[i]
    s = s[-1::-1]  # 反転
    print(s[s.find("1"):])  # 頭にたくさんついている0を除いて表示


def quad(i):  # 数値を4進数表記の文字列に直す。16→"100"など。
    s = ""
    while i > 0:
        s += str(i % 4)
        i //= 4
    return s[-1::-1]


l = [0, 1]
for i in range(1, 20):  # 候補の生成。最長で20ビット。
    l += [4 ** i + j for j in l]

n = int(input())
if n == 0:  # n==0は出力が空文字になってしまうので別に扱う
    print("0")
else:
    for i in range(len(l)):
        ind = bisect.bisect_left(l, (l[i] - n) // 2)
        if l[i] - 2 * l[ind] == n:
            put(quad(l[i]), quad(l[ind]))
            break

※ m^+,m^-の候補について
Nの-2進数表記での最上位ビットが 2n番目だとする。そのような数は、最小でも 2^{2n}-2^{2n-1}-2^{2n-3}-2^{2n-5}- \dots -2 = 2^{2n}-\frac{2}{3}(2^{2n} - 1)=\frac{2^{2n}+2}{3}>2^{2n-2}になる。制約は 10^9<2^{30}であるので、32ビット目に1が立っている数が Nとなることはない。負の数についても同様に考えると、34ビット長まで候補を持っておけば十分である。4進数では17ビット長に相当する。
本番では「 Nの-2進数表記のビット数はせいぜい2進数表記+1くらい→とりあえず30ビットより多めに持っておけば良いか」でOK。上のコードではとりあえず40ビット(4進で20ビット)持っている。

解法2

入力例など、いくつかの数字の2進数表記と-2進数表記をそれぞれ計算してみて見比べると、結構似ていることに気づく。そこで、手軽に得られる2進数表記をベースとして、-2進数表記に直していくことを試みる。

まずは解法1と同様偶奇性に目を向ける。

  • 偶数番目のビットは-2進数の負号が消えているので、2進数と変わらない。
  • 奇数番目のビットが0である場合も、両方で0になるので変わらない。
  • 差が出るのは奇数番目のビットが1のときである！

奇数 iについて S_i=1である状況を考えてみると、この位が表す数は2進数で 2^i、-2進数で -2^iであるから、この差というのは結局 2^{i+1}であることがわかる。これより、正の数については以下のような手順で答えを求めることができる。

  • \tilde{S}=(Nを2進数表記した文字列)　とする。
  • i=0から始めて、条件「 i番目以下のビットについては-2進数表記、それより上は2進数表記と思って \tilde Sを数値に直した値が Nに一致する」を満たし続けるように \tilde Sを修正しつつ iをインクリメントすることを繰り返す。
  • iが最上位ビットに至ったときの \tilde Sが求める Sである。

途中で行われる \tilde Sの修正は、 iが奇数かつ \tilde{S}_i=1でない限り必要なし。そうである場合は、-2進数の方が 2^{i+1}だけ損しているので 2^{i+1}を足す。これは \tilde{S}_{i+1}に1を足すのと同じことであり、このビット以上は普通の2進数表記であるから、繰り上がり等普通に処理して良い。

文字列に直してから繰り上がり処理とかしたくないので、実装するときは \tilde{S}を作らず数字のまま、2で割りながら最下位ビットを処理していくことになる。入力が負の数だった場合は1行目の処理ができないので、左ビットシフト(-2倍)したものについて答えを求めてから右ビットシフトする必要があることにも注意。

Submission #3011216 - AtCoder Beginner Contest 105

def solve(n):
    ret = ""
    i = 0  # n%2が元の何ビット目にあたるか
    while True:
        if i % 2 == 1 and n % 2 == 1:  # 奇数ビットが1のとき
            n += 2
        ret += str(n % 2)
        n //= 2  # 1ビット右にずらす
        i += 1
        if n == 0:
            break
    return ret[-1::-1]  # 逆順に結合されているので反転


n = int(input())
if n == 0:
    print(0)
elif n < 0:  # 負数は左ビットシフト、一文字落として表示
    n *= -2
    print(solve(n)[:-1])
else:
    print(solve(n))

D: Candy Distribution

これは想定解と同じ。 B_0=0 及び B_n=\displaystyle \sum_{i=1}^n A_iとして累積和を計算しておく。 A_l から A_rまでの和は B_r-B_{l-1}となる。

これが Mの倍数、つまり (B_r-B_{l-1}) \% M=0のとき、 B_r\% M = B_{l-1}\% Mが成り立つ( Mの剰余は 0から M-1であり、 B_r\% M - B_{l-1}\% Mが 0以外の Mの倍数になることはあり得ないので、 Mの倍数ならば必ず 0と言える)。

結局、この問題は B_i\%M=B_j\%Mなる組 (i, j)が何組取れるか求める問題ということになる。累積和の M剰余だけが問題なので、はじめから剰余を取りつつ累積和を作れば良い。あとはそれをソートして左から見ていけば、剰余の同じものがいくつあるか調べることができる(もちろん解説の通りハッシュマップでも良い)。剰余の同じものが n個あったとしたら、組の取り方は {}_n \mathrm{C}_2通り。これを足し上げていく。

Submission #3011217 - AtCoder Beginner Contest 105

m = int(input().split()[1])

b = [0]
s = input().split()
for c in s:
    b.append((b[-1] + int(c)) % m)
b.sort()

l = []
j = b[0]
cnt = 1
for i in b[1:]:
    if i == j:
        cnt += 1
    else:
        l.append(cnt)
        j = i
        cnt = 1
l.append(cnt)
res = 0
for i in l:
    res += i * (i-1) // 2 # i==1のときは自動的に0になってくれる
print(res)

所感

DよりCが難しかった(こなみ)。C問題あたりまではろくに考察せずに書いちゃえば良いと思っていたけど、今回みたいにバグらせずに書くのが大変なパターンもあるので、少しは考察してみるといいかもしれない。考察をする気さえあれば10分そこそこで解けたはず。一方で、筋力をつけて脳死で書けるようにするのもまた大事っぽい。
tex使えるのは綺麗で良いけど、人が読むと思ってブログの文章書くと無限に時間かかることがわかったのでもう少し手を抜いて書きたい。

*1: 4^kをかけながら和を取っていくのは4進数の位取りそのものであり、また、 S_kはすべて0か1であるため。

自己紹介・このブログの目的

自己紹介

同志カツカレーです。物性寄りの物理をやっているM2ですが、理論は詳しくありません。大きく実験が先行している(=理論の構築が遅れている)分野に居るため、どちらかと言えば測定技術の方にフォーカスして研究しています。測定機器の制御やデータ解析が好きです。

Dまで行くと大学院はあと3年あるので、研究が落ち着いてきたこのタイミングで計算科学の方にシフトしようかと思っています。勝手なイメージですが、計算は理論と実験の間にある分野という感じがしますね。ab initioであって公理から演繹されているけどある種「実験的」に結果が得られており、物理的な意味は後から与えられることが多いので。

目的と内容

計算系に寄せようとしたのは「希望の業種が電気系というよりは計算寄りだから」という側面もありまして。D卒で情報系に就活するなら自分のやったことをまとめておくページがあったほうがいいよなあと思ってブログを書きはじめようといった具合です。

・電子工作(Arduinoではなく素のAVRを使うことが多い)

・切削やレーザー等一般の工作

・競技プログラミング

・その他、一般のプログラミング

あたりが書きやすいでしょうか。

ブログは後で見返すために書くものだと思っているので、ノートの清書のような記事を貯めていければと思います。