HACK TO THE FUTURE 2019 本選に行きました。

HACK TO THE FUTURE 2019 本選に参加させていただきました。

予選

20卒パワーで通過しました。20卒に感謝。 

tempura0224.hatenablog.com

本選前日

大学に行ってから東京に行ったので23時に新橋に着きました。華金23時の新橋の治安は最高でした。晩ごはんは一蘭を食べました。

晩ごはん食べる pic.twitter.com/2Dr0NOYOzw

— 🍤てんぷら🦐 (@tempura_cpp) November 30, 2018

晩ごはんを日付変わってから食べてる時点でまぁまぁ危険なんですがホテルについてからも無限に麻雀をしていたら寝るのが5時になりました。

当日

9時に起きれた。えらい。開始直前までTwitterに浮上しない芸をしたら竹雄さんferinさん番兵さんたちに心配されて少し申し訳なくなりました。

ところで今回からオンサイトでプーさんを持ち歩くことにしました。よろしくお願いします。

#HTTF pic.twitter.com/lGIguCUQ4T

— 🍤てんぷら🦐 (@tempura_cpp) December 1, 2018

コンテストは何もわからなくて、スキルを均等に満タンにあげて、そこからよさそうな任務を受けていく感じしか書けませんでした。一応スキルレベルが満タンになる前でも超良さそうなものがあったら取るようにはしたら少し伸びました。スキル上げの順番をよき感じにするのを思いつけなかったのはひどいなぁ。

結果は35人中の17位なのでギリギリ上位。経験の浅さを考えると善戦したほうかなと。

デバッグ方法をSubmitしか知らないので何かを実装するたびに提出していたら凍結時点では10位で、少しだけ夢を見れました。

コンテスト後の企業説明がまったく頭に入ってこなくて申し訳ない気持ちになりました。なんかプロスピの写真っぽいものを見たような気はする。あとJobsに求人が出たのをみて待遇すごくいいねっていう話をしました。

懇親会ではいろんな人と初めましてしました。ざきさんとかMdさんとか同じ大学なのに初めましてが東京なのウケるwって感じでした。

懇親にうつつを抜かしていたらピザ争奪戦に敗北しておなかが空いたのでferinとc7c7さんと春日亭に行きました。c7c7さんにホテルどこか聞いたら同じで笑いました。ちなみに安心お宿新橋汐留です(いつもの)(実家のような安心感)。

翌日

みんなでボドゲをする約束で、12時ごろ集合だったのですが起きたら14時でした。まじでごめんなさい。15時チェックアウトの安心お宿に心からの感謝を。

結局ボドゲ会には16時ごろに着きました。楽しかったです(小並感)。

がやがや pic.twitter.com/b3bUhQvmtN

— 🍤てんぷら🦐 (@tempura_cpp) December 2, 2018

 晩ごはんにはShinya Kato も来てくれて中華を食べました。

竹雄さんと一緒に帰って新幹線からABC114に出たんですが、竹雄さんがCのデバッグで冷えてるのを眺めながら酒を飲む邪悪をしました。帰ったら頭が痛くなりました(自業自得)。

竹雄さんとはまたDDCCでと言って別れたんですが大阪人どうしだし関西で会えばよくないですか？(関西オンサイトの開催が待たれる)

終わりに

HTTF2020も絶対出たいんですが新卒優遇がないので精進しないとなぁ。

次のオンサイトはドワンゴ本選です、参加者の皆さんよろしくお願いします。

CODE FESTIVAL 2018 参加記

CODE FESTIVAL2018に参加したのでスマホコーディングについて書きました。

本選

案の定ホテルで二度寝をするなどしていたら到着がかなりギリギリになって焦る。

とりあえずAを投げたあとBもまぁ式はすぐに書けるので適当を投げる。

確認したらAがMLE、BがWAだったので絶望する。

Aのlong long をintに直したら通る。

Bをちょっと書き直したけど通らないのでやめてCに行く。

CはCHTのCなのでCHTを貼るだけをすると通る(ごめんなさい)。

順位表をみるとEが異常に解かれていたのでEに行く。EはsEgmEnt trEEのEなので貼ると通る。根拠はこの速度で解かれるならこれくらいしかなさそうなこと、正当性はACすることから分かります。

D、最初普通に略称になる回数が1番多い文字列(同じ文字列内で何回数えてもいい)だと誤読して真ん中で場合分けするいつものじゃんをやると当然嘘。各文字列内では1回しか足しちゃダメなことに気づいてboolにし直したりmapで管理したりをするとTLE。冷静になるとpair<int,int>で(ある文字列の個数、最後に足したindex)をするとO(1)で管理できることに気づくので直してAC。パーカーを獲得して安堵。

Fが全然解かれていないのでGに行く。3乗のDPはわりとすぐに生えるので必死に高速化を考えながら式を眺めるとCHTですねとなるけど一生バグる(ちなみに枝刈りのほうには気づかなかった)。なんとか直してAC。

順位表を見ると賞金を得るにはFが必要だったので考えるけど何もわからなくてタイムアップ。

結局2400点で31位。賞金圏内とは点差だけ見ると300点なのでちょっと悔しい結果。

チームリレー

僕は最初Gが回ってきたけど完全に無理なやつだったのでHを強奪して考察をする。意気揚々と書きに行くとサンプルがあわなくてデバッグしたらmod逆元がバグっていてはいとなる。残り15分くらいで出したコードがWAするけど何でかわからなくてそのまま終わり。IHさんが終了30秒前ACを決めてかっこいいなぁとなる。

ところでバグはkとすべきところをn-kにしていたからで、終わって3分くらいしてから気づいて投げると通ったので本当にごめんなさいとなる。通セてれば肉だったらしい。DPとかの遷移はあっていて最後の締めの足すだけのところで間違えていたので誰も気づけなかったというやつなんですが、こういう詰めの甘さが本当に嫌になって自己嫌悪で死んでた。

懇親会

お昼のフリータイムもそうだけど意外と認知されていてびっくりする。だいたいスマホコーディングの人という認識だった。今はもうほとんどやっていませんが、当時の環境とかを聞かれたのでいくつか答えると

エディタ...AtCoderコードテスト

コンパイル...AtCoderコードテスト

デバッグ...AtCoderコードテスト画面でprintfデバッグ

キーボード...普通にスマホの英字キーボードでフリック入力を頑張る。

ライブラリ...なし。必要になったらAtCoder Problemsで過去の自分の解いた問題を漁って見つける。

辞書登録...特にしていないけど予測変換で勝手に出てくる(例えばrと打つと第一候補がrep(i,n)で第二候補がreturn になってる)

つらいこと...AtCoderのコードテストは有能エディタなので中括弧はちゃんと自動インデントされるから意外と快適。だけど[を開いた状態でうっかり改行をしてしまうと自動インデントがバグってスペースが20個くらい挿入されるので死ぬ。

スマホでの成績...最近だとABConlyはスマホでも30分くらいで全完できる。ARCとAGCでは橙パフォまでは1回ずつ出しているはず。

今後スマホでコーディングする予定...二度とやるかバカ。と言いたいんですがたぶんDDCC予選はスマホで出ます。落ちたら笑ってください。

こんな感じです(他に気になる点があるとリプなりコメントなりをいただけると追記します)。縛りプレイをしたくなったらやってみるといいと思います。

なんか何の記事かわからなくなりましたがいろんな方と喋れて楽しかった。同じ大学の人と初対面を果たすなどした。大学でやれ。

感想とか

パーカーとタンブラーを獲得できたり会いたかった競プロerにお会いできたので最低限のToDoは果たせたはず。初参加だったけど超楽しめた。

ただ本選もリレーもわりと後悔を残してしまったので来年必ずリベンジをしにきます。特にリレーの2byteは絶対取り返してやる。食べ物の恨みはでかい。

しかしもう少し早く競技プログラミングを始めていたかったなぁ。。。

HTTF2019予選 ばらばらロボット

HTTF2019予選に参加しました。マラソンは初挑戦だったのでメモがわりに。

ランダムに1マス変えてみてスコアがよくなれば採用する山登りをしました。

問題→A - ばらばらロボット

コンテスト中

0:00 問題を読む。とりあえず#は使わないと決意(邪魔だし実装も面倒になりそうなので)

0:07 とりあえず白紙を出してみる(80940点)

0:36 .TDをrandom出力したものを提出(66336点)

TとDだけにしたのはこの時点でシミュレーションがDとTしか書いてなかったからだけどどうもTとDは微妙っぽいことがわかったので結果としては収穫だった。

0:45 なんか提出してみたくなったので白紙からTとDだけで山登りしたやつを提出(76065点)。山登りで白紙からスコア下がるのなんでやねん。

1:05 バイトに行かなきゃいけない時間になったのでとりあえずもう1回出してみる(80162点)。山登りとは。

4:18 バイトから帰ったので再開。バグの原因はxとyを逆にしてたからだった。競技プログラミング初心者か？(実際始めてから1年経ってないので初心者なんですね。)そこだけ直して提出(107803点)。やっとまともな点数が出たので安堵。

4:30 やっとLRも実装して提出(91196点)。何でやねん。

4:37 if文でelseをつけるのを忘れていたからだった。はぁ。DTよりLRのほうが効果的だらしいのでDTよりLRに変化させる確率を高く設定してみる。これで提出すると118343点。暫定42位だったので本選いけるのでは？となる(20卒なので20卒内25位で本選に進めるため)。

6:06 上の提出の時点ではループ回数が3000回だったので高速化を考える。変更するマスを通るものだけ再計算するようにする。最初は通るものも変更箇所以降だけを再計算することにしようとしたけど頭がバグったのでやめた。この改善でループ回数が20000回まで増やせたので提出(124795点)。26位に浮上して本選ありがとうという気持ちになる。

7:05 適当にパラメータとかいじって遊ぶけど目立った収穫なし。焼きなましを書いて提出したら点数が下がる。終わってから気づいたけど温度管理でバグってた(1文字変数を競合させるのをやめなさい。)

7:33 4個以上が集まるマスも減点してみると微増(125040)。結局これが最終結果になった。あとは適当に評価関数をいじって終わり。7分前に提出したコードが80682点で爆笑した。

コンテスト後

DTは完全に不要でLRだけでいいらしい。あとなぜか初期値は.よりLのほうが強いらしい。

→DTをなくすと場合わけが減った分とかでループ回数を3万近くまで増やせて125689点

ちなみに全部Lのtextを提出すると82374点で確かに白紙より強いので気づくとしたらそういうところからなのかなぁ。

焼きなましのバグに気づいて直す

→129733点。これコンテスト中に気づいてればと思ってコンテスト中のを直してみたけどいまいち変わらなかった。

TLのプロたち「LRしか使わないなら変更の影響を受けるのはそのマスの上で回転するやつだけ(Sは関係ない)」

→ループ回数が54000回になる。131097点。

プロたち「同じコマンドは圧縮できる」

→ループ回数が12万回まで増える。132825点。

(焼きなまし何もわかってないので適切な温度管理をすればもう少し伸びそうな気もする) 

感想

結果は37位。マラソンデビュー戦にしてはなかなかでは？

バイトで3時間抜けたのはやっぱりちょっと痛かったけど本選には進めそうでよかった。ありがとう20卒。

アルゴに比べて実装重めだけどそれを加味してもバグらせすぎなので反省しましょう。

今後はマラソンも積極的に参加してみようかな。

FORCIA Summer Internship 2018 参加記

フォルシア株式会社のインターンに参加しました。記憶があまりないので想像で補って書きます。言えないこともあるのでさらに曖昧な文章になります。文章力もないのでNoiminさんのブログ(http://noimin.hatenablog.com/entry/2018/09/18/233705)を大いに参考にしました。例えば会社名にはリンクを飛ばすといいということを学びました。彼女のほうが僕より1週間後のタームのはずなんですけどね。時系列壊れる。

－４０日

　今は数学科の院生をやってるんですけど、修士を出たら就職しようと思っているので流石に何もしないのもなぁと思っていたらAtCoderJobsに面白そうなインターンを見つけたので応募しました。Jobsに求人を出してくださるとターゲットが明確に自分に向いてる感じがあって超応募しやすいんですよね。AtCoderさんありがとうございます(このブログでは多方面に媚を売っていこうと思います)。

　有給なのも大きくて、これは給料がいただけるからというよりは、お金出してまでインターン生を募るならがっつりと経験を積ませていただけるんじゃないかっていう。

－３５〜－２０日

　応募したはいいんですけど、書類選考ってだいたい研究内容とか実績とか書かないといけないわけで、ここで詰みました。なんちゃって数学科なので大した研究をまだ開始できていないうえに書いたところでインターンの内容とかすりもしないし、プログラミングを始めたのも今年に入ってからなのでろくな実績もなく。ほげもちと相談した結果「AtCoder黄色なんで地頭は悪くないと思います」をそれっぽい感じの文章にして出しました。これで通ったら面白いなって言ってたら通りました。面白かったです。Rust検索エンジン開発コースに決まりました。

０日目

　前泊しました。前泊の宿泊料は負担しないよって言ってくださったんですが給料いただける時点でプラスじゃんという雑勘定をしました。場所は安心お宿新橋汐留

店https://www.anshin-oyado.jp/shiodome/にしたんですがすごくオススメです。大浴場が24時間使えるだけで優勝なんですがホテルにあって欲しいものは大きなベッドを除いて全部あります。あと晩ごはんはてんぷらを食べました。前日だしRustでセグ木くらい書いてから寝ようと思ったら寝れなくなりました。そもそもC++でもセグ木を空で書けないことが判明しました。

そろそろちゃんとしたインターンのブログに切り替えます。

１日目

　朝適当に来た電車に乗ったら逆向きでした。あとはいい1日だったと思います。お昼ご飯はカルビを食べました。この日は与えられた課題(あとで詳しく書きます)のコードを読んで、コードを読めば誰でも書けるようなものを書いたりしてたら終わりました。

２日目

　僕の課題は雑にいうと作りかけのアプリに新しい検索クエリを実装することでした。と言ってもすでに社員さんが書いていたアルゴをいい感じに組み込めばよかったんですが、1から書こうとして破滅をしたりしていました。この日のお昼ご飯はケバブでした。

３日目

　今回扱うデータベースに対してはいい感じに動くものが実装できたので、他のアプリでも使えるように汎用化した作りにしようとしました。汎用化しようと思うといろんなケースが想定されたり、今回実装したクエリが他のクエリとかなり異なっていたりで考えなきゃいけないことが多くて、開発してる感がありました。slackのステータスをてんぷらにしていたらてんぷら屋さんに連れて行っていただくことになって、自ら志願して共喰いをするサイコパスになってしまいました。

４日目

　昨日からの作業が昼頃に一応片付いたのでアルゴリズム早くならんかなぁみたいなことを考え始めました。とはいえ最終発表まで全然時間がなかったのですぐに改善しそうな定数倍だけいじることにしてガチャガチャやってました。僕は基本的に2/3から3/4くらいにして満足してたんですがなんか次のタームの人が爆速にしたらしくてすごいです。この日のお昼ご飯は海鮮丼でした。いいものの食べ過ぎで胃が東京に染まりそうだったので晩ごはんでは博多ラーメンににんにくを多めに入れて中和しました。

５日目

　お昼ご飯は社内の競プロerさんたちとピザを食べました。競プロerさんとのお食事ということで当然アイドルトークで盛り上がりました。最終発表があったのですが僕以外の３人はアレクサで面白そうなアプリを提案していたり特徴語を抜き出してデータ分析していたりですごくて圧倒されました。しょうがないのでインターン参加者唯一の関西人らしく適当にボケをはさんでごまかしました。それなりにウケてよかったです。懇親会ではメンターさんとナブラ演算子ゲームをしました。あれはたぶんシラフでやるゲームではないんですが酔っててもできないのでどういう時にやるのが適切なのか謎です。

何も考えていなかったら宿を取っていなかったので安心お宿に電話してみたら余裕でした。神か。

６日目

　東京住みの友達とダラダラしてから大阪に帰ってABCに出たら社員さんのAtCoderアカウントが特定できました。

８日目

　人事の方からマイナンバーカードを忘れて帰ってるよと連絡がありました。ごめんなさい。

１６日目

　無事受け取りました。

まとめ

　分からないことだらけで反省すべきところも多々ありますが、その中で(今後ちゃんと勉強することを仮定すれば)社会に出てもなんとかやっていけそうな自信も得られたので良かったと思います。あと社内の雰囲気がすごく肌に合っていたので勤めたい企業像も具体的になりました。

　あととにかく競技プログラミング(とバイト先の塾のVBA)でしかプログラミングをしたことがないという状態から脱出できてよかったです。結局アルゴリズムまで踏み込みきれなくて実装中心になってしまいましたが、むしろ僕にはちょうどいい課題だったように思います。社員さんからも直接ポテンシャル採用だと言われましたが、ほんとによく採ってくださったと思います。選んでくださった社員さんや、迷惑をかけ続けたメンターさんには(申し訳なさと)感謝しかありません。

　後悔としては(Noiminさんと丸かぶりするけど)メンターさんたちにもっと厚かましく色々聞きにいけばよかったというのと、他のインターン生徒との交流ですね。たぶんアレクサの人は僕と交わした口数よりアレクサに話しかけた回数のほうが多いと思う(それはそう)。

　なんか最後に感動的な文章を書きたかったんですが不可能なので終わります。あとフォルシアさんの魅力も全然書けてない気がするのでインターンがこれからの人たちはぜひ実際に参加して直接みてもらったほうがいいんじゃないかなぁと思います。その際はてんぷらが行けって言ってたって言ってください。たぶんてんぷら屋さんに連れて行ってもらえると思います。

PCK2017 予選11 ネットワークの課金システム

自分のブログの存在を完全に忘れていた(おいおい)。問題を解きました。

Charging System for Network | Aizu Online Judge

問題概要

頂点数Nの木(各辺s-t はコストc[s,t]を持つ)と整数Kが与えられる。以下のクエリをQ回処理する。

• send : 2頂点u-v間のパスのコストの総和を答える。ただしコストがKの倍数である辺は0として計算する。
• add : 頂点uから伸びているすべての辺のコストをd増やす。

制約は 1<=N,K,Q<=10^5

解法

明らかに「Kの倍数は0とする」の部分が厄介です。

addクエリは頂点に足された値を記録しておけば(これをa[u]などと書きます)辺u-vのコストは c[u,v]+a[u]+a[v] と計算できるが、sendクエリで普通に辺を1つずつ見ていくとO(N)かかってしまってダメ。

「Kの倍数は0とする」の操作をaddに押し付けることができればsendはオイラーツアーなりなんなりで高速に答えられるようになるけど、今度はaddで頂点の周りの辺をすべて見ないといけないのでO(N)かかってしまう。

八方塞がりに思えるのですが、ここでHL分解の以下の性質を思い出します。

(HL分解そのものについては書かないです、ごめんなさい(僕はこの方の記事で勉強しましたHeavy-Light Decomposition - beet's soil))

• 各頂点についてそこから出るHeavy edgeは高々2本 
• 各パスについて、通るLight EdgeはO(logN)本

するとこのような折衷案が思いつきます。

• addクエリでは、頂点に足された値を記録した後、Heavy Edgeの値を更新する。
• sendクエリでは、Heavy Edge は更新されているのでそのまま利用して、Light edge については1つずつ計算する。

上記の性質により、addクエリでは2箇所、sendクエリではO(logN)箇所しか計算をしないので高速に行うことができます。求めたいものは区間和なのでセグメントツリーを用いることで、addクエリをO(logN)、sendクエリをO((logN)^2)で処理でき、全体計算量は最初の入力等も含めてO(NlogN+Q(logN)^2)となり無事解くことができました。

実装↓ (雑然としているのでアです)

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3100945

 

ICPC2018 国内予選 参加記

ICPCお疲れ様でした。先に結果だけ書いちゃうとABCDの4完で30位でしたが学内順位の問題でアジアには行けませんでした。

以下軽い振り返りです。

メンバー

• tempura0224 ぼく。ABとDorEを担当する予定だった。
• zunda1st BCあたり担当。
• chocorusk EorD,特に数学担当。

全員数学科で競技プログラミング経験は3人合わせて15ヶ月。

コンテスト

とりあえず予定通りぼくがAを開いて解く。

流石にすぐにできてBを見たらできそうだったからそのままやる。適当にやりすぎて1WA(悲しい)。

Cの進捗をzundaに聞くと微妙っぽかったので一緒に考えるとなんか解ける。適当に実装したら今度はちゃんと通る。

chocoruskがDは全探索でいけるというので全探索を書く。ぼく中心で実装したけどミスりまくって横から指摘されまくる。これ最初からぼくが実装しないほうがよかったのでは。いざ書き上がると一発で通る。

chocoruskたちにEを任せてFGを考える。これが完全に判断ミス(幾何も構文解析もろくにできないのになんで行ってしまったのか)。

トイレに行ったり教室内を走り回ったりしてるとEの解法が生えたので書いてみる。サンプルが全然合わなくて泣く。場合分けと評価の順番をミスりまくっていると教えてもらったので直す。サンプルが最後以外通って「浮動小数点例外」って怒られる。ナニコレ。何が違うのかわからないままコンテスト終了。

反省と感想

これの読者は大体わかると思うんですけど浮動小数点例外は0除算でした。エラーコード136とか言ってくれたらわかったのにっていうのは流石に言い訳でこれに気付けないのは本当にひどい。

弊大学は無駄にハイレベルで5完高速じゃないとダメだったらしいので完敗。

とはいえBのWAがなくてDの実装をchocoruskに任せてその間にEを詰めるとかしてれば無理じゃなかったような気もするので悔しい。まぁ0除算に気付けなかったので完全に論外なんですが。

ぼくは早生まれな関係で来年も出場資格があるらしいので実装力(とタイピング)を鍛えて来年こそはアジア行きたいですね。組んでくれる人見つかるといいな。

ARC094 F Normalization

　はい。ARC094のF問題(F - Normalization)の解法です。解説(aを0、bを1、cを2だと思うと和のmod3が保たれるとかいうやつ)がド天才だったのですが、もう少し思いつけるかもしれない解法でACしたので投稿します。

　といっても結局mod3を見ることにはなってしまうのでそこに至るまでのステップも書いていこうかと思います。

解法

　まず、操作後の文字列はどこかに同じ文字が連続する部分があるということはすぐに分かるのですが、それだけでは条件が足りなさそうです。また、操作の順番によってできる文字列が変わる(というか操作の順番を変えるとそもそも操作ができなくなることもある)ので左から順番に操作するorしないでDPといったことも出来なさそうです。ということで別の方向で考えてみましょう。

　数列や文字列に対して何らかの操作を施すタイプの問題では、

操作の前後で変化しないものに着目する

という方法が有効なことがあります。また、今回のように操作が3種類ある場合すべての操作に対して共通してなりたつものを見つけるとよいです。具体的に今回の問題の操作での個数の変化を見てみましょう。

1. ab→cc　　　a：-1、b：-1、c：+2
2. bc→aa　　　a：+2、b：-1、c：-1
3. ca→bb　　　a：-1、b：+2、c：-1

「2増える」「1減る」という操作を同一視したいなぁという気持ちになりますね(なって。)。この時点でmod3に気づく人もいるかもしれませんが、さらにこれもよくある手法として、「個数の差(和)はわりといい性質を持ちがち」というのがあります。ということで各操作でのaの個数とb,cの個数の差の変化を見てみましょう。

1. ab→cc　　　a：-1、b：-1、c：+2　　b-a：±0、c-a：+3
2. bc→aa　　　a：+2、b：-1、c：-1　　b-a：-3、c-a：-3
3. ca→bb　　　a：-1、b：+2、c：-1　　b-a：+3、c-a：±0

　「aとbの差」「aとcの差」は操作の前後で「3増える」「変わらない」「3減る」のいずれかです。もうわかりますね。操作の前後で「aとbの差」「aとcの差」を3で割った余りは変化しないということです。なるほどここで3で割った余りがでてくるのか、という感じですね。3で割った余りがカギになることに気が付いてさらに考察を進めると解説の方針になるのかなぁ。

　とはいえこれで操作後の文字列に対する重要な性質がわかりました。

1. どこかに 連続している部分がある

2. 「aとbの差」「aとcの差」を3でわった余りは最初の文字列と同じ。

この性質をみたす文字列は本当に全部つくれるのかという問題はあるのですが、実は|S|≠3のときはできるらしいです。(証明は帰納法でできるらしい。解説に書いてた。)ということで|S|=3のときだけ全探索することにして、他は上の条件をみたすようなものを数えるためのDPをします。

　具体的には、dp[文字数][最後の文字][(b-a)を3で割った余り][(c-a)を3で割った余り] のようなdpテーブルを2つもって、1つで「2の条件をみたすもの全部」、1つで「2の条件を満たすが連続する箇所は1つも持たないもの」を計算して差をとるのが楽な気がします。

　ということでこれでこの問題をO(27*|S|)くらいで解くことができました。最初の文字列が連続箇所を持たない場合は答えに1足すのも忘れずに。一応自分のACコードのリンクを貼っておきます。

Submission #2374335 - AtCoder Regular Contest 094

※追記

　少し考察すると「aとbの差」のmod3が保たれるなら「aとcの差」のmod3も自動的に保たれることがわかるため、dpテーブルは、dp[文字数][最後の文字][(b-a)を3で割った余り]と1つ項を減らして計算しても大丈夫なようです。(Submission #2374698 - AtCoder Regular Contest 094)

感想

　本番中にこの性質に気づけていながら手計算の実験部分を間違えていて解けなかったのはちょっと悔しい。|S|=3の場合だけ無理というのも罠でした。短すぎる文字列なら例外がおこりうることには思い至るべきだったなぁ。700点はさすがに嘘な気がするけどとても面白い問題だと思います。