ctf4b2016博多参加記
ctf4b2016博多参加記
ctf4b博多に参加してきましたので参加記を
web講義
web問題についての講義でした.内容はXSSについて.この講義でgoogle CTFの一番簡単な問題がカバーできたのかなぁ...
web問題を解くためのツール類の紹介もあり,google CTFのときに「え??サーバに盗んだcookie送りつけるの??管理してるサーバとかないし無理じゃね???」と思った私にとっては嬉しい講義だった.
フォレンジックス講義
パッケットキャプチャしたファイルが与えられるから,そこからフラグを探し出してくださいという趣旨の問題群を解くための講義だった.
ツールの機能を活用していかに効率的にパケットを読んでいくか,また,集中して読むべきパケットがどれかという点に焦点を当てての講義だった.前後のパケットの内容から,いつフラグが通信されたかを推測する話や,使用されたプロトコルの統計情報から集中して読むべきパケットを絞り込むと良いらしい.
講義を受けて,プロトコルとその代表的な利用目的について勉強しておくと,通信内容について推測できるから良いのかなと思った.
バイナリ講義
逆アセンブルされたバイナリを読む講義だった.mipsなら3ヶ月ぐらい読んでいたことがあったが,x86は未知の世界.x86はディスティネーションレジスタが決め打ちされてる命令があったりとか,分岐の方法とか覚えるのがmipsと比べて辛い印象を持っている.
幸いにも今回の講義で読んだバイナリたちは素直なバイナリだったので,何がなんだかわからんということはなかった.
パタヘネ読んでたりとか,低級な部分を大学で研究してたりというバックグラウンドがあったせいだろうが,今回の講義の中では一番簡単な講義に感じた.
実際にプログラムを逆アセンブルして読もうとすると,どの処理を集中して読んだら良いかわからん.ということが起こりがちなので,読むべき部分の絞り込みとかの話がもう少し欲しかったかなぁ...
あとIDAすごい.ループの構造をグラフィカルに表示してくれる.あれいい.
練習コンテスト
コンテストについて
6位でした.やったね!講義でやったことをきっちりやれば解ける問題が出ていたので,練習コンテストとして良い問題セットだったと思う.
MISCと分類されていた問題
基本的にやるだけっぽかった.CountUpGameの必勝法は競技プログラミングのスキルがCTFに活きたなーと.
Webの問題
web100点は憶えてない.web200はダブルクォテーションと山括弧使っていけそうだったけど,うまくいかなかった.あれなんでだろうな.
ICPC2016国内予選参加記
はじめに
チーム t9qmib としてnikollson, nola_suzと一緒にICPC国内予選に参加しました。結果は4完24位で、正式なアナウンスはまだですがアジア地区筑波大会への参加権を獲得できているはずです。
A問題
A問題の担当でした。2つ目の出力ファイルの作成時間を見ると6分でACしたようです。問題文の印刷が終わらないうちにACしてかなり良い調子。
B問題
nikollsonの担当。30分経過時点で通っていなくて嫌な予感がする。nikollsonの実力でこの時間にAC取れてないのはおかしい。途中でコーダーを交代して51分ごろにAC。図らずもB問題の担当になる。
C問題
素数定理を知っていたので、エラトステネスの篩みたいに書けば計算時間的には問題なく終わることに気づく。最大ケースが与えられていたことにはサンプルを通す段階で気づいた。B問題で詰まっていたので代わってもらい37分でAC。私がコーダーでした。
D問題
問題の概要を説明された時に「これ、TDPCで見た問題だ!」となる。TDPCのiwiの解法の方針は覚えていたものの、細かいところが記憶になかった。もやっとした方針を nola_suz 説明すると「区間DPってこと?」と言われ、そのまま nola_suz が漸化式を立ててコーディングすると64分でACした。強い。自分がiwiを書いたときバグに苦しんだ記憶があったから、バグが出て1時間ぐらいかかることを覚悟していた。
E問題
共有部分の表面積を辺の重みとしたグラフを作って、辺の重みの合計が最大になるような、連結な部分グラフを求める問題。ああでもないこうでもないと言いながら解法が立たずに苦しんでいた。コンテスト終了後にblue_jamさんがやってきて「いやぁ、E問題のEはEASYのEでしたね。」といわれる。一つの立方体は最大でも二つの立方体としか共有部分を持たないという制約を読み落としていたことに気づく。チームメンバーのうち2/3が制約を読み落としていた。
F問題
実装が重いやるだけ問題というnikollsonの直感。根付き木の同型判定を効率的にやる方法を知らなかったが、nola_suzが「ノードを訪れるときに '(' を、ノードから親に戻る時に ')' を文字列に追加するようにして、子から上がってきた文字列を辞書順にソートして親に上げれば良い感じに同型判定できるんじゃない?」と言って効率的に根付き木の同型判定ができることが分かる。完全にプロ。効率的な根付き木の同型判定のアイデアが出た時点で、E問題の解法が立たずに1時間何もしていない状態だったので、何もしないよりは書いていたほうがいいだろうという判断で実装に入る。この時点で残り1時間。途中、H問題の解法が分かったという声が上がったが、その時点で残り30分少々。チームメイトに残り20分時点までに一通りの実装が完了するが、残り20分でデバッグが完了する見込みは薄いことを伝えるが、F問題を解き続けたほうがいいという判断になった。結局間に合わず。1時間PCを占領したのに申し訳ない結果になってしまった。
ちなみに説明された解法はこんなの
G問題
よんでない
H問題
やるだけじゃないかという意見が出たが、この時点でコンテスト終了まで残り30分ということで、F問題を書き続けるほうがいいだろうという判断でコーディングせず。
感想
どう見ても5完セット。あわよくば6完狙う感じでやらなきゃだめだった。
A問題の実装、図らずもB問題の実装、C問題の実装、間に合わなかったF問題の実装を担当していました。チーム中レーティング最弱なのになぜこうなった。
Distributed Code Jam 2016 について
はじめに
Distributed Code Jam R1に参加して、環境構築とか環境構築とか辛かった人を散見したので記事を書くことにした。
Distributed Code Jam とは
Distributed Code Jam (DCJ) とは、Google Code Jam (GCJ) に併設された分散処理のコンテストです。ざっくり言うと、100並列で競技プログラミングをやるコンテスト。2016年はGCJのRound2進出者に参加権がありました。
環境について
普段の競技プログラミングとは異なるところもあるので、思いついたところのまとめ。Mac/C++で参加しました。
並列化用ライブラリ
MPIっぽい関数を実装したライブラリがコンテストの運営から配られます。コンテスタントはそれを使ってプログラムを実装します。基本型の送受信用キューへの追加/読み出しと、送受信用キューの内容の送受信程度でしょうか。ライブラリの詳しい仕様を把握しないまま書いたら書けてしまったので詳しい仕様は言えない。
入出力仕様
入力は関数を呼んで取得する。問題ごとに入力用の関数が用意されていて、入力用関数の仕様は問題文中で与えられる。problem_ name.h というヘッダファイルに実装されているので、それをインクルードする必要がある。ヘッダファイルはソースと同じディレクトリの中に置いてね。sample-inputをくれるヘッダファイルは問題文の下のほうにあるリンクからダウンロードできました。答えの出力はどこか一つのノードが標準出力に吐けばよい。
環境構築
Distributed Guideに書かれてある。
Linux || Mac
LinuxかMacがメイン環境の人は環境構築がしやすいから幸せだ。DCJ 用のテスト用ツールを Distributed Guide に書かれてあるリンクから落としてくる。.tar.bz になってるので、 コマンドラインで
tar jxvf dcj.tar.bz
とかやって展開する。あとはGoをインストールして、
cd src/parunner/ go build cp parunner ../../executable/
とやると環境構築おわり。
config.jsonにどのコンパイラを使うかとかを指定するようになってるので、「コンパイラみつかんねーよ」と怒られたりしたらconfig.jsonを書き換えるといいかもしれない。sample-configsの中にいくつか設定例があったので、自分で書き換える必要が出てくることはないかも。テストを行うには、Distributed Guide に書かれてあるコマンドを打てばよい。
problem=prblem_name srcfile=${problem}.cpp ${DCJ_UNPACK_DIR}/dcj.sh build --source=$srcfile
problem=prblem_name runnable=${problem} ${DCJ_UNPACK_DIR}/dcj.sh run --executable=./${runnable} --nodes=100 --output=all
とか書いてスクリプトにまとめとくと便利。
SRM501 div2 hard 1000pts : FoxAverageSequence 解説
はじめに
SRM501 div2 1000pts を解いたら計算量の落とし方がいい感じだった && 多くの人が自分よりひとつ悪いオーダーで通してて悔しかった ので解説記事を書いてみる
問題概要
美しい整数列Aは以下の制約を満たす。
- 要素数40以下
- となるiは存在しない
整数列seqが与えられる。seqの各項は-1以上40以下である。seqの-1の項を0以上40以下の任意の数に変えることが出来るとき、seqから得られる美しい整数列の総数を求めよ。
解法
dp(i,j,k,l)を、i個目までの和がj、i個目の要素がkで、i個目の要素がi-1個目の要素から{ l=0 : 減少していない, l=1 : 減少している}として、
に従って更新すればとりあえず答えは求まる。
但し、dp(i,j,k,l)はseqのi個目の要素が-1で無くseqのi個目の要素がkでない場合0である。また、k * i ≤ j - kを満たさない場合もdp(i,j,k,l)=0とする。
これを愚直に計算しようとすると、時間計算量はseqの要素数nとseqの各要素が取りうる値の最大値mを用いてとなり微妙に怪しい*1。
ということで、よく使う例の方法で計算量を落としにかかかる。
同じ要領で、2番目の式
を変形すると
となる。
これでdp表の更新にかかるオーダーが減り、全体のオーダーは無事に落ちたのだが、seqのi個目の要素が-1で無い場合のdp表の更新を上の漸化式に従って行うと間違う。なぜならば、を計算する場合を例にとれば、 のつもりで書いている が、k-1とseqのi+1番目の要素が異なる場合、 になるためである。
seqのi番目の要素が-1で無い場合、dp(i,j,k,l)はseqのi番目の要素とkが一致した場合には
を使って更新し、そうでない場合は0にすればよい。各(i,j,l)の組に対しての更新が回と、の更新が回しか呼ばれないのだから、DP全体の計算量はに収まる。
実装
バグの箇所がなかなか見つからずにつらかった。書き直す気はない。ぺたり。
#include <string> #include <vector> #include <algorithm> #include <cmath> #include <cstdlib> #include <map> #include <set> #include <iostream> #include <sstream> #include <unordered_map> #include <unordered_set> #include <stack> #include <queue> #include <deque> #include <list> #include <utility> #include <cassert> using namespace std; #define all(x) ((x).begin()),((x).end()) #define pb push_back #define mkp make_pair #define fi first #define se second typedef long long ll; typedef pair<int,int> pii; typedef pair<double,double> pdd; const int mod = 1e9+7; int dp[50][50*50][50][2]; vector<int> S; int solve(int i, int j, int k, int l) { if(i < 0 || j < 0 || j > 40*40|| k < 0 || k > 40) return 0; if(dp[i][j][k][l] + 1) return dp[i][j][k][l]; if(k * i > j - k) return dp[i][j][k][l] = 0; if(S[i] + 1) { if(S[i] != k) return dp[i][j][k][l] = 0; dp[i][j][k][l] = 0; for(int k_ = k + l; 0 <= k_ && k_ <= 40; k_ = k_ + (l == 0 ? -1 : 1)) { dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,0)) % mod; if(l == 0) dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k_,1)) % mod; } } else { dp[i][j][k][l] = 0; if(l == 0) { for(int l_ = 0; l_ < 2; l_++) dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k,l_)) % mod; dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j-1,k-1,0)) % mod; } else { dp[i][j][k][l] = (dp[i][j][k][l] + solve(i-1,j-k,k+1,0)) % mod; dp[i][j][k][l] = (dp[i][j][k][l] + solve(i,j+1,k+1,1)) % mod; } } return dp[i][j][k][l]; } class FoxAverageSequence { public: int theCount(vector <int> seq) { S = seq; for(int i = 0; i < 50; i++) for(int j = 0; j < 50*50; j++) for(int k = 0; k < 50; k++) dp[i][j][k][0] = dp[i][j][k][1] = -1; for(int i = 0; i < 50*50; i++) for(int j = 0; j < 50; j++) dp[0][i][j][0] = dp[0][i][j][1] = 0; if(S[0] == -1) { for(int i = 0; i <= 40; i++) { dp[0][i][i][0] = 1; } } else dp[0][S[0]][S[0]][0] = 1; ll res = 0; for(int i = 0; i <= 40 * 40; i++) { for(int j = 0; j <= 40; j++) { for(int k = 0; k < 2; k++) { res = (res + solve(seq.size()-1,i,j,k)) % mod; } } } /* cout << endl; for(int i = 0; i < 5; i++) { for(int j = 0; j < 20; j++) { for(int k = 0; k < 50; k++) { cout << dp[i][j][k][0] << "," << dp[i][j][k][1] << " "; } cout << endl; } cout << endl; } // */ return res; } };
SRM356 div2 medium 500pts : AverageProblem 解説
はじめに
SRM356 div2 500pts を部内の練習で解いたところ、面白い問題だった && 人々が辛そうにしてた && 日本語の解説記事が見つからなかったので解説記事を書いてみることにした。
問題概要
0 以上 10 以下の範囲の整数で評価する、評価項目が 1 つ以上あるアンケートを 1 つ 以上とった。各アンケート毎に、そのアンケートの評価項目毎の評価の平均を小数第4位で切り捨てたものが与えられる。アンケートに回答した回答者の人数としてありうる人数の最小値を求めよ。
- 1 ≤ アンケート数 ≤ 50
- 1 ≤ アンケート毎の項目数 ≤ 50
解法
アンケートの回答者を1人から順に調べ、その人数でアンケートを回答したとき、入力として与えられた平均となるような回答の方法があるかどうかを調べればよい。アンケートの項目ごとにどのような判定を行うべきかを解説する。
判定法
アンケートの回答者を人、各人のアンケート項目への評価をとすると、アンケートの評価の平均は、
入力として与えられる平均は小数点以下3桁まででそれ以下の値は切り捨てられている。切り捨てられた値をとして、と表せる。 上の式は
と変形でき、右辺を整数にできるか否かを判定する問題となる*1。今回の場合、左辺の値が具体的に何になるかを考慮する必要は無い。右辺を整数にするためには、入力として与えられる平均が表現できる最小の値が*2、アンケートの参加人数が人(定数)であったとき、半開区間に整数があればよい。がの範囲の値を取るためである。
計算量
アンケートの数を、アンケートの項目数を、与えられる平均が表現できる最小の値をとすると、時間計算量は
実装
上で書いたことを実装すればよい。誤差対策として入力として与えれれる値を1000倍して持っておくとよい。整数であれば剰余演算子を用いれるので、判定を行う部分の実装も楽になる。
#include <string> #include <vector> #include <utility> #include <algorithm> #include <iostream> #include <cmath> #include <cstdlib> #include <set> #include <map> #include <queue> #include <stack> #include <sstream> #include <list> #include <deque> using namespace std; #define fi first #define se second #define all(x) (x).begin(),(x).end() typedef long long ll; typedef pair<int,int> pii; typedef pair<double,double> pdd; typedef pair<long,long> pll; class AverageProblem { public: int numberOfParticipants(vector <string> marks) { vector<int> ave; // 入力の受け取り部 for(int i = 0; i < marks.size(); i++) { stringstream sstr(marks[i]); string s; while(sstr >> s) { // 入力を1000倍して, ave に追加する int a = 0; for(int j = 0; j < s.size(); j++) { if(s[j] != '.') { a *= 10; a += s[j] - '0'; } } ave.push_back(a); } } // resはアンケートに答えた人の人数の候補 int res = 1; // このループは1000回を超えて回ることはない while(1) { bool flg = true; for(int i = 0; i < ave.size() && flg; i++) { // diff は ave[i] * res 以上の最小の整数との差 int diff = (1000 - (ave[i] * res) % 1000) % 1000; if(diff < res) // 条件成立 ; else flg = false; // 条件不成立 } // ave のすべての要素に対して条件が成立していれば, その res が答え if(flg) return res; // そうでなければresを増やしてまた調べる res++; } } };
感想
素直な問題で解いていて面白かった。計算量の見積もりや、アンケートの回答者がN人のとき入力として与えられた平均にできるか否かの判定など、div2med(500pts)の問題としては難しいように感じた。この難易度なら最近のdiv1easy(250pts)でも通用するのではないだろうか。切り捨てた値を適当な文字で表して式変形を進めるという考えに至れれば解け、行う式変形も分母を払う程度で難しくないため、その発想に至れるかどうかが勝負の分かれ目のよう。
無視した値を適当な文字で表すというアイデアに関しては、例えば電気系であれば抵抗の誤差を適当な変数として表して、最終的にどの程度誤差が現れるかを調べるなどの応用が利くので押さえておきたい。
2015年 競技プログラミングの進捗
今年の競技プログラミングの進捗です。
ICPC
チーム l-_-..-_-..-_-lJJJJJJ として参加。
国内予選37位。アジア地区予選進出ならず。
今年は自分自身の実力もメンバーの実力も去年より上だったので今年こそはアジア地区予選に行けると思っていただけに悔しかった。
ICPCは来年で引退なので、来年こそはアジア地区予選に出場したいです。
TopCoder
rating: 1448 -> 1524 (+76)
rating(highest): -> 1448 -> 1580 (+132)
div1easy が安定してきて黄色にはなれたものの、この先維持できるかどうか不安なところ。
今年のratingの上げ幅が微妙だったのと、来年でICPC最後なので難しい目標ではあるけども highest 1800 と黄色安定を目指したい。
Codeforces
rating: unrated -> 1849
rating(highest): unrated -> 1913
今年の9月からcodeforcesにも出るようになりました。
来年はd2Dまで安定できる実力をつけてd1に定着したい。