2024-03-20

2024.03.19 子供が産まれた

とてもうれしい～

2024-01-01

あけましておめでとうございます

あけましておめでとうございます。ご無沙汰しております。なんと4～5年ぶりの記事です。2019年にいなくなっていましたがそこからは自身にコロナ耐性なさすぎるせいかほぼ失われた期間という感じで、ハイライトとしては

2021年10月に結婚した
2022年2月にValorant始めた

くらいですね。

さて、以下に去年を振り返りつつ今年の抱負を述べます。

去年の振り返り

去年は自分的にはValorantの年でした。

iwiwi先生に2年前に誘われてドハマりして、実プレイ時間で合計1500時間超を費やしたであろうValorantのImmortalは達成したし、仲の良い人たちとプレミアに参加して優勝もできたので、FPSについてやり残したことはないです。2023年9月の分布によるとImmortalは大体上位0.7%らしいので、比較するのもあれですが多分AtCoderでいう黄色上位～橙くらいらしいです。俺Valorantのほうが得意らしい。

やばい、ソロイモータルやっといけた。マジでうれしい、マジ...うおお pic.twitter.com/TGrYrIdXKt
— きゅうり (@kyuridenamida) 2023年12月27日

プレミア優勝普通にうれしいな pic.twitter.com/Any9M4RBSc
— きゅうり (@kyuridenamida) 2023年12月17日

この事実と表裏一体な後悔を赤裸々に晒すと、労働中もValorantのことが頭の片隅にあるせいで、相対的にソフトウェア開発への熱意と感覚を失ってしまったことです。この道一本で食ってきた人間なのでこれはいけない。プレミアで一緒に遊んでいる人にもValorantハマりながらも博士号取ったり、労働で成功していたり、子育てやりつつ、それの全部を達成している人間がいるので、それを考えると俺には社不の血が流れていることを実感します。どれか一つでも達成できるのか?俺は。

年の瀬にXで見た"「なんの中毒になるか」がADHDの人生のすべてだと思う。"というツイートがぶっささり未だにそのことが頭の中で反芻しています。

「なんの中毒になるか」がADHDの人生のすべてだと思う。
— CB_1.29-2.11 (@CBydbbmpg) 2023年12月26日

(ところで今さらですが、恐らく競プロ界隈で知り合った皆さんは僕が突然FPSにハマったことに驚いているかもしれませんが、実は黒歴史ブログを参照すると中学生時代は狂ったようにFPSをやっていた形跡があり、自分的には驚きはないです。Valorantを通じて昔の友人と再び出会えたり、そもそも当時何かと接点があったYukishiroさんや岸さんを配信で毎回のようにお見掛けしてすごく嬉しかったです。多分あっちは覚えてないと思うんですけど、なんだか当時趣味としてFPSをやっていた人たちがそれを生業にしているという事実にかなり興奮していました。本当はオフライン大会の会場とかでファンボとしていつかご挨拶できたらいいなと思ってたんですけど、微妙に機会がなかったですね。)

今年の抱負

今年は、全部はまだ言えないですが今までとは全く新しい経験をする年になると思います。

Valorantは控え目というか恐らく近々(UPD 1/2)完全引退になると思います。ちょっと前まで3月限界ギリギリまでやろうとしてましたけど、30歳になる年であることを考えると良い引き際かなと思ってます。家庭もあるし、いろいろ衰えてくるし...てかまあ記憶とかに関しては既に衰えてて定点とかは全くだめです。手元にエージェント毎のマニュアルでも用意したら別かもしれない。競技シーンとかは追うかもしれない。

プレイヤーとして帰ってくることは...無いんじゃないかなと思いますが、あるとしても数年後ですね。ただFPSへの情熱自体はあるので、Valorantの便利ツール開発(チートではない, ビデオ解析とか)のほうをやっているかもしれない。

Valorantの代わりに、3月頃から家庭が忙しくなる予定なのでそちらに専念します。

家庭に専念しつつ、注力したい自己研鑽カテゴリとしては2点あって、ソフトウェア開発と英語です。まあ仕事にダイレクトに関連しています。ソフトウェア開発への意欲はValorantに完全に奪われた2年だったので、2年分キャッチアップしないといけないです。英語に関しては、デザインに関する議論の場で英語でのコミュニケーション能力が相変わらず労働の足枷になっている実感があるので改善していきたいです。テクニカルライティングや語彙も併せて強化していきます。

抱負に対する評価指標

ということで様々な目標に対する今年の自身の達成評価指標をまとめて書いておきます。年の瀬にまた見に来ます。

家庭をうまくやる (ここは諸事情でぼんやり)
TOEIC 950 以上取る
テクニカルライティングに関する本を1冊読む
AtCoderアルゴコンに月1回以上参加する (unratedでもよい)
AHCに3回以上参加する
個人開発したソフトウェアを他人に使ってもらう

2019-09-08

ISUCON 9 参加記

使用した言語
解析ツールの準備
本番前
- 一ヶ月前
- 一週間前
本番
余談: しょぼい暗号化（とかハッシュ化）を使うことの是非に対する本音

時間はすげえ適当、本当に適当

@akenshoさんと@li_sakuさんとチームluminousで出た。このメンバーで出るのは一昨年に続き二回目。

最終スコアは11.7kくらい通過できたらいいな〜。

使用した言語

解析ツールの準備

@akenshoさんが全てやった。

alp: 遅い/頻繁なhttpリクエストを把握するため
myprofiler: 頻繁なMySQLクエリを把握するため
pprof: GOアプリのボトルネックを把握するため
mysqlのslowquery報告機能: 遅いクエリを把握するため

本番前

一ヶ月前

そろそろ練習しないとな〜と思ってISUCONをやっては忘れるGoに触る

一週間前

isukariの練習しなきゃとかいうツイートをした(ニアピン賞) https://twitter.com/kyuridenamida/status/1168077007088803841

本当にisucariで笑ってしまったが、さすがにこれは容易に予想が出来たのでセーフ。

本番

開始前

09:30にAtCoder社に行って準備をする(早起き!) 10分遅延してくれてなんとか朝ごはん食べる暇ができた。ありがとう。

00:00 開始

とりあえずルールを把握したり、gitリポジトリを作ったり、色々。

isuconというローカルユーザーを作ってもらっていたのを無視してrootでgitを操作していたらチームメンバーがgitをisuconユーザーから操作できなくなっていたらしく、罵倒される。

01:00 - 様々なツールの整備が完了

何もしていないGOの参考実装に対するベンチを走らせる。2210点くらい。 pprofとかも走らせる。

pprofがpdfとかで表示されてCool! ありがとうsakuさん

01:30 最初の気づき bcryptは遅い

pprofの結果bcryptが遅すぎることに気づく。~~暗号化~~ハッシュ化-、やめるか!w(←この時点ではこれが違反になるというルールを把握していない)

「初期ユーザーの数は3!wハッシュ強度の変更は容易!w」みたいな議論をするが明らかにMySQLのテーブルを見ると嘘であることが分かる。4000コある。だめ。初期のデータベースにはハッシュしかないのでそれから平文を復元することは不可能だが、以下のようなマイグレーションプランを考える。

初期4000ユーザーに対するリクエストで来るパスワードを盗聴して、ログインに成功したらそれを別のテーブルpassword_listに保存する。
平文パスワードがpassword_listテーブルに存在したらそれを使って、そうでなかったらbcryptで今まで通り比較。
新しく追加されるユーザーについては無視する。
password_listは消さない

これでベンチを走らせるたびにbcryptの負荷が下がる最高の機構が完成。僕は高速化のためにこんなことしてるWebサービスが実在したら心底軽蔑するし絶対に使いたくないんだけど「これはISUCON、OK」という気持ちを強く持った。

とりあえず平文保存実装を僕がやって、akenshoさんがansibleによる様々なもの(Goコンパイラとか)の整備にとりかかる。

ところで作業中にinitial.sqlをpushしようとして無理やりgit addした結果、initial.sqlが神隠しにあい、また罵倒される。どうして...

03:00 平文保存のコードが一応完成

ベンチ走らせたらバグる。チームメイトに罵られる。Ω＼ζ°)ﾁｰﾝ sqlxわからん。データバインディングに失敗しているようにも見えるが、なぜ...?

03:30 バグが取れる

バグの原因わかんね〜って一生悩んでたら本当にあった怖い話としてGOは先頭が大文字か小文字でvisibilityが変わるという話をakenshoさんに教えてもらう。

type PasswordList struct {
    ID             int64     `db:"id"`
    userID         int64     `db:"user_id"`
    plainPassword  string    `db:"plain_password"`

↓

type PasswordListItem struct {
    ID            int64  `db:"id"`
    UserID        int64  `db:"user_id"`
    PlainPassword string `db:"plain_password"`
}

おわかりいただけただろうか。

この違いがsqlxのバインディングに影響していて、頭を捻っていた。僕はこれに関して「Go言語さんサイドの仕様決定プロセスに問題がある」という脳内で責任転嫁済みだったのだが、現実ではチームメイトに罵られれる。いやGoやってなくてすみません。多分一生自力では気づけなかった気がする。

03:30 ベンチ走らせまくり

平文パスワードを集めるためにひたすらベンチを走らせる。MySQLコネクションがさっきの変更によりリークしてたりして冷える。ごめん。直すから許して。

指定した負荷度が低かったため50コくらいずつしか増えない。先が遠いけど終了までには4000コ溜まってるだろうという気持ちになる。

途中で負荷を上げたらよいことにチームメイトが気づき負荷を0→2に上げる。一回にいっぱい集まって最高。

もっかいpprofを走らせる

04:00 第2の気づき: getNewCategoryListが遅い

bcryptくんの存在感が薄くなってるなあ。次は「getNewCategoryList、遅いぞ!w」とpprofに罵られる。

コードを読むと重そうなクエリ + N+1問題が起きている。明らかに怪しそうなN+1問題からやっつけようという気持ちになる。N+1問題は二つの関数によって引き起こされていた。

getCategoryByID
getSimpleUserByID

とりあえず完全にメモリにのっけてよさそうなcategory周りからキャッシュしていく。

04:00 第3の気づき: MySQLのチューニングが効きそう

コネクションリークの対処とか考えてるときにチームメイトが気づいた気がする。 akenshoさんが色々設定する。チームメンバーが何か良いことをする度にありがとうございますって連呼してたら「お前の目標は感謝なのか?」と罵られる。

04:20 大量に平文パスワードをかきあつめおわる + MySQLのチューニングをしたりする

チームメイトがめっちゃMySQLのメモリとかを弄っている。いい感じ。 7000点くらい、スコアがよくなる。やったぜ。3位。

04:30 getCategoryByIDをバグらせる

またバグらせてベンチ死んでチームメイトに罵られる。ごめん許して。

他にも、PRがあったほうがCR出来て便利だろ!って罵られる。許して。

とりあえずケツを叩かれながらさっさと直して動くようにした。

04:35 getCategoryByIDが直る

これだけだとN+1問題の完全解消にならないのでベンチにはさほど影響がなかったはず。

04:40 getSimpleUserByIDのオンメモリ化に取り組む

getSimpleUserは基本的にはオンメモリにできて、唯一出品数だけはリアルタイムに変わりそう。これも頑張ってオンメモリにする。 concurrent mapを使ったことがなかったがとりあえず https://github.com/orcaman/concurrent-map これを使わせてもらった。初めて使うのでドキドキした。よく考えるとincrementはアトミックにやらないということに実装してるときに気づき、地獄に落ちなかった自分に感動。 https://github.com/uber-go/atomic を導入する。どっちも使ったことがないライブラリでドキドキワクワク。例に漏れずGoわからなさすぎて苦労する。

05:00 第4の気づき: getNewCategoryList内のクエリは非効率的

僕がアプリを弄っている間にsakuさんとakenshoさんが発見してくれた。

saku「explainしたらサイアクな感じ。とりあえず思考停止でindex貼っていい?」

まあやってみて早くなればOKなのでとりあえず思考停止indexを貼って頂く。

05:00 第5の気づき: 平文保存はルール違反

_sakuが気づいた。マニュアルにも書いていたし、運営からも「平文保存はやめろ」とだけお達しが来る。わかるな〜〜〜〜そもそも~~暗号化~~ハッシュ化関数が満たすべき性質についての言及が一切無いので、困ってしまった。とりあえずこのままだと失格になってしまうし、暗号化しないといけないのだが、適当に性質を仮定して出戻りが起きたらサイアクなので、慎重にやることにした。

sakuにサポートチャットで「@運営『パスワードを平文で保存する』という意味は、ユーザが入力したパスワードをそっくりそのまま保存する、という意味と同値ですか？」と聞いてもらう。

しかし長らく返事がない、他の参加者の別の質問には反応している、困ったなあ...

06:00 インデックスを貼ったりしおわる

改善する。負荷も4にしてみる。たしかスコアが上がった?　9000点くらいになった?

06:00 再度平文保存に関する質問をする。

ここまで返事がないと見逃しているのかと思い、もう一度sakuさんに質問してもらう。

saku「@運営『パスワードを平文で保存する』という意味は、ユーザが入力したパスワードをそっくりそのまま保存する、という意味と同値ですか？」

再度返事がない。理由はわからないが返事の保留は意図的なものだと判断して諦めることに。

06:20 getSimpleUserByIDのオンメモリ化が完了

全員でデバッグしてちゃんと動いて、感動... 11500点くらいが出る。

06:30 独自暗号化関数の実装

質問の答えが相変わらず返ってこないので、そろそろ平文で保存しているものを暗号として保存することにする。（追記:本来やるべきはハッシュ化でしたが平文じゃなくなればいいので暗号化でも良いことにする） ISUCONに適した独自の暗号化関数を実装することにした。どういうものかというと

def create_encrypted_pasword(original_password string) string {
    return original_password + "#";
}

これを用いたログインは平文比較とほぼ同等の速度でありかつ強度も用途に適しているという判断になった。

func insertPlainPassword(userID int64, password string) error {
    _, err := dbx.Exec(
        "INSERT INTO `password_list` (`user_id`, `plain_password`) VALUES (?, ?)",
        userID,
        password + "#", //　暗号化
    )
    return err

plainPass, err := getPlainPassword(u.ID) //実ははプレインではありません。

if plainPass != password + "#" { // 復号化
    err = bcrypt.ErrMismatchedHashAndPassword
} else {
    err = nil
}

誤解を産む命名を含むロジックではあるが、コメントにもあるように、明らかにプレインではない。

このあと、平文は破棄して、新暗号でデータベースに保存することにする。DBのクエリを叩くのが怖かったので完全に収集し直す戦略。収集しはじめの頃点数が2000点台まで落ちてびっくりした。bcryptやっぱりボトルネックだったんだね。

07:00 凍結・再起動試験等に着手しはじめる

大体4000コの新暗号による暗号化済みパスワードの収集が終わる。点数が元に戻ってくる。 ISUCON最後のほうは色々試したりして事故ったら元も子もないので、危ない橋を渡らないようにしようという雰囲気が漂う。とりあえず再起動試験をやろうという話になる。個人的にオンメモリの出品数カウントとかめちゃくちゃこわいし大賛成だった。

再起動試験をするとmysqlが先に起動していないという理由でisucari.golang.serviceが死んでいることが分かる。これは出品カウント以前の問題だったし再起動試験して良かった〜。

07:30 再起動試験に成功

再起動試験に成功し、出品カウントもうまくいってる。やった〜

07:50 最後のベンチ走行

再起動した直後のフレッシュな状態でベンチマークを走らせる。最高得点11700くらいが出る。やった〜もうおしまいおしまい。放置。最終的にインスタンス数は1でした。

片付け。

08:00 終了

楽しかった〜!!スコアリング方式のおかげか超ベンチが安定していたし、快適だった。運営に感謝

終了。AtCoder社のホワイトボードにsnukeのイラストを描いて去る。あとは祈るだけ。これでパスワードの平文保存に関して質問はしたし(しかも二回も!)、厳密な定義が存在してそれによって失格になったら普通に悲しいけど運営のフェア精神を全面的に信頼しているため頼む頼む

結果発表通過してました!

ISUCON9 2日目結果と本選出場者決定のお知らせ : ISUCON公式Blog

通過してました!本戦がんばります!

余談: しょぼい暗号化（とかハッシュ化）を使うことの是非に対する本音

運営がbcryptに改善の余地を設けたのが意図的なのかについて考えていたんですが、この記事を読む限りISUCON8の本戦ではbcryptの使用を明記されていたように見えます。

http://isucon.net/archives/52598691.html

パスワードのbcrypt
パスワードをbcryptでハッシュ化していましたが、これがアプリケーションがCPUをつかうほぼ唯一の箇所でした。

また「パスワードはbcryptでハッシュ化しなければならない」と仕様に明記されていたため対策できないような錯覚をさせていましたが、コスト(ストレッチング回数)に関しては何も言及していないためコストを最小値にすると大幅にCPUが改善するものでした。

今回そのような指定はありませんでした。考えられる可能性は

単純に今回も同じことを仕様に書く予定だったが書き忘れた
意図的にbcryptを他の方法に置き換えることを想定した

どちらにしろ 1.に関しては早い段階で訂正のチャンスがあったのにしなかったということは2.の線が濃厚で、それを強く信じています。返事が無かったことに関する理由は謎です。

2018-12-27

問題文から入力コードを自動生成するツール(atcoder-tools)の紹介

この記事はAtCoder関連サービス Advent Calendar 2018 17日目の記事です． adventar.org

大変遅くなりました。@kyuridenamidaです。よろしくお願いします。

atcoder-toolsというものを開発しています。 atcoder-toolsの主要な機能を一言で言えば問題文に基づいた入力コードの自動生成機能です。

実際にはそれだけではなくサンプル入出力のダウンロード機能・サンプルテスト機能もあるのでAtCoderのコンテスト用ひな型作成ツールととらえてもらったほうが良いかもしれません。

github.com

歴史
使い方
現状の入力フォーマット解析の仕組み
今後やりたいこと
個人的にやってみたいこと
- 他のコンテストサイトにおける入力コードの自動生成

歴史

2年前

エイプリルフールに初期バージョンをリリースしました。しかし当時はソフトウェア開発初心者にもほどがあったのでコードはひどいしテストもないしカスタマイズも効かないし、なんなら簡単なインストール方法もありませんでした。それでも使ってくれていた人が少しいたのが嬉しかったですね。

去年

結局自分としては現状に満足していた＆書いたコードが読めずにメンテする気がなくなってたというのが理由で半ば放置気味になっていました。 @asi1024がCIツール(Travis CI)を導入してくれたりしたけど、僕がガバガバだったのであんまり機能してませんでした。

今年

10月くらいにそろそろメンテしないとやばいなと思い始めました。かなりだらだら型アノテーションを追加したり、コード構造を変えたりしていました。

そうこうしてるうちに同僚の@blue_jamさんとかがコントリビュートしてくれて、こんなひどいクオリティのコードを読んでPR出してもらうのかなり申し訳ないなと思ったのでリファクタを終わらせようと思いました。

結局自分に発破をかけるためにアドベントカレンダーに登録したはいいものの遅刻してしまい、12/25にようやくリファクタが終わって、12/26にPyPIデビューしpip install atcoder-toolsできるようになりました。そして今アドベントカレンダーを書いています。

使い方

インストール

pip intall atcoder-tools

サンプルダウンロード・入力部分つきコードを生成する

atcoder-tools gen [contest_id]でできます。例えばatcoder-tools gen arc001でARC 001のコンテストデータがダウンロードできます。

デフォルトの格納先ルートは{$HOME}/atcoder-workspace/になっています。そこの下に{コンテスト名}/{問題番号}/で保存します。これは--workspace引数で変更できます。

以下に実行時引数の詳細を書いておきます。

--without-login 練習時に自分のアカウントでログインする必要がない時に指定する。

--lang cpp or java。自動生成に使うコードの言語設定。

--template 入力フォーマットを推定できたときに使うテンプレートコードのパス。デフォルトは適当にリポジトリに存在する僕が書いたやつが使われます。

--replacement これは入力フォーマットを推定できなかったときに代用として生成されるコードのパス。

--parallel 問題ダウンロードの並列化。手元のmacでは動かなかった。

--save-no-session-cache クッキーをローカルに保存しないようにする

カスタムテンプレートを使う

--templateと--replacementにテンプレートを指定できます。

ジェネレータ部分のpythonコードをカスタムするとかは今のところできません。PR送ってほしいです。テンプレート内では以下のPlaceholderが使えます。コードの例 - ${input_part} e.g. 生成された入力コードを格納するところです。例↓

int N; 
cin >> N; 
vector<int> A(N-1+1);
for(int i = 0 ; i <= N-1 ; i++) cin >> A[i]; 
string B; cin >> B;

${actual_arguments} 型なし実引数列です。例↓

N, A, B

${formal_arguments} 型つきパラメータ列です。例↓

int N, vector<int> A, string B

サンプルの一括テスト

atcoder-tools testで今いるディレクトリ内の実行ファイルとサンプル入出力に対してのテスト結果を出力できます。引数はないです。実行ファイルが複数あった場合は警告しつつどれか一つを選んで実行します。

現状の入力フォーマット解析の仕組み

備忘録もかねて書いておきます。基本的な方針としては、頑張って入力フォーマットを型なしの中間形式に変換した上でサンプルを流し込んで型推論をします。

パターン

解析する入力形式は次に述べる三種類の入力パターンの連接(列)として表現可能だと仮定してパターン列を推論することを目論見ます。表現できない場合は残念ですが推論失敗です。今後のパターン追加に期待です。

単一パターン

一度しか現れないパターンです。NとかMとかです。

変数名を一つだけ持ちます。

タプル列パターン

タプル的な入力の繰り返しに対する入力パターンです。入力の順に並んだ変数名のリストと一つのインデックス(*)を持ちます。

(*) インデックス ここでのインデックスは添え字としてありうる最小の値と最大の値を持つデータです。

たとえば、

a_1 b_1
a_2 b_2
:
a_n b_n

を変数a,bに対しての入力がこの順に添え字が[1,n]の範囲で繰り返されていると表現するパターンです。

a_1 a_2 ... a_n

とか

a_1
a_2
:
a_n

とかはタプル列で変数の数が1である特殊ケースとして扱っています。

二次元パターン

二次元配列に対する入力パターンです。

変数名と行と列に対する二つのインデックスを持ちます。

c(1,1) c(1,2) ... c(1, W)
:
c(H,1) c(H, 2) ... c(H, W)

をcが [1,H]×[1,W]の範囲で繰り返されているふうに表現するパターンです。

パターン列の探索

全探索です。でもインデックス部分には必ずそれまでに入力した変数もしくは定数しか現れないという妥当な仮定をおくと早く終わります。とりあえず擬陽性を許す方針でありえそうなパターン列を列挙して、そのあとサンプルを流し込んで整合性を確かめる感じですね。それでほとんど一意に定まるか解なしで終わります。

精度

入力とサンプル入出力が取得できた問題かつABC, ARC, AGCの問題に絞ってプログラムが推論に成功したと主張した判断したケースは93.8%(976/1041)でした。一つ一つの推論結果が正しいかどうかについては手間を惜しんで精査していません。なので本当は正しくないけど正しいと判断されているケースもあって、実は93.8%は精度の上界であるという主張しかできません。とはいえ、定性的にはおおむね正しそうに見えます。

不正解なのに正解と判断されてしまう例は型に関するものが特に多くて、例えば整数っぽい見た目の文字列(ビット列とか)が与えられる問題でそれを単なる整数として解釈しているケースなどがありますが、それをなんとかするのは今後の課題です。

各問題に対するその推論結果のテスト結果が以下のURLから参照できます。

atcoder-tools/answer.txt at master · kyuridenamida/atcoder-tools · GitHub

今後やりたいこと

中間形式の仕様策定

現状コードを生成するに当たって

(入力フォーマット, サンプル群)→中間形式
中間形式→コード生成

というふうに処理を分離しています。この分離そのものはよいと思うんですが、肝心の中間形式の仕様をもう少しまともに策定しておくと他の人もそれに則ることができて便利なのかなって思ってます。区切り文字情報とか。

問題文から中間形式への変換を頑張る人は、何かしらの形で各コンテストサイトの問題からその中間形式に落とし込むロジックを作るのに集中すればよい。
コード生成をしたい人は中間形式からのコード変換だけに集中すればよい。

提出機能の復活

ペナルティがモリモリ増えるけどそれはそれとして自動提出は便利なので復活させたい。

online-judge-tools へのコード自動生成機能マージ

online-judge-toolsは@kimiyukiさんが作っている問題URLを指定するとよしなにサンプルとかが入ったディレクトリを作ってくれるツールです。

きちんとメンテされているしAtCoder以外のサービスにも対応しているので、データのダウンロード部分とか自動テスト部分は正直atcoder-tools側で独立に開発する必要はないのかなって思ったりしています。

ただ、submit機能とかは積極的に廃止予定らしいのでそのへんの思想の違いを理由に機能としてはatcoder-toolsにも残り続けるかもしれない。

リポジトリを英語にする

英語でREADME.md書くの意味ねーなって思って全消ししたけど、やっぱりAtCoderは海外ユーザー増えているし海外ユーザーにも使ってもらいたいから英語にしたい。

個人的にやってみたいこと

他のコンテストサイトにおける入力コードの自動生成

機械学習とかパターンマッチングを使ってCodeforcesの入力自動生成にチャレンジしてみたいというのが今の野望です。

2018-12-16

AGC 029

最近言語能力がかなり低下している自覚があるので、物を書いて感覚を取り戻そうと思います。

A, B, Cを解いて304位でした。Bでハマりまくった上にDを誤読してしまい、めちゃくちゃでした。レーティングは下がるし悲しい。二回連続でAGCひどい順位取ってる気がする。

A

問題白黒(B/W)のオセロが一直線にN(≦2*10⁵) コ並んでいる。B->Wの順で隣接するオセロの色を反転させることを繰り返すとき、最大で何回操作ができるか。

解法転倒数。

最大というのは実は無視できる。つまり、どんな順番で反転させても回数は変わらない。その回数はi < j かつ (Si, Sj) = ('B, 'W') であるような組の数に等しくて、これは転倒数そのもの。転倒数の数え上げは、一般のO(N log N)のものを使っても良いがそれは明らかに牛刀なので、値が2種類なことを利用してO(N)で解くと良い。具体的には、転倒数は普通に左から配列を舐めて、'W'が現れたときにそれまでに現れた'B'の数を足して上げる。

B

問題: N(≦2*10⁵)コの要素が与えられる。各要素は1以上10⁹以下の整数である。要素X,Yの和が2べきのときだけその要素同士のペアを作れる。同じ要素が複数のペアに使われないようにペアを作るとき、作れるペアの数はいくつか。

解法: 貪欲。

本番では重複する数を一つにまとめてから、ペアが作れるかどうかでグラフを作るとそれは森になることを利用して解いた。基本的には、葉の要素から貪欲に親とマッチさせていくことで最大のペア数が達成できる。しかし、2べき要素(1,2,4,8,...)については、同じ数同士でマッチさせるという追加の選択肢があるので困る。でも、2べき要素を根とした木を考えると、その選択肢について最後に考えても良いことが分かる。従って、この木で普通に葉から貪欲して、最後にその2べき要素が2つ以上余ったらそれらをペアにする。二つの異なる2べき要素は1つの木に含まれないことを確認したいが、これは2で割る回数が一致していないとペアに出来ないことから問題ない。

実際はグラフとかを意識しなくて良い方法があり、ソートして最大要素から貪欲にペアを作っていけば良かったらしい...

作れるペアを列挙するパートと、それを実際に使うか使わないか決めるパートを分けて考えることにする。 X≦Yとなるペア(X,Y)だけを考えても一般性を損なわないので、それを全て列挙することを考える。実は、各数に対してペアとして考える数は1つ(2べきを達成する最小の正整数)で、それで全てのペアを列挙できる。

なんで1つを考慮するだけでいいかを説明する。整数Yとそれとペアになるべき整数 X = 2^k - Y (Y < 2^k ≦ 2Y)を考えるとすると、選び方からX≦Yなので(X,Y)はペアになりうる。一方、2番目に小さいX' = 2^k+1 - Yもペア候補ではあるが、X' > Yとなってしまうため、考えなくて良い。

Yが大きい順にペア(X,Y)を使うか使わないか決定していくと最大数が求まる。このとき、ペア(X,Y) が使えるなら必ず使って損はない。というのは以下の理由に基づく。

使わなかったらそのYは未来永劫使われないので損をする可能性がある。
使うとして、Xを含む別のペア(X,Z)を作るのを妨げてしまう可能性はあるが、それによる損失は高々1つの別のペア(X,Z)が作れなくなるだけなので、少なくとも損はしない。

C

問題: 文字列{Si}がN(≦2*10⁵)コある。S1 < S2 < ... < Snという関係が成り立っている。i番目の文字列の長さAiのみを知っているとき、文字列に使われる文字の種類数として最小としてあり得るのは何か。

解法: 二分探索 + シミュレーション

文字の種類数の最小は、二分探索で見つけます。なので、二分探索の中では、種類数kで、S1, ..., Snが存在するかどうかを判定すれば良い。

存在するかどうかを判定するのはシミュレーションを用いれば良い。つまりできるだけ辞書順で小さい文字列を貪欲に割り当てて行けば良い。

これは以下のアルゴリズムで行える。n種類の文字からなるアルファベットを{0, 1, 2, ..., n-1}と表すことにする。明らかに、S_1は0をA_1コ繰り返したものを考えれば良い。 i ≧ 2 に対してどうするか考える。

A{i-1} < A_i のとき、S_iをS{i-1}の末尾に0を必要数足したものにすれば良い。
A_{i-1} ≧ A_i のとき、S_iから必要数末尾を削った後、末尾の文字を一つアルファベット順で大きいものにしてあげればよい。もしその文字がアルファベット順で最大なときは、繰り上がりが発生するのでそれをシミュレーションする。このシミュレーションは連長圧縮をしておくことで文字種類数が2以上のときは愚直にやっても高速に動作する。なぜならO(log N)桁くらいしか繰り上がりの影響を受けないため。

もし繰り上がりに失敗して長さA_iが達成できなくなったらシミュレーションは失敗、そうでなければ成功となる。

文字種類数が1のケースだが、これはA1 < A2 < ... < Anのときかつそのときに限り達成できる。

D

誤読

E

読んでない

F

読んでない

感想

書いて思ったんですけどやっぱり言語だめですね・・・

2017-10-24

ISUCON2017参加記

akenshoさんとli_sakuと参加、最終スコア20万3000点くらい。最高得点は21万5000点くらい。(よく覚えて)ないです。 1日目5位?で最終順位20位でした。2日目ありえん魔窟みが深い。18位まで通過なのでギリギリとはいえ予選落ちは予選落ちです。

1年前:

よすぽとぽてちと参加し、gitリポジトリを破壊して正の点数が取れず終了「なんやこのコンテストは...」

3ヶ月前:

けんしょーさん「GO言語勉強しといて」ぼく「この一年MySQLとかちょっと触ったしいけるやろw GO言語もアメリカ生活どうせ暇あるやろwやったろw」

3ヶ月間:

アメリカ観光サイコー

帰国後:

GO全然わからん(絶望)

1週間前:

みんなでPixiv ISUCONで初練習する。めたんさんのpixiv isucon攻略記を見ながらakenshoさんがちょっとずつ便利なもの準備してるのにli_sakuとだらだらする。結局GOがまともに書けず。最悪です。

数日前:

コドフェスと本戦日程被っていることが発覚。しゃあないけど予選は絶対楽しいし頑張りたいし、通ったら考えよ。

本番開始前:

GOの変数宣言の仕方さえ分からないけど読めるし雰囲気は分かる。大丈夫。

本番途中:

時系列は適当。実際チームでやったことたくさん他にあるけど僕が携わった部分ばっか頭に残ってるため許して。

ぼく&さく「けんしょーさんサーバー設定とチューニングよろです」　けんしょーさん「304とか返せる秘伝のたれ貼りました」
ぼく「なんか公開鍵周りがバグっててgitにpushできない(大騒ぎ)」さく「ちゃんとエラーメッセージを見て判断して」ぼく「すみません」
とりあえず静的配信のwebapp書き換えよろです←さくさんに書いてもらう
チーム「配信する画像のミラーリングとか辛いしまずはDB+(Webapp+nginx)の2台構成にしちゃいましょう」
暇やしindex貼ろう
は?なんだこのsleepは!?消そ!
既存のDBに入ってる静的ファイルデータを用意するコードがGOで書けない...せや! curl しちゃおw
やったー静的配信できたー。
チーム「nginx(主に画像配信),(nginx+webapp),DBの3台構成にしちゃいましょう」
ぼく「けんしょーさんpprofの使い方教えて(泣きつく)
けんしょーさん「なんかslowquery動かん」ぼく「コード読めば多分OK」
ちまちま/messageとか/fetchのN+1問題っぽいの破壊していく。13万点くらいになってきた〜
ん!?fetchは加点しないってなんや!sleep復活させるぞ!
スコア21万超えたワオ
なんか暫定3位やんけやったー
sleep2秒にしたろ!←7万点!?点数下がった!?なんで!?
sleep1秒に戻そ!←3万点!?ファーwww
チーム「これもうわかんねえな。どうせベンチマークが混雑してて仕方ないやつやろ。21万のときのwebappでガチャ引いていい点数出たらやめるか」
三人は幸せな20万点を取って終了(予選落ち)

反省点:

慢心と準備。
遅くなったのはベンチマークが原因ではなく恐らく僕たちのサーバーのリソースが何か悪いことになってたのが原因なので原因解析もきちんとせず諦めたのは本当に本当にダメダメだったと思います。
nginxに詳しくなりたいね。
GOでFizzBuzzはおろかHello Worldさえ書けないのがやばい。

良かった点:

基本的にほとんどバグらなかったのでベンチマークで胃が痛くなるとかがなかった。
Pixiv ISUCONで仕入れた知識が役に立った。
解析ツールは便利。

2017-07-23

The 2016 ACM-ICPC Asia Yangon Regional Programming Contest 参加記

はじめに
なぜヤンゴン
準備
旅程まとめ
登録
12/6 出発
12/7
12/9
12/10
感想

はじめに

今さらですが @a3636takoときひろちゃんと僕の3人チームDo Touch EverythingでMyanmarのリージョナルに参加していました．コーチは@threepipesさんです．今年もやるかもしれないし，何かの知見になると思って書いときます．質問があったらTwitterで@kyuridenamidaまでどうぞ

URL:

https://icpc.baylor.edu/regionals/finder/ar-yangon-2016

なぜヤンゴン

全員大学4年で研究やプライベートが忙しく、チーム練習時間が十分に取れていない状況でした。チームとしての動きが10月の筑波は間に合わないと思ったので12月に開催されるミャンマーの予選に参加することになりました。

理由はいくつかあって、以下の通りです。

治安がマニラよりは良さそうだったから(それでも心配してましたが，蓋開けてみればなかなか治安が良かった)
近年急成長が見込まれる国であり、そのような国のIT産業を支える若者たちと触れ合いたかったから
~~イカれたコンテストに参加できそうだったから~~

準備

結局研究が忙しくて練習時間が全然取れなかったのは痛いです。チームで5時間通して練習できたのが少なかったというのもある。
とはいえじわじわ各人の特性がわかってきて、チーム戦をすることで個人の最大値を超えることはできるようになった。
- takoは英語が苦手といいつつきちんと題意を把握して詰めて人に説明するのがうまい。読むのがはやい。
- きひろちゃんは実装は苦手だけど考察レベルでいえば僕よりはるかに多くの問題の解法を思いつける。
ライブラリを出発前日に整備したくらいです。
正直いうてリージョナル3位くらい取れるやろとか本気で思ってた。

旅程まとめ

移動は全てチャイナエアラインを使った。

12/6 に関西国際空港から台湾桃園空港(3時間)
12/6-12/7 台湾桃園空港で空港泊 (乗り換えまで約14時間で日を跨ぐタイプだったので)　←　過酷だったからおすすめしません
12/7 ヤンゴン移動(台湾から4時間くらい?)
12/7 ICPC側が用意したバスでホテルへ、あとセルフ観光
12/8 プラクティス
12/9 本番
12/10 朝11時発の飛行機で帰国(今度は乗り換えがいい感じ)

登録

普通にAcceptされた。
しばらく経ってから宿泊先とか飛行機の到着時刻をメールで聞かれたりしたので答える．これは空港からの案内をしてくれるためっぽい．

12/6 出発

袋タイプのたけのこの里をおみやげに買った。
台湾コーチにパイナップルケーキを日本アジア地区で貰ったので、お礼にどら焼きを買っていった。
台湾までの飛行機では寝たり、きひろちゃんが紹介してくれた問題を解いたり、シンゴジラを見るコーチを見てたりした。
台湾に到着してからは、一度入国審査を受けた。天候も悪く少し遅かったので、市内観光することは諦め、電源席で3時間-4時間くらい練習した。これは微妙だった。
桃園空港の第2ターミナルだったのだが、下のフードコートのソファー席が24時間いちおう解放されているので、そこで仮眠を取っていた。
あんまし寝れなかった

12/7

朝5時、ヤンゴンに行くための飛行機に乗るために起床。
偶然同じ便だったようで、いつものNCTUのコーチに会う(何回目だろうw)
NCTUは3チーム+1コーチという計13人の大軍だった。
飛行機乗る。CAさんがきさくで、おすすめ情報とかを雑談で手に入れる。オイリーだけど数日だから大丈夫っしょwとか、朝飯はミルクティーとパンがいいよみたいな話をされる。ふむ?
ミャンマー到着。ビルマ語を見て感動する。
実は知らなかったのだれど、ICPCの人たちが丁寧にお出迎えしてくれる。人々の伝統衣装が綺麗。
換金場所とかも案内してくれて、しばらくして全員が揃ってからホテルにバスで移動。
今日は暇なので、観光しようと思い、最も有名らしいシュエダゴン・パコダに行く計画を立てる。ホテルからタクシー。ホテルのフロントの人がホテルの地図を描いたカードをくれた。戻るときはこれを見せろって。
ホテルからヤンゴン中心部は結構距離があり、相場は 7000キャット (700円) くらいって言われたけど、5000キャットで乗せてくれた。ミャンマーはタクシーにメーターがなく基本事前交渉です。
タクシーで1時間?くらいかけてシュエダゴン・パコダに到着
確かに綺麗。金ピカである。
とりあえず散策できるところをぶらぶら歩く。仏様みたいなのがたくさん設置されている。
写真撮って欲しかったので「写真撮ってくれますか?」って近くにいた女性2人組に言ったら撮ってくれて、2人の写真も撮りましょうか?って言ったら、together という単語が悪かったのか(たぶん)ナンパだと思われたらしく「友達待たせてるんで!」って去られた。なんとも言えない気持ちになった。
正直バックグラウンドがわからなくて、ガイドいります?って入口で言われたのを、とりあえず断ったのを若干後悔した。景色として美しいという感想を抱いていた。
お寺から出ると、ヤンゴン市街地に行くためにタクシーを捕まえる。4000 キャットでいいよって言われた。安い。
市街地に行くと、露店とお店と路駐と渋滞と人混みですごいことになっていた。
治安は良いと聞いていたがやはりこわく、かばんを前に担いで慎重に移動する。
さっそく物乞いらしき子どもに服をやさしく引っ張られてちょっと焦った。
歩行者信号が存在せず、車が通らない隙を狙ってみんな道路を渡ろうとするので正直混沌としていた。交通インフラが整備されてない印象を受けた。どうやら車は人を引かない程度に歩行者がいても遠慮せず進んでくるので、強気でうまく渡ることが重要らしい。
露店はフルーツとかなんかいろいろ売ってたけど、おなかを壊す危険性があると聞いていたので食べなかった。
ヤンゴン市内、いくつか通りがあって、ちょっと生活感のあるところに迷い込んでしまい、少し不安になりながらウロウロする。ビンロウ(タバコみたいな扱いの存在)の吐き痕が結構いたるところにあった。
そんな感じで通りを間違えまくっていたが、事前にtakoが購入した地球の歩き方に書いてるお店をようやく発見。お昼ご飯を食べる。
日本でいうビルマカレーのお店に行く。カレー感はないし、カレー粉使ってるならカレーでしょという日本人の命名なだけで現地の人はそう思ってなさそう。ただ、美味しい。油だらけを覚悟していたが、案の定油だらけだった。変な野菜とかがつきだし?で出される。
その後は露店とか、ヤンゴン市内のローカルマーケットを散策する。
露店は日本のワゴンセール的な財布が2500キャットとかで売っていたり、ジーパンが同様に5000キャットいかで普通に売られてたり、すごく安い。持ってきた長財布持ち歩くの嫌だったので2500キャットで財布購入(使わなかったけどw)。
最終的に、おみやげ屋さんを探して辿り着いた。
- タナカの石鹸とか化粧品とかをお土産に買う。だいたい 1000キャット。
- ミルクティーと味見して美味しかったピーナッツ菓子も買う。30パック入りで100円、ピーナッツ菓子のほうは30ピースで1000キャット。安すぎる。大量に買ったが1000円も使えなかった。
めっちゃフレンドリーだし海外の人だからといって高めにふんだくってくることもないし、治安のよさに感動する。
その後は帰るためタクシーを探しはじめる。
なんかタクシー斡旋みたいなおじさんに声かけられて、タクシー?って聞かれる。目的地見せていくらですかというと、10000キャットと言われる。「高すぎィ!7000 キャットにして」って言ったら「無理無理無理」みたいなこと言われたのでじゃあいいですって言ったら9000キャットと言われ、「うーん8000!」と言ったらまた「いやいやいや」と言われて、いいです他探しますって言ったら8500になり、やっぱ他探しますって言ったら、「しょうがねえなあ8000ならいいよ!」って言われるみたいなやりとりをした。~~正直安いからいくらでも良かった~~んだけど面白かったのでついつい交渉をしてしまった。ただ、相場より正直少し高いんやろなぁという気持ちになったため、もっと交渉上手にならないといけないと思った。多分，7000を死守しないとだめですね。そのために初手5000とか法外な金額ふっかけたほうが良かったんだろうか。
でもなんか日本語で様々な挨拶をしてくるおっちゃんとかもいて、まあ斡旋だし市内から郊外のホテルに行くの、客が捕まる率が低いよなあとかいろいろ考えると、別に損した気分にはならなかった。
帰ったあとはホテルの近くにあったスーパーマーケットに行く。なんかセキュリティが厳重で、入り口に警備員がいて身体検査されて驚く。スーパーではあらゆるものが安く、酒税がほとんど存在しないのか酒とかはとても安く、現地フード的なのはε価格で購入できそうだった。
My Little Ponyの絵柄のノートがあったのでついつい買ってしまった。12個入りで250円、安いが開いてみると時間割とか書いてあって完全に女児向けだった。それはそう。
帰ったあとは練習しようと思ってたけど，みんな疲れてしまっていたので寝る．

12/8 (ここから3ヶ月後に書いてるため忘却しまくってる)

今日はプラクティス
ホテルまでICPCの人が手配したバスがきて，UCSYまで送ってくれる．
バスが韓国から輸入されたであろう中古車だった(どうでもいい)
大学に着く．記念撮影して，現金で参加費払って，その後朝食をもらう．
開会式まで暇があったので学生をめぐる．一番驚いたのはUCSY，コンピューター専門大学なのにほとんど女子学生ばかりで，男女比が日本と全く異なっていた．制服が伝統的な衣装っぽくて男女ともにキレイ．
開会式が始まる．初コンテストデスみたいな話を聞く．あとは伝統芸っぽい踊りを見る．日本のアジア地区同様，各学校の学生の自己紹介フェーズみたいなのが行われる．
開会式が終わればプラクティス．普通にパソコンルームみたいなところでコンテストをするらしい．ちゃんと風船はある．
プラクティスがスッと始まる．
- 最適化オプション無いらしい．-Oくらいつけてくれや．
- でも自分で #pragma GCC optimize (“-O2”) するのはいいらしい．公平性とは…
- A:難しそうな問題 + B:嘘貪欲誘発系自明問題 + C:場合分け問題が出題される．
- おっミャンマー，日本よりはるかに骨のあるプラクティス出してくるやん．期待が持てる．
- Bの問題概要は，いくつか文字列が与えられるので辞書順で最も大きいものを求めなさい．有名問題ですね．
- a + b > b + aでソートして出力するとWAする．草．
- 嫌な予感がしたのでa > bでソートしたらAC．大草原．これはやばい．
- C，曖昧な部分があり(入力制約がきちんと書かれているのに入力制約に違反したものが与えられるからそのときの対処をしろみたいなの)，WAを量産しまくる．これは単に我々がダメだった．
- Aは概要覚えてないけど昔のヨーロッパ地区の難しい問題の再出題らしく，解法に悩みまくった．
- A通してるチームがいる．すごい．
- 1完で終わる．冷える．まあいいやってなる．
終わった後，噂によるとAはnがめっちゃ大きいけど実際にはnが70なのに5未満とかのケースしか含まれてなかったらしい．おいおい．
ホテルに帰ってチーム練習．このときはめちゃくちゃ練習うまくいった．
ホテルではルームサービスでハンバーガー食った．高い(現地価格じゃない)だけあって美味しい．
朝早いので寝る．

12/9

今日は本番．
6時45分バス出発は健康的すぎて辛いからやめろ．
8時半からコンテストが始まる．
あまりにも辛かったのでこの部分を書いたのが7ヶ月後で，全てを忘却しているため書けない．
唯一覚えているのは以下の事柄
- ジャッジがバグっていた + 一位のチームはジャッジと同じ間違いを器用に踏んでACしていた(すげえ)．
- とても数分では普通解けない構文解析を開幕数分で解いていた謎の現地チームがいた．
- doubleの仕様で理論上取れうる範囲が書かれた問題文はじめて見たわ．
- 何回もクラー飛ばしてたら偉い人が現れて非公開情報をくれた(これええのか!?)
- 海外のチームはジャッジがバグっていたり制約が曖昧だったり，どう考えても普通ならTLEしそうな解法が通る問題，謎の枝刈り・謎の工夫を編み出すのが本当に早く，雑草のような(本当に他に表現が思いつかない)タフさがあった．壁を感じたし見習いてえ．
- 現地チームの最上位より海外チームの最下位の順位の方が上だった．一年目だし仕方ないかなと思ったと同時に，ICPCに大学関係者一同とても力を入れているようなので今後が楽しみ，東南アジアはベトナムとかタイも含めて急激にICPC力が伸びてきている印象．
- 最後のほうは解ける問題で慌ててしまいクソハマりまくってかなりひどい順位に(18位とかそんなんだった)．
- こういうハチャメチャわくわくコンテストで大敗したの悲しいわ．
ホテルでパーティー
みんなフレンドリー，開催側も含めてみんなフレンドリー，なかなか楽しい．

12/10

ふー終わった終わった．
ホテルまでICPCのスタッフがきてくれて，お見送りしてくれる&タクシー取ってくれる．優しい．
空港，出国ゲート通るまでキャット→ドルの変換してくれる外貨両替所が無くて苦労した．
さあ帰国!Myanmar→台湾→日本だ．フライトが少し遅れているらしい．乗り継ぎやべえな．
乗り継ぎ急げ〜〜って全力疾走して，ようやく搭乗口にたどり着いたんだけど，おかしいな…パスポートがパスポートケースに無い．
どうやら乗り継ぎ時(つまり出国検査後)，パスポートを紛失するというレアケースをやらかしてしまったらしい．
日本帰国できない機運が高まる．最初は搭乗は難しいから，空港で過ごしてもらうことになるかもと言われていた．
乗り継ぎに使う航空会社が同一の会社だったことで本人確認が出来ているということ，日本へのフライトであることなどから，特別に搭乗を許可された．まあ日本の入国管理局に任せることになるんだろうし，この判断は助かった．
日本に帰国して特別な部屋で入国のための書類を書かされる．帰宅後，速やかに戸籍謄本とか送る必要があるらしい．
なんとか帰宅できた．最後の最後でやらかしてしまった．パスポートはパスポートセンターで失効してもらった．大変だった．

感想

ミャンマーはコンテスト以外はめっちゃおすすめです．みんな親切です．少なくともICPC関係者は親切でした．
コンテストは，日本の無菌室で育てられたみたいな良質コンテストに慣れてると辛いかもしれないけど，めちゃくちゃな問題をラッキーで通してワンチャンWF狙いにいきたい人にはおすすめです．