2019-07-30

約2ヶ月半のグループ開発をして学んだこと

雑記

はじめに

　この記事は, 講義として約2ヶ月半のグループ開発を経て, その過程で学んだことを記録する目的で書きました。グループ開発の内容よりも良かった部分および悪かった部分とその改善策を書いた方が自分のためにも見る方のためにもなると考え, 開発の中身はあまり深く書きませんでした*1。ご承知おきください。

はじめに
もくじ
開発していた環境
開発したもの
開発に伴い作成した書類
良かった部分
悪かった部分とその改善策
今回の開発で学んだこと
- 技術的な話
- 非技術的な話
  - 時間は有限
  - 「グループワークに不満があるなら全部お前がやればいい」は大嘘
おわりに

開発していた環境

　開発日数は全体で2ヶ月半で, 環境構築に2週間ほど, 残りの1ヶ月程度でコーディング及びテストを行いました。メンバーは6人で以下の通りでした。

人	立ち位置	補足
もっちー	リーダー兼デザイナー	事務作業およびデザイン系のプロ。「コードが書けないので」と言いつつ実績コード数はある。
松君	フロント側の開発リーダー	休息を犠牲にして指数関数的に強くなったプロ。彼のおかげでVueXを導入できた。
K君	フロントエンドエンジニア	初心者なりにも理解しようと努力していたひと。分からない部分はしっかり質問してた。
O君	バック側の開発リーダー	インフラ面やコードレビューの絶対的プロ。何故かアイコンがいちごオレ。
鴨君	バックエンドエンジニア	Javaのプロ(らしい)。Golang初めてとか言いつつしっかり実装してた。
私	バックエンドエンジニア	Vue.jsとGolangを少し書ける。最終的にフルスタックになってた気がする。

開発したもの

概要

　開発したアプリケーションは, モノを管理するアプリケーションで「mono-management」と言います。提供する機能は, モノの登録と編集, 親子関係を持つタグによるモノのカテゴリ分けなどです。

　アプリケーションの構成は以下の通りで, フロントエンドをVue.js, バックエンドをGolangおよびMySQLサーバで実装しており, アクセスはNginxを介して行う設計としました。なお, これらのサーバは全てDockerコンテナ上で動作させました。

f:id:task4233:20190728203931p:plain — アプリケーション構成

サーバの環境構築

　サーバの環境構築には, docker-composeを選定しました。選定した理由は, 複数のサーバを立てて相互で通信するため, 1発でまとめて環境構築できるのが魅力的だったためです。とはいえ, バックエンドで使用したDockerのMySQL8.0公式スクリプトにバグが潜んでいたため, それの特定と対応に時間がかかりました*2。これにより, 環境構築のためのdocker-compose.ymlやsqlfiles, nginx.conf等の作成が約2週間程かかってしまいました。しかし, ここでしっかりと環境構築したおかげで, 開発時の結合テストが本当に楽になったので悪くなかったと考えています。

フロントエンド

　フロントエンドのページ作成には, JavaScriptのVue.jsフレームワークを選定しました。選定理由は2つありました。1つ目の理由は, 納期があるため学習コストの低いフレームワークを選定する必要があったためです。フロントエンドのフレームワークを触れたことがないメンバーが複数いる状態だったため, 私たちに選択の余地は無かったように思います。2つ目の理由は, サーバとの通信を最低限にするSPAを導入したかったためです。今回開発したWebアプリケーションはモノの登録や編集などでページ遷移をすることが多くなることが想定されました。そのため, 必要な部分のみをバックエンドのAPIサーバとやりとりすることで通信時間の短縮が期待できました。結果として, Vue.jsを利用したことで開発初期はあまり進んでいませんでしたが, 途中からコンポーネントの再利用やVueXの導入によって開発が加速し, 結果として何とか納品することができたので正しい選択だったと考えています。

バックエンド

DBサーバ

　バックエンドのDBサーバには, MySQLを選定しました。選定理由は, フリーで使用できるDBの中で最もポピュラーなDBだったためです。今回はdocker-composeでサーバを管理していたため, 初期起動時にテーブルを自動生成するためのsqlファイルを書きました。sqlfilesを置いておくだけで, コンテナ内にテーブルを生成してくれるのでかなり楽でした。

JSON APIサーバ

　バックエンドのJSON APIサーバには, Golangのginフレームワークを選定しました。選定理由は, Golangのフレームワークの中で最もGitHubのドキュメント等がしっかりしていると感じたためです。以前の記事であるmixiさんのGit Challengeでしゅもんさんという方に相談した際には「APIサーバ程度なら軽量でswaggerでAPIが吐くJSONも簡単に確認できる出来るgoaがオススメ」と言われました。しかし, メンバーのO君と話し合った結果, swaggerを利用した開発は魅力的ですが, 今回の開発規模なら手書きで対応できるため学習コストを低くするという意味でもginの方が良いという結論に至りました。結果として, ドキュメントを見るかググることで対応できたので, ginで問題ありませんでした。しかし, 他の言語・フレームワークと比較した時にGolangのginフレームワークである必要があったかと聞かれると, はっきりと答えることができません。強いて言えば, 「私がGolangの言語仕様が好きなので」ということくらいでしょうか？

　また, Golang以外の言語でもあるとは思いますが, documentを自動生成してくれる機能も魅力的でした。実際にGitHub Pagesで公開しているので, もし良ければ参照してみてください。

ORMライブラリ

　APIサーバがDBサーバとやりとりするために, GolangのORMライブラリとしてgormを選定しました。このライブラリの選定理由は, 使用するginフレームワークとの相性が良さそうで, 何よりGolangのORMライブラリの中で最も多機能だったためです。基本的な文法に加え, トランザクション管理などもしっかりと対応していたため, 開発時に欲しい機能は大抵あり非常に助かりました*3。

開発に伴い作成した書類

　開発を始める前に, 要求仕様書・外部設計書・内部設計書・総合テスト仕様書という書類を作成しました。各仕様書の内容については, ググれば幾らでも出てくるので割愛します。

良かった部分

設計書を書いてからコーディングを始めたこと

　(講義の構成上ですが)設計書を作成してからコーディングを行なったため, 全体像を見据えながら次に何を書くべきなのかを明確にしてコーディングを行うことができました。更に, フロントとバックを結合する際に想定されるリクエストとレスポンスが定義されていたので, 割と問題なく結合できたのも良かったです。*4

Pull Requestに対するレビューの義務化

　私たちはGithub-Flowに沿った開発を行っていました。そこで, developが汚染されるようなコードをマージされるのを危惧して, developへのマージに関して1人以上のレビュアーによるApproveを義務化しました。*5これにより, 他人に読まれることを意識して, 関係ない差分を入れないようになりました。また, 私だけかもしれませんが, 自分のコードを読んでもらえると嬉しいので, モチベにつながったという副作用もありました。

docker-composeによる一括管理

　これはサーバの環境構築でも書きましたが, フロントエンドとバックエンドの結合テストが, $ docker-compose up と1度叩くだけでできてしまうので非常に楽でした。そして, コンテナはVMと比較して軽いので複数コンテナを立ててもメモリが圧迫されなかったのもポイントです。また, Dockerは環境依存しないので, 本番環境のUbuntuでもO君のArchLinuxでも私や鴨君のMacOSXでもテストをすることができ, Pull Requestに対するレビューに対応できたのも良かった点です*6。

slackによる情報共有

　現在はslackを使用している人が多いと思うので主要機能は割愛します。私たちのslackで特徴的だったのは, #懺悔室チャンネルの存在です。#懺悔室チャンネルはミスした時に懺悔(報告)をするチャンネルです。ここに吐き出すことで, ミスをしても後腐れなく開発ができたので良かったと考えています。*7

f:id:task4233:20190730012845p:plain — #懺悔室の様子

悪かった部分とその改善策

関係ない差分を含んだPull Requestを飛ばしてしまったこと

悪かった点

　例えば, 以下のようなPull Requestが挙げられます。

f:id:task4233:20190730015659p:plain

　色々とツッコミどころがあると思いますが, 何より「Fix get tag list」というPull Requestにも関わらず, modifiedに関係ないファイルが多すぎることが一番の問題だと思います*8。実はこのPull Requestでは関係ない差分で必要な行を削除してしまっていたのです。この時はレビュアーがミスに気づき指摘してくれたので助かりましたが, このように関係ない差分を含んだPull Requestを飛ばしてしまったのは悪かった点だと考えています。

改善策

　シンプルで効果的な改善策は, Pull Request名を厳格に書くということです。厳格に書くことで, 関係ない差分を含んでいる場合は気づけますし, Pull Request名に「&」が入る場合はPull Requestを分割して行えば良いので, 差分の簡略化かつ明確化に繋がると考えています。しかし, 今回の開発でもそうでしたが, 厳格な命名をつけるのは面倒なものです。そのため, 普段から厳格な命名をつける心がけをして, 厳格な命名を習慣化することが重要だと考えます。

環境構築が遅かったこと

悪かった点

　サーバの環境構築でも書きましたが, docker-compose関連の環境構築で約2週間を費やしてしまいました。先日以下のようなツイートを見かけて, 　他講義により開発時間を確保できなかったり公式MySQL スクリプトの不備などの問題があったりしたものの, やはり2週間は長すぎたなと思いました。

えっ！？
開発環境の構築に二日以上かかるエンジニアがいるんですか！？
— と (@t0riumi) 2019年7月29日

　しっかりとした環境構築のおかげで, 後々の開発が加速したのでその点は良かったのかもしれませんが, この期間が短ければ開発日数を増やせたのかなとも思います。

改善策

　これに対する改善策をずっと考えていたのですが, 思いつきませんでした。強いていうなら経験を積んで, 起きそうな問題を把握しておくことくらいでしょうか？環境構築が大変なことはよく理解しているつもりなので, これに対して効果的な改善策はないと考えています(あれば教えて欲しいです)。

レビューの仕方が曖昧だったこと

悪かった点

　先述した通り, 今回はPull Requestをマージする際にレビューを義務化しました。しかし, レビューをする機会がほとんど無かったため, レビューの仕方が人によって異なっていたのも問題だった気がします。私は, コードの変更差分の確認と, 動かした際にPull Requestの内容で正しく修正されていることが確認できたらApproveしていましたが, このレビュー方法も正しかったのかどうかわかりません......

改善策

　レビューに関して詳しいことはわからないので, 本なり記事なりを見て学ぶのが一番だと思います。ただし, Pull Requestする側は, レビュアーがレビューしやすいように変更差分を簡潔にしたり, commitを多く挟んだり, Pull Requestの目的などを明確にしておくべきだと感じました。結局のところ, Pull Requestが曖昧だとレビュアーも困りますしね。

今回の開発で学んだこと

　今回の開発で学んだことを技術面/非技術面に分けて要点のみを絞って書いておきます。

技術的な話

docker-composeによる環境構築は時間をかけてもやっておくべき

　今まで散々書いてきましたが, 結合テストが楽というメリットが最も強いです。今回のようにフロントエンドとバックエンドが異なる場合は, 結合テストを行う際にそれぞれのサーバの環境を合わせて別々に立てるのは大変です。また, 仮に立ててもCORS関連で通信ができないトラブルが起きようものなら辛い気持ちになることでしょう。そのため, $ docker-compose up で本番環境が立つdocker-composeは有用でした。

公式のスクリプトにも誤りはあるのでコードを読んでみるのもアリ

　今回悩まされた公式MySQL8.0のスクリプトの件です。今までは, 5,6時間バグと格闘して対処法が見つからない場合, 時間がかかりそうなので別の手法に変えるようにしていました。しかし, 今回のようにGitHubでコードが見れる場合は実際のコードを確認して「なぜそのエラーが出ているのか」を確認することで, 自らパッチスクリプトを書いて対処可能なことを学びました。時間はかかるかもしれませんが, どうしてもその技術を使用する必要のある時に有用なので, 頭に留めておくつもりです。

不明瞭で必要のない差分を含むPull Requestは悲劇を生むことがある

　今回の記事では触れませんでしたが, 実は問題のあるPull Requestがマージされてdevelopブランチが汚染されたことがありました。$ docker-compose upが正しく動作しなかったので気づけましたが, これが気づきにくい部分だったらと思うと恐ろしいです。この件に関しては, レビューの時点で気づけなかったのも問題ですが, 何よりそのようなPull Requestを飛ばさないのが一番だと思います。

非技術的な話

時間は有限

　今回開発を行った際に強く感じたのは, 時間が足りないということでした。コーディングを始めてから締め切りまでは1ヶ月強ほどあったはずですが, 他講義との兼ね合いで実際にコーディングできたのは50時間も無かったように思います。これは開発以外にも言えることかもしれませんが, 締め切りが先でも使える時間は有限なので, 必要最低限のコードを実装できるような規模にすることが重要だと感じました。

「グループワークに不満があるなら全部お前がやればいい」は大嘘

　これはとある講義のグループワークをしていた時に, とある教師から言われたのですが, 長期間の作業に関してこの考えは通用しないなと感じました。結局, ひと1人ができることなど高が知れていますし, 何よりこのやり方は自分の首を締めるだけでなくメンバからの不信感を増大させるので, 長期間の作業には向いていないと感じました。大抵の場合, 「これやって」とお願いすれば何らかの反応があるので, まずそれをするのが良いと思います。

おわりに

　ここまでお読みいただきありがとうございました。読み返してみて「まぁそれはそうだよな」と思えるレベルのことが多い気がしましたが, 少しでも参考になれば幸いです。良かった部分は「当然だろ？」と思えるように, 悪かった部分は繰り返さないようにしようと思います。

　また, 今回の開発は長かったようで短く, 前期日程の空き時間をほとんど全て注ぎ, 他のことが出来ないほどでした*9。正直こんな厳しい開発はしたくないなと思うので, 次に開発をするときはマトモなボリュームの設計にして開発しようと思います。

*1:現時点でその部分を知って得する人が思いあたらないので書くつもりはないです

*2:既にIssueが立っていました。O君がこのバグに対応するパッチスクリプトを書いてくれました。

*3:開発時に「有能じゃん」と頻繁に言っていたのをよく覚えています。

*4:一応JSONの変数で大文字小文字関係のトラブルはあったものの, それ以外に大きな問題は起きませんでした。

*5:企業でのグループ開発をしたことがないのでわかりませんが, やはりこれが一般的なのでしょうか？

*6:Windows10 Home EditionだとHyper-Vが使用できなかったので, フロントの2人は使えませんでした。早くWSL2出てくれ......

*7:これは余談ですが懺悔したメンバーがすぐに退出するので, 常駐していた1人のメンバーがシスターと呼ばれるようになっていました。

*8:「CreateMonoとEditMonoは副作用なのであまり見なくておkです。」も問題ですが。

*9:7月に入ってからコンテストにも出られていませんし, Twitterで呟くこともありませんでした......

2019-05-19

Git Challenge #11 参加記

参加記録

f:id:task4233:20190519105753p:plain

はじめに

この記事は, 2019年5月18日に開催された株式会社mixi主催のGit Challenge#11の参加記になります。

ブログを書くまでがGit Challengeらしいです。

はじめに
Git Challengeとは
きっかけ
イベント当日までに行ったこと
イベント当日に行ったこと
感想
- 競技に関して
- 懇談会に関して
展望
スタッフの皆さんへ
おわりに

Git Challengeとは

2人1組となってGitリポジトリに設けられた難題を解決していく競技型技術イベントです。このイベントは今回が第11回目で, ジャッジシステムの構成を一新したそうです。

詳しくは, 次のリンクを参照してください。

きっかけ

mixiさんのツイートでした。実は直前までデータベーススペシャリスト試験の対策等で忙しかったので, 締め切り30分前にオタクのような文を2000字程度書いてmixiさんにお祈りをしながら提出しました。その結果, 締め切り直前の提出にも関わらず当選しました。*1

ですから, 締め切りのギリギリでも諦めずに提出していきましょう！

イベント当日までに行ったこと

まず, Slackで要求されたPerl5系のアップデートを行いました。そして, Perlはコードゴルフで使われている印象が強かったので, AtCoderでコードゴルフをしているこたつがめさんの記事に目を通していました。結果的にほとんど理解できなかったので意味があったかは分かりかねますが......*2

次に, 基本的なGitのコマンドをローカル環境で動かしてみて確認しました。参考にしたサイトをぶら下げておくので, もし良ければ確認してみてください。

イベント当日に行ったこと

会場に到着するまで

起床Challegeは当然成功しました。*3

渋谷駅に到着したのが10時ごろと早すぎたため, 近くのドトールで過去の参加記を確認しながら時間を潰していました。

会場に到着してから

f:id:task4233:20190519110757j:plain

会場には, AlphaからLimeまでの12グループがありました。その中で, 私はCharlieグループに分類されました。

イベントは次の流れで行われるようでした。

スタッフによる技術解説 part1
チュートリアル
昼食
競技本番
解説
スタッフによる技術解説 part2
夕食と懇談会

スタッフによる技術解説 part1

Git Challengeにおける新システム構成

今回の11回目で新システムを導入したそうです。詳しくは, ジャッジシステムのリポジトリを参照すると良いと思います。

Gitでドメイン管理

Gitでドメイン管理をする話についてご説明いただきました。

ドメイン管理をする際に, 手動でやろうとするとミスが出たり, ログが残らなかったりします。そこで, Gitでドメイン管理をすることでこれらの問題を解決しようという試みだそうです。技術仕様としては, DNSであるAWSのRoute53にDrone CIを噛ませ, GitHubでドメイン管理するというものでした。

私は自分用のドメインを持っていないので欲しいなと思うなどしました。*4

チュートリアル

問題に関する情報は非公開とのことなので割愛します。

昼食

f:id:task4233:20190519111457j:plain

チキンカレーをいただきました。昼食はチームDeltaの方々とスタッフのお2方とご一緒しました。

競技本番&解説

問題に関する情報は非公開とのことなので割愛します。

f:id:task4233:20190519112629p:plain

結果は, 17スターで同率5位でした。

問題とは関係ないのですが, 解説前に乾杯をしました。スタッフさん含めほとんどの方がアルコールを摂取していたので, 自由だなという印象を受けました。

スタッフによる技術解説 part2

コミットログで機械学習

Git本体のGitリポジトリに溜まっている約55000件のコミットログを使って, コミットメッセージから特徴を抽出して変更対象の機能を予測しよう と考えたそうです。

pygit2で集めたデータをよしなにPandasに投げて分析を行い, 結果として正解しているケースが現れたそうです。しかし, 精度で見ると0.26...と低い値であり, 偶然の産物とも考えられる結果になったそうです。

結果に対する考察として, コミットメッセージとして署名を含んでし待ったことが精度が下がってしまった原因ではないかと考えたそうです。また, 今回はコミットメッセージに含まれるタグを教師データとして用いていましたが, 変更されたファイル名を教師データとして用いても良いのではないかという話もしていました。

懇談会

f:id:task4233:20190519111922j:plain f:id:task4233:20190519112211j:plain

軽食と共に他の参加者やスタッフの方々とお話をする時間でした。

そのはずでしたが, 最後の問題を通しておきたかったので解説を改めて拝聴してACしました。

f:id:task4233:20190519112948p:plain

その後は, ほとんどの時間をスタッフの方々との話に費やしていた気がします。話していた内容としては, 私事のプロジェクトや実際の業務, それに自作キーボードの話などでした。

詳しい話を書くと更に長くなりそうなのでやめておきます。

感想

競技に関して

2人で1組なので, もし自分が解けなくとも相方が解ける問題があったり, またその逆もあったりしました。そのため, 私はチーム内でしっかりとコミュニケーションを取ることが重要だと感じました。

幸いにして, 私の相方は気さくな方だったので, 問題が解けた時にお互いで進捗を確かめあったり褒めあったりしていました。結果的に優勝は逃したものの, よく健闘していた方だと思いますし, 良い意味でチーム戦をできていたと考えています。

また, 競技で優勝した方によると, 普段からGitのリポジトリを破壊して修復することが多いのでその経験が大いに役立ったとのことでした。やはり経験が重要なのかなとも思いました。

懇談会に関して

以前参加したBSC*5では他の参加者との話で時間を使ってしまったため, 今回はスタッフの方々とお話しようと決めていました。その結果, 私が個人的に進めているプロジェクトに関する技術的な話や, mixiさんの業務に関する話など多くの話をすることができました。

結果的に, 以前のBSCと比べて, 交流関係の拡大が乏しかったものの多くの情報量を得ることができたChallengeとなりました。

展望

おそらく, 今回のGit Challengeほど多く$ git *というコマンドを叩いたのは初めてでした。更に, 普段のGit使用で見ることのなかったコマンドやフォルダ構成などについて知ることができました。これは素晴らしい知見であり, 今後は積極的にGitリポジトリを壊して$ git fsckを叩いていく人生を送っていきたいと思います。*6

スタッフの皆さんへ

Git Challengeというイベントを開催していただき, 本当にありがとうございました! イベント中になんどもリセットをお願いしたり, 遅くまでお話していただいたりと色々とご迷惑をおかけしましたが, 全てしっかりと対応していただき本当に感謝しています。

ありがとうございました！お疲れ様でした！

おわりに

毎回言っている気がしますが, こういったイベントはやはり良いです。私が趣味で競技プログラミングやCTFをやっているというのもあるかもしれませんが, 問題を解決することで他人と競えるイベントというのは本当に楽しかったです。

また, BSC, Git Challengeに参加してきたので, 残りのTDDC*7にも参加してみたいと考えています。そのために, 更に研鑽を積んで積極的に新しいことに挑戦していく姿勢を保ち続けていこうと考えています。

以上がGit Challengeの参加記となります。 Gitの使い方について深く知れるだけでなく, スタッフや他の参加者と話して知識を広げるチャンスなので, ぜひ次回のGit Challengeに参加してみてはいかがでしょうか?

*1:長文を確認してくださった人事の方, お疲れ様です。

*2:print+(<>+<>)*<>/2程度のコードならば理解できました。

*3:情報技術者試験0次試験に落ちたことがないので余裕でした。

*4:お金がかかると思うとつい手が出せないんですよね......

*5:Bug Shooting Challenge

*6:積極的に壊しはしないが。

*7:Test-Driven Development Challenge

2019-05-13

春のプランクトンサミット in 関東参加記

参加記録

TL;DR

外部設計書のデータ設計とデータ構造設計終了
AtCoder200/300/400/500点問題AC!
プラサミは様々なジャンルを持つ ~~オタク~~ プランクトンが集う場所
精進する人もいれば話をする人もいる
全体的にモチベが高い
都合が合えば必ず行くべき

はじめに

この記事は春のプランクトンサミット in 関東の参加記になります。

この記事の目的は，時系列に沿ってプラサミを振り返り充実していた一日を懐古することです。 f:id:task4233:20190512234134p:plain

プラサミとは？

プランクトンサミット（以下プラサミと略します）とは，主催者のヴァネロピさんによると次のように書かれています。

プランクトンサミットを簡単に説明すると、「取り組んでいる少し周りとは違ったこと」や「取り組みに対する異常なまでの執着心や集中力」によりあまり普段「普通の人たち」と溶け込めないオタクみんなで集まって、「精進とか大変だよねー」「一人でやってると寂しいよねー」「自分のやってること、誰かに知ってもらいたいな…」みたいなのを共有する場です♪(๑ᴖ◡ᴖ๑)♪ﾌﾟﾗｯ

実際にプラサミに参加してみると，受験勢・数学勢・低レイヤ勢・競プロ勢などなど複数のジャンルの人間が参加していました。そして，各自が思い思いの作業をしていました。

詳しくはconnpassのイベントページを参照してください。

connpass.com

きっかけ

きっかけはTwitterで流れてきた次の2連ツイートでした。

僕が「何がプラサミか」と聞かれ、絶対に失いたくない雰囲気があるとしたらそれです。「取り組みの度合いが極めておかしいオタクたちの本気」をシェアしたい会です。「分野がなんでもいい」というのは「あなたがその分野に本気で取り組んでいるならなんでもいいからその熱量を見せつけてみろ」です。
— 夜の帝王ヴァネロピ (@Vane11ope) March 19, 2019

このツイートを見るまでヴァネロピさんをよく分からない方だと認識していたのですが，このような発言を見てこの人は面白そうだなと思い申し込みました。

当日のムーブ

会場入りまでの時間

がっちょさん・kodaiさん・3⁵さん・すとまとさんと同じ店で，イベント前にラーメンを食べました（写真は撮り忘れました）。

その後，会場に向かうまでにkodaiさんからForthという言語についてお聞きしました。この言語はスタック指向というパラダイムの言語で，C言語等でも使用されるスタックに関数アドレスや変数情報等を積むような操作を明示的に書く言語だそうです。言語の構成は，要素をスペースで分割しif-else文に関してはアセンブリをメタプラグラミングチックで書くそうです。そして，非常に速い実行速度を誇る言語だそうです。また，kodaiさんは現在FORTH言語の入門書を作成しているそうです。

github.com

会場に着くと赤い服を着たヴァネロピさんを発見し「この人がヴァネロピさんか！」と思うなどしました。

Cybozuさんの会場に入るために入館証を発行しました。

f:id:task4233:20190512233836j:plain

会場入りの時間

Cybozuさんの会場に入ると，複数のブースや机椅子がありハンモックやバーなどもありました。

f:id:task4233:20190512234234j:plain

私は会場で誰もいなかった部屋「TANEGESHIMA」で作業をすることにしました（画像を撮り忘れました）。壁がガラス張りで綺麗な景色が見える開放感ある部屋でした。

#プラサミ
 Cybozuさんの部屋, 景色が良い。 pic.twitter.com/eRIsKegRwm
— Tasker (@task4233) May 12, 2019

作業をしている内に競プロ勢が来て，まさに競プロ部屋のようになりました。

競プロの時間

各自作業をしていました。そんな中，16:20~17:20の1時間でVirtual Contestが開催され，多くの方が参加していました。

私にとっては初のオンサイト（？）だったので，他のContestantと同じ環境で競プロが出来て楽しかったです。

Plankton Summit 3 Tanegashima Contest

その後，いらしていたChokudaiさんとお会いし，サイン入りのステッカーをいただきました。ずっとAtCoderのステッカーを欲しいと思っていたので，非常に嬉しかったです！早速Macに貼りました。

f:id:task4233:20190513000345j:plain

また，作業をしていたTANEGASHIMAにChokudaiさんがいらっしゃり，dpについての考え方をお聞きしました。リアル解説放送のようで少し興奮しました。

数学の時間

どういう流れかリーマン積分とルベーグ積分の話になりました。するとboscoさんとkakiraさんによる数学の講義が始まりました。勉強会という感じが色濃く出ており，ついつい聴き入ってしまいました。

リーマン積分をざっくり言うと，求めたいx座標の区間を縦で短冊状に区切り，極小領域で捉えると長方形のように考えることが出来るため，それの総和を計算する事で求めたい区間を積分で求められると言うものでした。要するに，求めたい積分の値を縦に区切ってたくさんの縦長短冊を作り，総和を求めるということです。

それに対して，ルベーグ積分は求めたい区間に対して横長短冊を作り，総和を求めるという積分を行います。そのため， $y$ 座標の区間を与えるとそれに対応するx座標の区間を返す逆関数 $f^-1(y)$ ，区間を与えると区間の大きさを返してくれる $μ$ という関数のようなものを定義します。そうする事で，求めたい $y$ を逆関数 $μ(f^-1(y))$ に与える事で対応するxの区間の大きさが求められ，それに $y$ の値を乗じる事でリーマン積分と同様に極小区間で考えると長方形のように考える事ができるため，それの総和を計算する事で求めたい区間を積分で求められるというものらしいです。

お二方ともわかりやすく説明してくださったので，話された範囲に関しては理解できました。

撤収の時間

お片づけをしながら，競プロの話をするなどしました。気がつくと時間は20時を回っており，Cybozuからの夜景が綺麗でした。

f:id:task4233:20190513003131j:plain

感想と反省

プランクトンが集うという謎のイベントでしたが，想像以上に良いイベントでした。

その理由としては，全ての参加者が武器となるスキルを保持していたのが大きかったです。どの方と話をしても，全ての方が必ず何かのことに熱中している（or いた）んですよね。私は努力をしている人間が大好きなので，何かに熱中できる人間が沢山いる環境は素晴らしいと考えていて，個人的に今まで参加してきたイベントの中で最もレベルの高い参加者だったのではないかなと考えています。

また，今回のサミットでは話している人が精進している人の邪魔になっているのではないか？と思われることが何度かありました。私も話しているうちに誰かにご迷惑をかけていたかもしれないです（申し訳ない）。そのため，精進に集中したい人用に完全消音部屋を用意しても良いのではないかなと感じました。

まとめ

今回のサミットでは，数学と競プロをメインに話せた印象でした。今までに参加したことのあるイベントだと交流会の時に口で会話する程度でしたが，今回はホワイトボードがあったため話している内容が具現化されてお互いの意思疎通がうまくいったという印象が強かったです。

次に参加する際はCTFについてもお話したいなと考えています。

最後になりますが，本日のイベントをセッティングしてくださったヴァネロピさん，会場設営等に携わった関係者の方々，イベントに参加したプランクトン各位，本当にお疲れ様でした。ありがとうございました！

2019-03-02

Bug Shooting Challenge #2 参加記

参加記録

f:id:task4233:20190303001351j:plain

はじめに

タイトルにもありますが, この記事はBug Shooting Challenge#2の参加記になります。

この記事の目的は, 時系列に沿ってざっくりとBug Shooting Challenge#2を振り返ることです。

この記事の概要は次のとおりです。

Bug Shooting Challengeとは

Bug Shooting Challenge（以下BSCとします）とは, 2人1組となって、ゲームサーバのログから不具合の原因を特定し、ソースコードの修正までを行なうChallengeのことです。

詳しくは, 次のリンクをご参照ください。

きっかけ

きっかけは, mixiさんからのメールでした。mixiさんの+Challenge系は面白いという噂を耳にしていたため, 申し込みました。

申し込んだ後に事前課題が与えられたので, 事前課題を解いて提出し, とおりますようにとお祈りをしていました。

結果は当選だったので, 喜んだのをよく覚えています。

イベント前日までにしたこと

Slackで要求された, DockerおよびDocker Composeのインストールを行いました。

Dockerは使用したことがあったのですが, Docker Composeはあまり使用したことがなかったので, 次の記事を読んでおきました。

Docker compose ことはじめハンズオン - Qiita

当日したこと

会場に到着するまで

起床Challengeに成功して家を出ました。

渋谷駅に到着したものの, 渋谷駅付近で迷いました。高低差が多く, 道も多いため方向音痴の私としては大変でした。

会場に到着してから

会場には, AからJまでのグループがあったと思います。その中で, 私はHグループに分類されました。

イベントは, 次の流れで行われるようでした。

スタッフの方々による技術解説
昼食
本番前のチュートリアル
本番
夕食と交流会

スタッフの方々による技術解説

田村さん

CREについてご説明いただきました。

CREとは, Customer Reliability Engineeringの略で, CS（Customer）とエンジニアを繋ぐ架け橋になる存在とのこと。

さらに, 本イベント中は私たち参加者がCREとなり, 不具合調査および問題解決に当たって欲しいとのことでした。

佐藤さん

次の技術についてご説明いただきました。

Ruby/Rails
Git/GitHub
Docker/Docker Compose

Ruby/Rails

Rubyに関しては, 20分ではじめるRubyや公式リファレンスを見てほしいとのことでした。

ちょっとした動作を確認するためにRubyを使いたい場合は, インタラクティブシェルを使うと便利らしいです。

$ docker run -it -rm ruby:2.5 irb
pryもオススメ

Git/GitHub

Gitとは, 分散型バージョン管理システムのこと。 GitHubとは, Git向けのリポジトリホスティングサービスのこと。

Git-Challengeもやっているので, 参加してほしいとのことでした。

Docker/Docker Compose

Dockerコンテナを活用することで, 環境を容易に用意できます。最近は, 異なるアーキテクチャのコンテナも起動できるとのこと。

佐野さん

SQL

はい。

Hadoop（Apache Hive）

オープンソースの分散ファイルシステムおよび分散処理基盤で, SQL Likeのクエリを投げられるとのこと（HiveQL）。

AWS EMR（Elastic MapReduce）でS3上のデータに対して, EC2インスタンスのクラスタで分散処理を実行できるとのこと。

メリットは, 膨れ上がったデータを高速に処理できたり, 低コストでスケールアウトできたりするとのこと。

昼食

f:id:task4233:20190303001038j:plain

釜飯をいただきました。昼食は, スタッフの佐藤さんと大谷さん, 隣のGグループの方々とご一緒しました。

本番前のチュートリアル & 本番

問題は非公開とのことなので, 割愛します。

スタッフの方々からの講評

バグレポートには実際のログを載せよう

色々なバグレポートがありましたが, 大抵が要点は抑えられていたとのことでした。しかし, バグレポートにバグの根拠となるログ自体を載せているグループは少なかったようでした。

バグレポートは書いた人のためにあるのではなく, 読む人のためにあるものです。読む人がログを見ることができるとは限らないので,実際のログも載せるとよいとのことでした。

チートは許さないという確固たる意志を持とう

CREである以上, チートは絶対に許さないという強い意思をもつべきとのことでした。

夕食 & 交流会

f:id:task4233:20190303001133j:plain

f:id:task4233:20190303001218j:plain

食事が豪華でした。数人とお話しましたが, やはり知らない分野の話を聞くのは面白かったです。まだ知らない世界があると思うとわくわくしてきますね。

また, 競プロ・CTF勢の多さが印象的でした。普段はこれらの分野の話ができないので, かなり楽しめました。

まとめ

今回のBSCを通して得られた知見を5つまとめてみました。

キャッシュとは程々の付き合いをしよう

キャッシュは, 使わなくて済む場合は使わない方がよい。しかし, 使うと便利なことも事実です。そのため, 使えるときは整合性に気をつけながら, 程よく使うとよいとのことでした。

リクエストを信用してはならない

HTTPリクエストには, 不正なものが含まれることもあります。そのため, リクエストログは客観的に見るべきだそうです。それに加えて, 不正なリクエストが来ることを考慮してコードを書く癖をつけるとよいとのことです。

意味的にひとかたまりの処理を意識したコーディングをしよう

コーディングをする際に, 処理をグルーピングするとよいとのことです。たとえば, データベースとのやりとりをするときはトランザクションをひとかたまりの処理として意識できます。そうすることで, 一貫したコードを書くことが可能になるそうです。

また, エラーが出た時の挙動を理解しておくとよいとのことです。

その場しのぎの対応策は良くない

バグを発見したとしても, 対策方法は複数あることも珍しくないです。そこで, その場しのぎの対応策を選ぶのではなく, ユーザのためのアプリケーションであることを第一に考えた対応策を選定するべきだそうです。

また, 単に簡単な対応策のみをとると他のバグを誘発する恐れもあるため, 根本的な問題を解決するような対応策をとるべきであるとのことでした。

バグレポートのフォーマット

以下のように, What, Why, Howを具体的に書くと良いそうです。

What（バグの説明）
Why（原因/根拠）
- ここには実際のログを入れるとよい
How（対応）

展望

BSCでのバグ対応は, 実際のアプリケーション開発においても意識面での実践ができそうです。

また, バグレポートの書き方はテストや仕様書, コメントを書く時にも転用できると考えます。基本的に他人が見る前提で, そのように書いた理由があれば具体的に書くとよいかもしれません。

スタッフの皆さんへ

BSCという機会を設けていただき, 本当にありがとうございました。イベント中は, 質問・要望に対して1つ1つ真摯に対応していただいたので, 本当に感謝しています。

ありがとうございました。お疲れ様でした。

おわりに

こういったイベントは, やはりよいですね。何より,自分の知らない知識や経験を得る機会になりますし, 参加者の研究内容や興味のある分野を聞く機会にもなります。こういった機会は日常生活ではあまり無いので貴重な時間でした。

また, 他の+Challengeも参加したいですね。そのためには, さらに知識と経験を積まねばならないな, という気持ちです。

ここまでが, BSCの参加記でした。興味のある方は, 次回のBSCに参加してみては如何でしょうか(開催するのかは分かりかねますが)？

2019-02-06

ABC117-D XXOR

AtCoder 競プロ

D - XXOR

概要

N個の非負整数A_1, A_2, ..., A_nおよびKが与えられる.
0以上K以下の整数Xに対して, f(X) = (X xor A_1) + ... + (X xor A_n)としたとき, fの最大値を求めよ.

解法

桁DPで解く.

dp[i][j] := 上位iビットまで見た時に, k以下であることが(j?確定:未確定)であるときの最大値

その上で, 上位(i+1)ビット目から上位(i)ビット目の遷移を考える.

1. 確定状態から確定状態

この遷移は, 遷移元が既に確定状態に入っているため, Xのiビット目として0と1のどちらが来ても必ず確定状態のままである.
したがって, 0と1の両方を比較して値が大きくなる方を選択して遷移すれば良い.

dp[i][1] = max(dp[i][1], dp[i+1][1] + (1<<i)*max(num, n-num));

2. 未確定状態から確定状態

この遷移は, 遷移元が未確定状態に入っているため, kのiビット目が1の時にXのiビット目として0が来なければならない.
したがって, Xのiビット目が0となる⇔Aのiビット目で1が立っている方に遷移させれば良い.

if (k & (1<<i)) {
  dp[i][1] = max(dp[i][1], dp[i+1][0] + (1<<i)*num;
}

3. 未確定状態から未確定状態

この遷移になるものは2種類ある.
1種類目は, kのiビット目が0かつXのiビット目が0のとき.
2種類目は, kのiビット目が1かつXのiビット目が1のとき.

1) `kのiビット目が0`かつ`Xのiビット目が0`のとき

Xのiビット目が0となる⇔Aのiビット目で1が立っている

if (!(k & (1<<i))) {
  dp[i][0] = max(dp[i][0], dp[i+1][0] + (1<<i)*num;
}

2) `kのiビット目が1`かつ`Xのiビット目が1`のとき

Xのiビット目が1となる⇔Aのiビット目で0が立っている

if (k & (1<<i)) {
  dp[i][0] = max(dp[i][0], dp[i+1][0] + (1<<i)*(n-num);
}

以上より, 遷移をまとめると以下のようになる.

dp[i][1] = max(dp[i][1], dp[i+1][1] + (1<<i)*max(num, n-num));
if (k & (1<<i)){
  dp[i][1] = max(dp[i][1], dp[i+1][0] + (1<<i)*num);
  dp[i][0] = max(dp[i][0], dp[i+1][0] + (1<<i)*(n-num));
} else {
  dp[i][0] = max(dp[i][0], dp[i+1][0] + (1<<i)*num);
}

桁DPの遷移は実装できたので, あとは残りの部分を実装するだけ.

#include <bits/stdc++.h>
using namespace std;
using int64 = int64_t;
#define int int64

// dp[i][j] := ibit目まで見てそこまでの値がk未満で(0:ない, 1:ある)時の最大値
int dp[60][2];

signed main(){
  int n,k;
  cin >> n >> k;
  vector< int > a(n);
  for(int i=0; i<n; ++i) cin >> a[i];
  memset(dp, -1, sizeof(dp));

  dp[45][0] = 0;
  for(int bi=44; bi>=0; --bi){
    int on_bit_num = 0;
    for(int ai=0; ai<n; ++ai){
      if((a[ai] >> bi) & 1) ++on_bit_num;
    }

    int digit = (1LL << bi);
    if(dp[bi+1][1] >= 0){
      dp[bi][1] = max(dp[bi][1], dp[bi+1][1] + digit * max(on_bit_num, n-on_bit_num));
    }     
    if(dp[bi+1][0] >= 0){
      if ((k >> bi) & 1){
        dp[bi][1] = max(dp[bi][1], dp[bi+1][0] + digit * on_bit_num);
        dp[bi][0] = max(dp[bi][0], dp[bi+1][0] + digit * (n-on_bit_num));
      } else {
        dp[bi][0] = max(dp[bi][0], dp[bi+1][0] + digit * on_bit_num);
      }     
    }
  }

  int ans = max(dp[0][0], dp[0][1]);
  cout << ans << endl;
  return 0;
}

以上.
ほとんどけんちょんさんの記事を参考にしました.
お疲れ様でした.

参考資料

2019-01-23

CombMofに聴き手として参加してきた

参加記録

CombMofの備忘録

下書きはできていたのですが, 公開するのを忘れていたので今更ながら投稿します。

はじめに

先日(2018/12/23)に催されたCombMofでのLTの概要と私個人の感想です。

CombMofの詳細は主催者のもふたろうさんの記事をご参照ください。

CombMof告知: nizi26i26.hatenablog.com

当日の流れ

会場にうまく着けず, ギリギリの到着になってしまいました。
Google mapsを見ながら歩いていたはずなのに迷いました。
不思議ですね。

LT

1. 文化祭のWebアプリを作ってみた話 by shuhannn

LT資料:

niconare.nicovideo.jp

2年連続で文化祭の物販システムに関するWebアプリを製作したお話。製作時の試行錯誤と成長した点について触れ, 最後には所属しているN-PointでLT支援イベントを始めた話をしていました。

感想

1年目の製作の問題点を踏まえて, 2年目の製作に反映させている部分が非常に良い部分だなと感じました(素人並みの感想)。

2. エンジニアのためのUI/UX入門 by tinykitten8

LT資料:

エンジニアのための UI/UX入門 from Tsubasa Sekiguchi

www.slideshare.net

優れたUX(User Experience)を作るにはどうすれば良いのか？という発問に関するお話。
その答えは「ユーザの立場に立って考える」ということ。
具体的には以下の通り。

近接(似ている要素は近づけて, 似ていない要素は離そうね)
整列(要素はグルーピングして整列しましょうね)
コントラスト(異なる要素の差異を強めて注意をひきましょうね)
反復(ページ内で一貫性を持たせませしょうね)

また, ユーザの立場に立つ具体例として「ABテスト」というものがあるようです。

www.assion.co.jp

感想

以上の4点程度ならば意識するのは容易なので, 今後意識します。

3. C#8.0という未来を垣間見る話 by 4_mio_11

LT資料:

speakerdeck.com

C#8.0(未リリース)の新機能のうち, null許容参照型およびSwith式に着目。詳しくは, LT資料もしくは以下のQiitaの記事を参照してください。 qiita.com

感想

C#はJavaに似ていると聞きましたが, 使ったことがないのでイマイチ嬉しさが響いてきませんでした。知識不足ですね。

4. プログラミングに触れよう by Akkyun919

LT資料:

docs.google.com

初心者向けのプログラミング入門用LT。プログラムとは何か？という基本から始め, 競プロ, ゲーム開発, Webプログラミング等を紹介していました。

プログラミングは「とりあえず,やれ」。

感想

初心者向けと言いつつ, Brainf*ckを出すのはどうなんでしょうね?(私はそういうの好きですが)。懇談会で, 「あの後にWhiteSpace入ってたら面白かったのに」という話をしていました。

5. モザイクアートをつくろう by shibh308

内容については, 塚本さんが記事を執筆していたのでそちらをご参照ください。

shibh308.hatenablog.com

感想

処理の端々にオーダに関する話が出ていたので, やはり競プロerだなと思いました。競プロは役に立つんですね(本当か?)。

6. プログラミング言語実装の話 by stmtk_01

LT資料:

docs.google.com

チューリング完全なプログラミング言語を実装してみようとしたお話。ループ処理を実装するのに飽きてチューリング完全ではないそうですが, 四則演算等の処理は実装できているようでした。

感想

あまり強く触れていませんでしたが, parserとlexerを自作しているのは強いなぁと感じました。構文解析って実装が大変な印象が強いです(何もわかっていない顔)。

7. PaaSを作ってみた話 by Wp120_3238

LT資料:

speakerdeck.com

PaaSもどき(PaaSから少しブレている)を製作したお話。設計, API定義(goa使用), コマンドラインツールの製作等の流れについて説明。

感想

PaaSを「作る」という内容を見て目を疑いました。強すぎでは？

8. 心中恋電脳　～心中恋のバーチャル～ by tatuyan_edson

こちらを見ると良いと思います。

youtu.be

感想

落語を聞いたのは初めてだったのですが, 自然と話の内容が耳に入ってきました。マウスの音を扇子(?)で出しているのには驚きました。

9. 超入門プログラミングの勉強法 by kazuiti10

kazuiti10さんが記事を投稿していたので, そちらをご参照ください。

qiita.com

感想

勉強法として, - プログラミングの明確な目的を立て紙に書く - Progate有料1ヶ月→入門書→応用書 - 実際に制作物を作るの3点を挙げていました。これに関して上の2つは良いと思いますが, 最後の「制作物を作る」というのが難しいと感じました。そのため, 次回は「超入門制作物の制作法」を期待しています(冗談です)。

10. UTIPS 家事のやり方を共有するサービスの発表 by yuki384love

「家事の情報共有」に的を絞って問題点を考えてそれに対する解決法を見出し, アプリケーション開発に繋げたというお話。問題点に対する解決法を1つ1つ丁寧に説明していました。

感想

個人的に、その人にとっての「当たり前」を共有して欲しいという部分が印象的で, 開発だけでなく教育においても見落としがちだなと感じました。しかし, その「当たり前」の共有と一言で言っても全て書き出したらキリがないと思うので, そこが難しい部分でしょうね。

11. 虫食い算に学ぶ探索アルゴリズム by drken

LT資料:

虫食算に学ぶ、深さ優先探索アルゴリズム (combmof, 2018/12/23) from Kensuke Otsuki

www.slideshare.net

虫食い算の探索法というテーマから派生し, DFS(深さ優先探索)という探索法について具体例も交えつつ紹介していました。丁寧なスライドのおかげで, 音声がなくとも割合理解できる内容となっていました。

感想

やはり資料が分かりやすいなという印象が強かったです。スライドを作ったりや記事を書いたりするときにも参考になるLTでした。また, 紹介していたのは探索法(ソルバ)のみでしたが, 個人的に生成アルゴリズムも面白そうだなと感じました。

12. ゲームに使えるようなアルゴリズムやデータ構造の紹介 by CuriousFairy315

ゲームに使えそうなアルゴリズムとデータ構造について, 具体例も交えつつその仕組みも紹介していました。スライドはJavaで自作したそうです。

感想

個人的に, ランダムアイテム生成に関して比で確率を設定するというのは面白いと感じました。PCの破損というアクシデントがありながらも, 最終的に登壇できたのはラッキーでしたね。

交流会

プロ達と実際にお話できたのが本当に良かったです。しかし, 私は自信を持って話せる内容が無かったので, 肩身の狭い思いでした(早いところ青になりたいところです)。
また, Twitter上のアイコンと現実の本人の印象がかなり異なっていたことに非常に驚きました。どなたかがLTで触れていましたが, 「現実では生身というアバターしか存在しない」という表現, 割と好きです。

おわりに

ここまでで, CombMofにて発表された11個のLT(+1個の落語)について, 概要と個人的な感想をつらつらと書いてみました。LTには私の専門外のものもいくつかありましたが, プレゼンターの方々のおかげで少ない負担で聴くことができました。
主催者のもふたろうさんとスタッフの皆さん, ならびにLT枠のプレゼンターの皆さんには, 本当に感謝です。
こういう機会がまたあれば, 参加してみたいなと思います。

2018-12-09

ABC115参加記録と解説

参加記録競プロ AtCoder

結果

f:id:task4233:20181209123422p:plain 3WA全完で648位でした。
推定緑パフォらしいですが, 全完できて嬉しかったので良いです。

beta.atcoder.jp

A - Christmas Eve Eve Eve

beta.atcoder.jp

概要

12月の日付Dが与えられる。
D=25なら'Christmas',
D=24なら'Christmas Eve',
D=23なら'Christmas Eve Eve',
D=22なら'Christmas Eve Eve Eve'を出力せよ。

制約

$22 \leq D \leq 25$

解法

if文で問題文の通りに書きます。

#include <iostream>
using namespace std;

int main() {
  int D;
  cin >> D;
  
  if (D == 25) cout << "Christmas";
  else if (D == 24) cout << "Christmas Eve";
  else if (D == 23) cout << "Christmas Eve Eve";
  else cout << "Christmas Eve Eve Eve";
  cout << endl;
  return 0;
}

B - Christmas Eve Eve

beta.atcoder.jp

$i$ 個目の品物が $p_i$ 円の品物が $N$ 個ある。
$N$ 個の品物のうち最も高い品物を半額にできる時, 品物の合計金額はいくらか?

制約

$2 \leq N \leq 10$
$100 \leq p_i \leq 10000$
$p_i$ は偶数

解法

最も高い品物のみを半額にするので, 最大値のみを1/2すれば良いですね。そのため, ソートしてから最後の要素(最大値)のみを1/2して全ての要素を足せば良いです。

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector< int > p(N);
  for (int i=0; i<N; ++i) cin >> p[i];
  
  sort(p.begin(), p.end());
  
  int ans = 0;
  for (int i=0; i<N; ++i) {
    if (i < N - 1) ans += p[i];
    else ans += p[i] / 2;
  }
  
  cout << ans << endl;
  return 0;
}

C - Christmas Eve

beta.atcoder.jp

$i$ 本目の木の高さが $h_i$ メートルの木が $N$ 本植えられています。
その中から $K$ 本の木を選んで装飾する時, 装飾した木のうち最も高い木の高さと最も低い木の差を最小化してください。

制約

$2 \leq K$ < $N \leq 10^5$
$1 \leq h_i \leq 10^9$

解法

$K$ 本を選ぶときに木の高さの幅を最小化するためには, ソートしてから連続した $K$ 本を見てあげるのが良いでしょう。

なぜなら, 連続した $K$ 本のうち最初の木が最小, 最後の木が最大となるので, (最大の木) - (最小の木)を全て試せば木の高さの幅を最小化できるからです。

#include <iostream>
#include <algorithm>
using namespace std;

costexpr int INF 1 << 30;

int main() {
  int N, K;
  cin >> N >> K;
  vector< int > h(N);
  for (int i=0; i<N; ++i) cin >> h[i];
  
  sort(h.begin(), h.end());
  
  int ans = INF;
  for (int i=0; i<N-K+1; ++i) {
    ans = min(ans, h[i+k-1] - h[i]);
  }
  
  cout << ans << endl;
  return 0;
}

D-Christmas

beta.atcoder.jp

多次元バーガーはパティ(以下 $P$ と略す)とバン(以下 $B$ と略す)で出来ています。
レベルLの多次元バーガーは次のように定義される。

レベル $０$ バーガーは, $P1$ 枚である。
レベルバーガーとは,
- $B1$ 枚,
- レベル $L-1$ バーガー,
- $P1$ 枚,
- レベル $L-1$ バーガー,
- B $1$ 枚,
  をこの順に下から積み上げたものである。

レベル $N$ バーガーを作って下から $X$ 枚取った時, その中に $P$ は何枚あるか?

解法

f:id:task4233:20181209155156p:plain

レベル $L$ バーガー(以下 $L$ バーガーと略する)の定義を見ると, 再帰的に $L-1$ バーガーを呼び出しています。それなので,

$f(L) := L$ バーガーの枚数

とすると, この $f(L)$ は以下のように表せます。

$\displaystyle f(L) = \left\{ \begin{array}{ll} 1 & (L = 0) \\ 1 + f(L-1) + 1 + f(L-1) + 1 & (L \geq1) \end{array} \right.$

そして, $P$ の数は図の赤い部分と, f(L-1)の再帰に含まれるPの数のみです。それなので,

$getP(L) := L$ バーガーに含まれる $P$ の枚数
とすると, この $getP(L)$ は以下のように表せます。

$\displaystyle getP(L) = \left\{ \begin{array}{ll} 1 & (L = 0) \\ getP(L-1) + 1 + getP(L-1) & (L \geq1) \end{array} \right.$

また, 図と式を見ると分かりますが, $L$ バーガー $(L\geq1)$ は以下の手順で作れます。

$B$ を1つ置く
$f(L-1)$ を置く
$P$ を1つ置く
$f(L-1)$ を置く
$B$ を1つ置く

この上で, 下から $X$ 枚取ったときを考えてみます。作成手順を見ると上下対称なのが分かるので, 上から $X$ 枚の中に $P$ が何枚あるかを同様の手順で考えてみます。

手順	上からの枚数	含まれるPの数
$B$ を1つ置く	1	0
$f(L-1)$ を置く	$1 + f(L-1)$	$getP(L-1)$
$P$ を1つ置く	$1 + f(L-1) + 1$	$getP(L-1) + 1$
$f(L-1)$ を置く	$1 + f(L-1) + 1 + f(L-1)$	$getP(L-1) + 1 + getP(L-1)$
$B$ を1つ置く	$1 + f(L-1) + 1 + f(L-1) + 1$	$getP(L-1) + 1 + getP(L-1)$

f:id:task4233:20181209123624p:plain

すると, 上の図のように場合分けされます。 $X = 0$ の時は当然1つも選べないので省略しています。この図に従って再帰関数を実装し, main関数から呼び出すことで解を求められます。

#include <iostream>
using namespace std;
// オーバーフローの可能性があるため, 64bitのint_fast64_tを使用します。
using int64 = int_fast64_t;

// Lバーガーの枚数を格納します。
int64 memo[55];
// Lバーガーに含まれるPの枚数を格納します。
int64 p_memo[55];

int64 f(int64 L) {
  // すでにメモされている場合はそちらの値を利用します。
  if (memo[L] > 0) return memo[L];
  // 0バーガーの枚数はPのみで1枚です。
  if (L == 0) return memo[0] = 1;
  // LバーガーはB + f(L-1) + P + f(L-1) + Bなので, 
  // まとめると全体の枚数は2 * f(L-1) + 3枚になります。
  return memo[L] = 2 * f(L-1) + 3;
}

int64 getP(int64 L) {
  if (p_memo[L] > 0) return p_memo[L];
  if (L == 0) return p_memo[0] = 1;
  // LバーガーはB + f(L-1) + P + f(L-1) + Bなので, 
  // まとめるとPの枚数は2 * f(L-1) + 1枚になります。
  return p_memo[L] = 2 * getP(L-1) + 1;
}

int64 solve(int64 L, int64 X) {
  if (X == 0) {
    // 残りの枚数が0枚になったら0を返します。
    return 0;
  } else if (L == 0) {
    // 階層が0になってしまったらgetP(0)=1を返します。
    return getP(0);
  } else if (X <= 1 + f(L-1)) {
    return solve(L-1, X-1);
  } else if (X <= 2 + f(L-1)) {
    return getP(L-1) + 1;
  } else if (X <= 2 + 2*f(L-1)) {
    return getP(L-1) + 1 + solve(L-1, X-f(L-1)-2);
  } else {
    return getP(L-1) + 1 + solve(L-1, X-f(L-1)-2);
  }
}

int main() {
  int64 N, X;
  cin >> N >> X;
  f(N);
  getP(N);
  
  int64 ans = solve(N, X);
  cout << ans << endl;
}

感想

今回のABCは, 最近のABCとは異なる難易度だったと考えています。A-Cは最近のABCの傾向からすると拍子抜けな簡単さだったと思います。そして, D問題は難しいと言う人がいるかもしれませんが, それは「考える」難しさではなく, 「実装する」難しさだと思います。なぜなら, 今回のD問題は実際に書き出してみれば再帰関数の目星はつき, 朧げでも実装方法は思いついていたはずだからです。そのため, 落ち着いて, 時間をかければACすることは不可能ではなかったでしょう。

逆に, 厄介なのは, Small Multipleのような「考える」難しさを要求してくる問題だと考えています。あの問題を見てdijkstra法が出てきますか？私は出てきませんでした。そのような, 問題と解法を繋げるのが難しい問題が私にとっては難しいようです。

長々と語ってしまいましたが, 久々に粘ってACをもぎ取るムーブが出来て非常に楽しいコンテストになりました。このようなコンテストが続くと良いです。

はじめに

もくじ

開発していた環境

開発したもの

概要

サーバの環境構築

フロントエンド

バックエンド

DBサーバ

JSON APIサーバ

ORMライブラリ

開発に伴い作成した書類

良かった部分

設計書を書いてからコーディングを始めたこと

Pull Requestに対するレビューの義務化

docker-composeによる一括管理

slackによる情報共有

悪かった部分とその改善策

関係ない差分を含んだPull Requestを飛ばしてしまったこと

悪かった点

改善策

環境構築が遅かったこと

悪かった点

改善策

レビューの仕方が曖昧だったこと

悪かった点

改善策

今回の開発で学んだこと

技術的な話

docker-composeによる環境構築は時間をかけてもやっておくべき

公式のスクリプトにも誤りはあるのでコードを読んでみるのもアリ

不明瞭で必要のない差分を含むPull Requestは悲劇を生むことがある

非技術的な話

時間は有限

「グループワークに不満があるなら全部お前がやればいい」は大嘘

おわりに

はじめに

Git Challengeとは

きっかけ

イベント当日までに行ったこと

イベント当日に行ったこと

会場に到着するまで

会場に到着してから

スタッフによる技術解説 part1

Git Challengeにおける新システム構成

Gitでドメイン管理

昼食

競技本番&解説

スタッフによる技術解説 part2

コミットログで機械学習

懇談会

感想

競技に関して

懇談会に関して

展望

スタッフの皆さんへ

おわりに

TL;DR

はじめに

もくじ

プラサミとは？

きっかけ

当日のムーブ

会場入りまでの時間

会場入りの時間

競プロの時間

数学の時間

撤収の時間

感想と反省

まとめ

はじめに

もくじ

Bug Shooting Challengeとは

きっかけ

イベント前日までにしたこと

当日したこと

会場に到着するまで

会場に到着してから

スタッフの方々による技術解説

田村さん

1) `kのiビット目が0`かつ`Xのiビット目が0`のとき

2) `kのiビット目が1`かつ`Xのiビット目が1`のとき

8. 心中恋電脳　～心中恋のバーチャル～ by tatuyan_edson

9. 超入門プログラミングの勉強法 by kazuiti10