ISUCON9 予選敗退した

ISUCON9。今年は縁あって声かけていただき id:Soudai さんと id:kamipo さんと、「失敗から学ぶISUCONの正しい歩き方」というチームで出場した。

練習会

インターネット上でよく知っている人たちとはいえ 実際に一緒に仕事をしたことも無ければチームを組んで一緒に何かをしたことがあるわけでもない。 予選の2週間前に一度集まって、1日かけて前年の予選問題を再現しつつ試し解きしてみる、という会をした。 言語は3人で共通した得意なものがあるわけではなかったので とりあえずRubyで、ということにした。

そのときの感覚では「やっぱり色んなところで躓くこともあるかもしれないけど 正しく計測して早めに大きな方針を決めて改善をしていけばそれなりの成績には辿り着けるだろう」という感じ。 DB関連はとにかく2人が強いので、自分はアプリケーションコードを如何に正確に早く書いていけるかが勝負になる、と。

当日

練習会のときはそれぞれのMBPで作業したけど コード書くのは共有画面あった方が良さそう、と思い 当日はモニタを1台かりて映しながら作業するようにした。あと自作の Claw44 も持参。 作業環境は万全だった

11:19 初期セットアップ → 2,110

インフラまわりはSoudaiさんに完全丸投げしていたので サーバが立ち上がるまで僕とkamipoさんはマニュアルを読み込む。1台だけ立ち上がったら即git pushしてローカルで動かせるようにしたりしつつ コードを読んで動作を把握する作業。 想像してた以上にすごい作り込まれている クオリティの高いWebサービスになっていて絶句した。

トラブルなどもあったけど 11:19 ようやく初期状態での1回目のベンチマークが回った。スコアは 2,110

11:25 Rubyに実装切り替え → 2,310

まずは初期実装のGoからRubyへの変更。今回はスコアのブレは少なそうだ。 そこからaccess logを切り替えて alp で傾向を分析するといった作業をSoudaiさんに任せつつ、kamipoさんとアプリケーションの動作を追い続ける。

あと明らかにCPUの負荷は高いし3台で動作させて分散させるのはやっていこう、ということでそのへんの作業もSoudaiさんに一任。

13:07 campaign を上げてみる → 4,900

どうやら campaign という値をいじると負荷の挙動も変わってきそうだ、ということで試しに上げて動かしてみる。 タイムアウトなども発生するが どうにかボトルネックを解消して捌けるようにしつつこの数値を上げていければ良さそう、というのは分かってきた

14:03 3台構成稼動 → 2,510

3台でappを起動して 1台は nginx + mysql をメインにして集約、といった構成がやっと動いた。

14:07 index追加、campaign を上げる → 6,410

明らかにindexがなくて遅くなっている items.created_at のあたりにindexを貼って 多少はやくなるはず、ってことで campaign も 2 に上げてみた。 ようやく改善の効果が出てきて大事なボトルネックも見えてくる。ということで昼飯食べつつ今後の作戦会議。

kamipoさんはloginまわりの負荷軽減、Soudaiさんはstaticファイル配信まわりやdeploy環境まわりの整備など、で僕は不変な categories 情報をDBから引かずにapp内で持つように変更する、という方針で動き始める

16:04 get_category_by_id の改善 → 6,730

上記の通り categories 情報をapp内の変数から出すよう変更したものが動かせた。が 思ったほどスコアは改善しなかった…

16:57 login まわり改善 → 8,970

kamipoさんの改善が効いた。

→ 9,650

その後 細々した修正でスコアを上げるも 10,000 までは届かず。そのまま最終スコア 9,650 でフィニッシュ。

最終的な予選通過ラインが 10,000 前後だったようだが そこまでは届かず予選敗退に終わった…

反省点

僕は早く正確にコードを変更していくのが役割だったはずなのに、結局そこで価値を出せなかった。 configure 内で categories情報を settings に入れて get_category_by_id は素早く改善できたものの、その後 /settings のresponseのところも変更しようとして

-      categories = db.xquery('SELECT * FROM `categories`').to_a
+      categories = settings.categories.map do |_, category|
+        category.delete('parent_category_name')
+        category
+      end

という変更を入れてFailするようになってしまい、revertして 動作確認して また失敗して、と原因の切り分けに時間がかかってしまい 40分くらいロスしてしまった… (なんてことはない、parent_category_name情報をresponseから省こうとしてdeleteした結果破壊的な変更になってsettings全体の値が変わってしまうという初歩的なバグ。。)

あとは外部リクエストを複数投げているところはどうにか並行化したいところだったけど GoやNodeならわりと簡単にできそうでもRubyでやるのは知見が無くて簡単には手が出しづらく、踏み込めなかった。 限られた時間内では「確実に出来そうな変更」にとどめざるを得なく、そこ以外のはやく出来そうなところから優先して手をつけることになり、最終的に残り1時間くらいでもう出来ることがなくなってベンチマークガチャを回すくらいしか出来なくなってしまった。 これは単純に能力不足と言うほかない。

3台構成にしようとしててMySQLが疎通しなくてDBのスペシャリスト2人いても苦戦していたところに bind-address 127.0.0.1が原因だって見抜いたことが僕の一番の功績だったかもしれない。

チーム的には…

最後の1時間くらいで出来ることがほぼ無くなって「次の一手」を打てなかったのが厳しかったか… 最初はしっかりaccess logを解析してボトルネックを見つけて、とやっていたけど 最後は「うーん やっぱり /buy が遅いみたいだけど どうすりゃええんや…」みたいな状態で そこから詳細に原因を調べて改善に繋げていくことが出来なかった。外部リクエストの測定も出来なかったし あと数時間あったとしても有効な改善を思い付いて実行できたかどうか分からない。

競技終了後に「これ、『明日もう1回 同じ問題に8時間取り組んでいいですよ』って言われても勝てる気しないっすね…」ってなってしまっていて完敗な感じになってしまっていた。

あとは全体的に作業スピードが遅くて時間に余裕が無くなりすぎていたか…？という気もする。 1人チームの学生さんに負けないくらいに各自がミスなく素早く動いて 最初の数時間をもっと短縮できていたら良かったのかもしれない。おじさんたちももっと精進して頑張らねば。

感想

結果は悔しいものに終わってしまったけれど、練習会・予選当日ともに このメンバーで集中して議論して改善に取り組んでいく過程はとてもエキサイティングで楽しかったです。誘っていただきありがとうございました！！！ また是非このメンバーで一緒に戦いたいな

運営の皆様には今回も良質な問題を提供していただき、ありがとうございました。 本当に 予選であんな盛り沢山の参照実装を用意してくるとは驚きでした。。

あとスタンプめっちゃ気に入ってます

本戦当日に妻と花火大会に行く予定でチケット買ってしまっててダブルブッキングになる不安があったんですが、心おきなく一緒に花火を楽しんでこようと思います。。。

電子工作 5作目・Claw44

Keyboard

f:id:sugyan:20190717112703j:plain

HelixPico、Mint60、ErgoDash、Corne Cherry に続いて、自作キーボード 5作目。

今回作ったのは Claw44。 この記事はClaw44を使って書いています。

booth.pm

なぜClaw44を選んだか

Corne Cherryで概ね自分の理想は実現されていたけど、前回の記事に書いた通り

親指用のキーは下部に3つ 押しやすい位置に斜めに並んでいるのだけど、 どうもそれでも最内側のキーがまだ少し遠くて押しづらい…。

というのが唯一の懸念だった。

そこで登場したClaw44。設計者の id:yfuku さんが、まさにそこにこだわって作られている。

blog.yfuku.com

ので自分のニーズにとても一致している。 Corne Cherryと同様にコンパクトで最小限のキー数なColumn-Staggered配列というのも理想的。

組み立て

前作Corne CherryのときはチップダイオードやLEDの表面実装が難しすぎて泣きそうになっていたけど、Claw44はそういう高難度の要素が殆どなかったので、 ビルドガイド を読みながら組み立てるだけで だいぶラクに完成させることができた。

キースイッチ・キーキャップ

今回のキースイッチは "Blue Zilent" 65g で。

yushakobo.jp

キーキャップは前作と同じ XDA Blank を使った。

talpkeyboard.stores.jp

親指の部分で 1.25U のものがどうすべきか分からないけど 今はお試しで送っていただいた傾斜つきのものを使わせていただいている。

キーマップ

前作同様、自分にとって最適のものを設定。

--- keyboards/claw44/keymaps/default/keymap.c   2019-07-08 13:16:45.000000000 +0900
+++ keyboards/claw44/keymaps/sugyan/keymap.c    2019-07-08 15:26:53.000000000 +0900
@@ -38,15 +38,15 @@
 const uint16_t PROGMEM keymaps[][MATRIX_ROWS][MATRIX_COLS] = {

   [_QWERTY] = LAYOUT( \
-  //,--------+--------+---------+--------+---------+--------.   ,--------+---------+--------+---------+--------+--------.
-     KC_ESC , KC_Q   , KC_W    , KC_E   , KC_R    , KC_T   ,     KC_Y   , KC_U    , KC_I   , KC_O    , KC_P   , KC_MINS,
-  //|--------+--------+---------+--------+---------+--------|   |--------+---------+--------+---------+--------+--------|
-     KC_TAB , KC_A   , KC_S    , KC_D   , KC_F    , KC_G   ,     KC_H   , KC_J    , KC_K   , KC_L    , KC_SCLN, KC_QUOT,
-  //|--------+--------+---------+--------+---------+--------|   |--------+---------+--------+---------+--------+--------|
-     KC_LSFT, KC_Z   , KC_X    , KC_C   , KC_V    , KC_B   ,     KC_N   , KC_M    , KC_COMM, KC_DOT  , KC_SLSH, KC_RSFT,
-  //`--------+--------+---------+--------+---------+--------/   \--------+---------+--------+---------+--------+--------'
-                       KC_A_DEL, KC_G_EN, KC_L_SPC, KC_C_BS,     KC_C_BS, KC_R_ENT, KC_G_JA, KC_A_DEL
-  //                 `----------+--------+---------+--------'   `--------+---------+--------+---------'
+  //,--------+--------+--------+--------+--------+--------.   ,--------+---------+--------+---------+--------+--------.
+     KC_TAB , KC_Q   , KC_W   , KC_E   , KC_R   , KC_T   ,     KC_Y   , KC_U    , KC_I   , KC_O    , KC_P   , KC_BSLS,
+  //|--------+--------+--------+--------+--------+--------|   |--------+---------+--------+---------+--------+--------|
+     KC_LCTL, KC_A   , KC_S   , KC_D   , KC_F   , KC_G   ,     KC_H   , KC_J    , KC_K   , KC_L    , KC_SCLN, KC_QUOT,
+  //|--------+--------+--------+--------+--------+--------|   |--------+---------+--------+---------+--------+--------|
+     KC_LSFT, KC_Z   , KC_X   , KC_C   , KC_V   , KC_B   ,     KC_N   , KC_M    , KC_COMM, KC_DOT  , KC_SLSH, KC_R_ENT,
+  //`--------+--------+--------+--------+--------+--------/   \--------+---------+--------+---------+--------+--------'
+                       KC_LALT, KC_LGUI, KC_L_SPC,KC_C_BS,     KC_C_BS, KC_RSFT , RAISE  , LOWER
+  //                 `---------+--------+--------+--------'   `--------+---------+--------+---------'
   ),

   //   \ ^ ! & |  @ = + * % -
@@ -55,23 +55,23 @@

   [_RAISE] = LAYOUT( \
   //,--------+--------+--------+--------+--------+--------.   ,--------+--------+--------+--------+--------+--------.
-     _______, KC_BSLS, KC_CIRC, KC_EXLM, KC_AMPR, KC_PIPE,     KC_AT  , KC_EQL , KC_PLUS, KC_ASTR, KC_PERC, KC_MINS,
+     KC_ESC , KC_EXLM, KC_AT  , KC_HASH, KC_DLR , KC_PERC,     KC_CIRC, KC_AMPR, KC_ASTR, KC_LPRN, KC_RPRN, KC_DEL ,
   //|--------+--------+--------+--------+--------+--------|   |--------+--------+--------+--------+--------+--------|
-     KC_LPRN, KC_HASH, KC_DLR , KC_DQT , KC_QUOT, KC_TILD,     KC_LEFT, KC_DOWN,  KC_UP , KC_RGHT, KC_GRV , KC_RPRN,
+     KC_LCTL, KC_UNDS, KC_PLUS, KC_LCBR, KC_RCBR, KC_TILD,     KC_GRV , KC_MINS, KC_EQL , KC_LBRC, KC_RBRC, _______,
   //|--------+--------+--------+--------+--------+--------|   |--------+--------+--------+--------+--------+--------|
-     _______, _______, _______, _______, KC_LCBR, KC_LBRC,     KC_RBRC, KC_RCBR, _______, _______, _______, _______,
+     KC_LSFT, KC_1   , KC_2   , KC_3   , KC_4   , KC_5   ,     KC_6   , KC_7   , KC_8   , KC_9   , KC_0   , _______,
   //`--------+--------+--------+--------+--------+--------/   \--------+--------+--------+--------+--------+--------'
-                       _______, _______, _______, _______,     _______, _______, _______, RESET
+                       KC_LALT, KC_LGUI, KC_L_SPC,KC_C_BS,     KC_C_BS, KC_RSFT, RAISE  , LOWER
   //                  `--------+--------+--------+--------'   `--------+--------+--------+--------'
   ),

   [_LOWER] = LAYOUT( \
   //,--------+--------+--------+--------+--------+--------.   ,--------+--------+--------+--------+--------+--------.
-     KC_F1  , KC_F2  , KC_F3  , KC_F4  , KC_F5  , KC_F6  ,     _______, KC_EQL , KC_PLUS, KC_ASTR, KC_PERC, KC_MINS,
+     _______, KC_F1  , KC_F2  , KC_F3  , KC_F4  , KC_F5  ,     KC_F6  , KC_F7  , KC_F8  , KC_F9  , KC_F10 , _______,
   //|--------+--------+--------+--------+--------+--------|   |--------+--------+--------+--------+--------+--------|
-     _______, KC_1   , KC_2   , KC_3   , KC_4   , KC_5   ,     KC_6   , KC_7   , KC_8   , KC_9   , KC_0   , _______,
+     _______, _______, _______, _______, _______, _______,     KC_LEFT, KC_DOWN, KC_UP  , KC_RGHT, _______, _______,
   //|--------+--------+--------+--------+--------+--------|   |--------+--------+--------+--------+--------+--------|
-     KC_F7  , KC_F8  , KC_F9  , KC_F10 , KC_F11 , KC_F12 ,     _______, _______, KC_COMM, KC_DOT , KC_SLSH, _______,
+     _______, _______, _______, _______, _______, _______,     KC_HOME, KC_PGDN, KC_PGUP, KC_END , _______, _______,
   //`--------+--------+--------+--------+--------+--------/   \--------+--------+--------+--------+--------+--------'
                        RESET  , _______, _______, _______,     _______, _______, _______, _______
   //                  `--------+--------+--------+--------'   `--------+--------+--------+--------'

結局 最内側の親指は相当手を広げないと届かないので使わない感じになっている…

使用感

最初は少し戸惑ったけど、慣れるとまったく気にならないレベル。 仕事用に会社でずっと使い続けていて、ほぼ不満無く快適に毎日使っている。

ただ普通のXDAキーキャップだと角が指に当たって少し痛くなるので やはり傾斜つきのものが欲しいな、というのが最近の気持ち。1.25Uの外隣のキー用に2個だけ何か欲しい…

TensorFlow.jsがChromeでWebWorker上でもWebGL backendで動く

TensorFlow WebWorker

僕も以前にWebWorker上でTensorFlow.jsを使おうとして WebGL backendで動かないことに気付いて諦めていたのだった。

memo.sugyan.com

…と思っていたのだけど、どうも先月くらいの @tensorflow/tfjs@1.2.2 あたりから ChromeではOffscreenCanvasというのを使ってWebWorker上でもWebGL backendで動くようになったようだ。 試してみたところでは 動くのはChromeのみで、SafariやFirefoxではCPU backendのまま。

動作を確認できるdemoページを作ってみた。

https://sugyan.com/tfjs-webworker/

ボタンを押すと適当にmodelをloadして、何回かrandom inputに対してpredictを計算する。

普通に MainThread上で実行すると、WebGL backendが使われて predictの計算などは高速になるのだけど、最初のloadや1回目の計算のときなどに重い処理が走り、UIの更新がストップしてしまう。 f:id:sugyan:20190801125155g:plain

Platform and environment  |  TensorFlow.js  |  TensorFlow

これを回避するために、MainThreadではなくWebWorker上で計算を行うようにすると、UIの更新がブロックされずに計算が出来るのだけど、従来だとWebWorker上ではCPU backendにfallbackしてしまうために計算がとても遅くなってしまっていた。

f:id:sugyan:20190801125825g:plain

これが、Chromeだと、UI更新をブロックせずにWebWorker上で高速に計算することが出来る。

f:id:sugyan:20190801125446g:plain

これは嬉しい。 すべてのブラウザでもサポートされてくれると嬉しいな〜〜〜

https://github.com/sugyan/tfjs-webworker

TOKYO IDOL FESTIVAL のタイムテーブル画像化ツール 2019

TypeScript GoogleAppEngine Go ImageMagick

3年前に作り始めたのがきっかけで、今年もTIFのタイムテーブルが公開されたので作ってみた。

memo.sugyan.com

Backend

昨年までのものをほぼ使い回しで出来るかな、と思っていたのだけど、今年は動かすプラットフォームを変えてみることにした。

今までは HerokuでRails appとして動かしていたのだけど、いつも月末になるとfree dynoを使い切ってしまい課金しないと見られなくなってしまっていた。 開催直前で使えなくなってしまうのはちょっと致命的だし困る… し、そもそも別にHerokuでRailsでないと動かないわけでもないので別のところに移しても問題ないな、と。

最近はBackendはGoで書きたい気分だったし、Google App Engine の Go1.12 Standard Environment で。

cloud.google.com

何故今までHeroku+Railsを使っていたかというと 画像生成の部分で rmagick を使っていたから、というのが大きい。 最近のGo 1.11/1.12 Standard Environmentは もうGAEのAPIに縛られた特殊なアプリ(ていうと言い方アレだけど)ではなく もはや普通のWebアプリとして作ってそのまま動かせる感じになっている。 imagemagick も普通に入っているので使える。のでGAEを使えない理由は無かった。

また、作成したタイムテーブルをリンク共有する機能でDBを使っていたけど、これはURLに使うユニークなIDと選択したステージのIDリストをひもづけるだけのものなので Cloud Datastore がむしろ用途として合っている。

ImageMagickでの画像生成

以前は rmagick に頼ったコードをRailsで書いていたけど、機能自体はImageMagickのCLIでも実現できるもののはずなので、Go版ではライブラリなどを使わず convert コマンドのみで画像生成を実装した。

タイムテーブル画像は同じサイズの細長い画像を縦に連結する形で作られている。合成するアイテム数が分かっていればそのサイズのcanvasを生成してしまって描画する位置を調整していけば良いのだけど、日付の列は -gravity Center で中央寄せで annotate したものを作りたい、などの要求があったのでやはり横長を複数連結する方式にした。

convert -size 100x30 xc:'#303030' -fill white -gravity Center -annotate +0+0 Hello out.png

といったコマンドで f:id:sugyan:20190722224424p:plain のような画像を作れる。 こういったものを複数作って、最後に -append してやれば良い。 …のだけど、いちいちtempfileに出力してファイル名を管理して…というのはやりたくない。 調べてみるとMIFFというformatを使ってstreamingに処理することが出来るらしい。 それぞれの出力をstdoutに繋げて出力して、pipeでまとめて受け取って使える。

File Handling -- IM v6 Examples

(
    convert -size 100x30 xc:'#303030' -fill white -gravity Center -annotate +0+0 Hello miff:-;
    convert -size 100x30 xc:'#505050' -fill white -gravity Center -annotate +0+0 World miff:-;
    convert -size 100x30 xc:'#707070' -fill white -gravity Center -annotate +0+0 '!!!' miff:-;
) | convert - -append out.png

と、こういう形で f:id:sugyan:20190722225309p:plain のような画像を出力することが出来る。 最後のところを png:- とすればPNGのバイナリデータも受け取れるので一切中間ファイルに吐き出す必要がなくなる。知らなかった〜〜

結局サーバ側の実装ではpipeを使わず bufferに貯め込んで読み取る という方式にしたけど、ともかく convert コマンドだけで冒頭のような画像を生成することが出来た。

Frontend

Frontendは元々 React + ReactRouter でSPAにしていたものを昨年TypeScript化していて、ほぼ変える必要なかった。

memo.sugyan.com

Updateしたといえば tslint を使うのやめて @typescript-eslint に変えた、というのが大きいか。出来るだけ recommended な設定を使って 1件もwarning出ないよう書ける限り正確に型を書いて使うように心掛けて結局ほぼ全部イチから書き直した。

出演者名で絞り込みするフォームで 入力文字列を使って RegExp を組み立ててmatchさせてフィルタリングする、という処理をしていたのだけど ? や * を入れるとぶっ壊れるバグがあることに今年になって気付いた。ひどいバグをずっと埋めていたんだ。。。気付かせてくれた 「転校少女*」さんに感謝。 しかしJavaScriptでRegExpのescapeしてくれる関数みたいのって無いものなのか。

あとは時刻系ライブラリ。去年までは Moment.js を使っていたのだけど、そんなデカい処理は必要なくて Backendから取得できるJSONの時刻文字列をparseして 「8/2(金) 09:30」のようにformat出来れば良いだけ。なので とても軽いらしいという Day.js を最初つかってみたのだけど、任意のtimezoneに固定した出力が出来ない、ということに気付いた。

こんなの日本国内の人間しか使わんやろ、と油断していたら昨年 フィンランドのヲタクのヒトから「お前んとこでは動くかもしれんけど こっちのTZだと時刻ズレるんやで」とプルリクを貰ったのだった。

Set time zone for formatting times by hannesj · Pull Request #1 · sugyan/tif2018-mytt · GitHub

なので Asia/Tokyo で固定して出力できる必要はある。適当に調べていたら spacetime というライブラリがあったので 今回はこれを使うことにした。

昨年のJSは 545KB だったのに対し 今年は 230KB と半分以下のサイズになったので効果あったと言えそう

Others

その他にも今回は PWA化とかも入れようかな？ と思っていたけど、それほど享受できるメリットも無さそうだし微妙かな、と思って見送った。

生成した画像も CloudStorage に入れるように、とかすれば良いのかもしれないけど そこまで参照されるものでもなさそうだし別にいいかな、と。

要するに、自分が行くわけでもないフェスのためにそこまで頑張るモチベが湧かなかった、、、

Repository

AtCoder水色

今年の2月くらいから始めたAtCoderで、ようやく水色ランクに到達できた。

水色 (Bランク R1200~1599　上位15%)
水色はかなり優秀です。

AtCoder（競技プログラミング）の色・ランクと実力評価、問題例 - chokudaiのブログ

とのこと

なんとなくここを最初の一つの目標に定めていたので、どうにか辿り着けて嬉しい。まだ簡単に降級してしまうかもしれないのでせめて維持できるようには今後も頑張りたい、、

始めたきっかけ

あんまり覚えていないけど 今年に入ってから転職活動的なもので幾つか受けたときに そういうプログラミング問題が思ってた以上に出来ないことを痛感して やり始めようかな、と思って

ちょうど春くらいに「私はこうやってG社に〜」っていうブログを幾つか読むと結構AtCoderとかLeetCodeとか出てきたので よしやってみよう！と思い立って始めた

取り組み

とりあえずC++がニガテなのも克服したい、と思ったのですべてC++で挑戦した。 慣れてくると色んなcontainerが使いやすくて好きになってきたのでこれはこれで良い結果。

AtCoderはコンテスト直後に解説がアップロードされるけど 正直それ読んでも分からんもんは分からん…という感じなので 出来そうだったら解けなかったやつを再チャレンジしてみる、というくらい

過去問も少しずつやってみたいとは思いつつあんまり出来ていない…

どちらかというとLeetCodeを日々のトレーニングに使っている。まずは難易度低めのalgorithm問題を、とそのへんを優先的に毎日1〜3問くらい解いてみてる

Problems - LeetCode

何も見ずに解く → 解説読む → Discuss読む → 速度やメモリ消費を改善できる方法みつけたら試してみる

で地道に続けてだいたい200問くらいは解いた

今後

とりあえず次の目標は青色、か…

なんかDP使ってくような問題をマトモに解けたためしがないので、ちゃんと使いこなして解けるようになりたいな

Google Code Jam 2019: Qualification Round

C++ Python

Google Code Jamに今年もチャレンジ。

(昨年の: Google Code Jam 2018: Qualification Round - すぎゃーんメモ)

最近少しずつ AtCoder や LeetCode をC++で解く練習をしているので今回のQualification RoundもC++でチャレンジ

Foregone Solution

4 を無くせばいいだけなので 基本的に元の入力を残し 単純に 4 が出てきたときだけ 3 と 1 に分割すればいいかな、と。 0 が先頭に来るときだけ注意して後処理で消すなど

#include <bits/stdc++.h>

using namespace std;

pair<string, string> solve(string n) {
    pair<string, string> answer("", "");
    for (int i = n.length() - 1; i >= 0; --i) {
        if (n[i] != '4') {
            answer.first = n[i] + answer.first;
            answer.second = '0' + answer.second;
        } else {
            answer.first = '3' + answer.first;
            answer.second = '1' + answer.second;
        }
    }
    while (answer.second[0] == '0') {
        answer.second.erase(answer.second.begin());
    }
    return answer;
}

int main() {
    int t;
    string n;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n;
        auto answer = solve(n);
        cout << "Case #" << i + 1 << ": ";
        cout << answer.first << " " << answer.second << endl;
    }
}

You Can Go Your Own Way

問題読んでしばらく考えて、、これはスタートとゴールを結ぶ対角線で対称に動けばいいだけでは…ということに気付いた。 単純に S と E を入れ替えたものを作ればいいだけだった。

#include <bits/stdc++.h>

using namespace std;

string solve(int n, string p) {
    string answer;
    for (int i = 0, l = p.length(); i < l; ++i) {
        answer += p[i] == 'S' ? 'E' : 'S';
    }
    return answer;
}

int main() {
    int t, n;
    string p;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n >> p;
        cout << "Case #" << i + 1 << ": " << solve(n, p) << endl;
    }
}

ここまで解いて予選通過ラインは超えたので満足してしまった。

Cryptopangrams

時間あれば解こう、と思って結局間に合わなかった。

素因数分解を正直にやると非常に厄介そうだけど、必ずすべての文字に対応する素数を因数にもつものが存在しているわけだし 作り方から考えると隣接する数値どうしの最大公約数をとれば因数は取れる、ということに気付いた。ユークリッド互除法は知っているのでそれは書ける。

そうして取れる素数たちを並べて対応する文字に置き換えていけばいけそう。 しかし最初が ABABC みたいな感じで 同じ数字が並ぶパターンを考慮していなくてハマった。そこは注意しないといけない。

そして大きな値にも対応できるよう多倍長整数で、と思って以下のようなのを書いた

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
namespace np = boost::multiprecision;

np::cpp_int gcd(np::cpp_int x, np::cpp_int y) {
    return y == 0 ? x : gcd(y, x % y);
}

string solve(np::cpp_int a[], int l) {
    np::cpp_int d, d0;
    for (int i = 0; i < l - 1; ++i) {
        if (a[i] == a[i + 1]) {
            continue;
        }
        d0 = gcd(a[i], a[i + 1]);
        while (i > 0) {
            d0 = a[i--] / d0;
        }
        break;
    }
    d = d0 = a[0] / d0;
    set<np::cpp_int> s { d };
    for (int i = 0; i < l; ++i) {
        d = a[i] / d;
        s.insert(d);
    }
    vector<np::cpp_int> v(s.begin(), s.end());
    string answer = "";
    d = d0;
    for (int i = 0; i < l + 1; ++i) {
        for (int j = 0, ll = v.size(); j < ll; ++j) {
            if (v[j] == d) {
                answer += 'A' + j;
                if (i < l) {
                    d = a[i] / d;
                }
                break;
            }
        }
    }
    return answer;
}

int main() {
    int t, n, l;
    cin >> t;
    for (int i = 0; i < t; ++i) {
        cin >> n >> l;
        np::cpp_int a[l];
        for (int j = 0; j < l; ++j) {
            string s;
            cin >> s;
            a[j] = np::cpp_int(s);
        }
        cout << "Case #" << i + 1 << ": " << solve(a, l) << endl;
    }
}

が、

Solution.cpp:2:44: fatal error: boost/multiprecision/cpp_int.hpp: No such file or directory
 #include <boost/multiprecision/cpp_int.hpp>
                                            ^
compilation terminated.

がびーん。ダメなのか。

ということでそのまま Python3で書き直し。

def gcd(x, y):
    return x if y == 0 else gcd(y, x % y)


def solve(a):
    d0 = 0
    for i in range(len(a) - 1):
        if a[i] != a[i + 1]:
            d0 = gcd(a[i], a[i + 1])
            for j in range(i):
                d0 = a[i - j] // d0
            break
    d = d0 = a[0] // d0
    s = set([d])
    for e in a:
        d = e // d
        s.add(d)
    v = sorted(s)
    d = d0
    answer = ''
    for i in range(len(a) + 1):
        idx = v.index(d)
        answer += chr(idx + ord('A'))
        if i < len(a):
            d = a[i] // d
    return answer


t = int(input())
for i in range(t):
    _, l = [int(x) for x in input().strip().split(' ')]
    a = [int(x) for x in input().strip().split(' ', l)]
    print('Case #{}: {}'.format(i + 1, solve(a)))

以上

4問目はまだ開いてすらいない。余裕あったら挑戦してみよう。。。

Repository

github.com

GCPUG in Nara #3 で話をしました #gcpugnara

奈良で開催された「GCPUG in Nara #3 ～ GCPではじめる機械学習 ～」に、縁あってお声がけいただき 30分ほどお話をさせていただきました。

【奈良】GCPUG in Nara #3 ～ GCPではじめる機械学習 ～ - connpass

以前 Mix Leap Study #29 で話したときからあまりアップデートは無かったけど、GCPUGってことでGCPをこのように使っています、というのを含めてデモを多めに紹介させていただきました。

京都から意外に近いのに奈良での勉強会やコミュニティは全然参加できていなかったので、この機会で奈良の方々と交流できて良かったです。

ありがとうございました！

懇親会で食べた不思議なサラダが忘れられない