Posts

グラフを使った解法を勉強した. グラフの表現方法として隣接行列と隣接リストの2つがあって, 最短経路問題を特にはベルマンフォード法, ダイクストラ法, ワーシャル-フロイド法があり, 最小全域木問題を特にはプリム法とクラスカル法がある. この一部を使った演習問題を紹介する. 二部グラフ判定 深さ優先探索を用いて, 隣接している頂点をどんどん塗っていく. グラフは隣接リストを使って表現されている. #include <iostream> #include <vector> using namespace std; const int MAX_V = 10000; vector<int> G[MAX_V]; int V, E; int color[MAX_V]; //頂点を1と-1で塗っていく bool dfs(int v, int c) { color[v] = c; for (int i = 0; i < G[v].size(); i++) { // 隣接している頂点が同じ色ならfalse if (color[G[v][i]] == c) { return false; } // 隣接している頂点がまだ塗られていないなら-cで塗る if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) { return false; } } return true; } int main(int argc, char const *argv[]) { cin >> V >> E; for (int i = 0; i < E; i++) { int s, t; cin >> s >> t; G[s].push_back(t); G[t].push_back(s); } for (int i = 0; i < V; i++) { if (color[i] == 0) { if (!dfs(i, 1)) { printf("No\n"); return 1; } } } printf("Yes\n"); return 0; } ```cpp ### Roadblocks 道を辺として, 交差点を頂点として2番目に短い経路を求める問題. 基本的にはダイクストラ法を用いるが, ２番目に短い経路も記憶しておくところがみそ. ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_N = 1000; const int INF = 99999999; struct edge { int to, cost; }; typedef pair<int, int> P; // firstは最短距離, secondは頂点の番号 int N, R, E; vector<edge> G[MAX_N]; // グラフの隣接リスト表現 int dist[MAX_N]; int dist2[MAX_N]; void read() { cin >> N >> R >> E; for (int i = 0; i < E; i++) { int s, t, c; cin >> s >> t >> c; edge x, y; x.to = s; y.to = t; x.cost = c; y.cost = c; G[s].push_back(y); G[t].push_back(x); } } void solve() { priority_queue<P, vector<P>, greater<P> > que; fill(dist, dist + N, INF); fill(dist2, dist2 + N, INF); // 発ノード dist[0] = 0; que.push(P(0, 0)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; int d = p.first; if (dist2[v] < d) { // 2番目の最短路より長い continue; } // vと隣接している頂点を更新 for (int i = 0; i < G[v].size(); i++) { edge e = G[v][i]; int d2 = d + e.cost; if (dist[e.to] > d2) { // 最短より短い場合 swap(dist[e.to], d2); que.push(P(dist[e.to], e.to)); } if (dist2[e.to] > d2 && dist[e.to] < d2) { // ２番目より短い場合 dist2[e.to] = d2; que.push(P(dist2[e.to], e.to)); } } } printf("%d\n", dist2[N - 1]); } int main(int argc, char const *argv[]) { read(); solve(); return 0; } ```cpp ### Conscription 人を頂点として親密度をコスト付きの辺として, 最小全域木をもとめる問題. この時, コストの高い辺を使いたいのでコストの正負を反転させる. また, この問題は男と女が分けられているが, 特殊な構造を使わなかった. 最小全域木を求めるときはクラスカル法を用いた. クラスカル法はUnionFind木の手法を応用している. ```cpp #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_N = 50000; const int MAX_E = 50000; const int MAX_R = 50000; // union find // -------------------------------------------- int par[MAX_N]; int depth[MAX_N]; void init_union_find(int n) { for (int i = 0; i < n; i++) { par[i] = i; depth[i] = 0; } } int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (depth[x] < depth[y]) { par[x] = y; } else { par[y] = x; if (depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y) { return find(x) == find(y); } struct edge { int u, v, cost; }; bool comp(const edge& e1, const edge& e2) { return e1.cost < e2.cost; } edge es[MAX_E]; int V, E; int kruskal() { sort(es, es + E, comp); init_union_find(V); int res = 0; for (int i = 0; i < E; i++) { edge e = es[i]; if (!same(e.u, e.v)) { unite(e.u, e.v); res += e.cost; } } return res; } int N, M, R; int x[MAX_R], y[MAX_R], d[MAX_R]; void read() { cin >> N >> M >> R; for (int i = 0; i < R; i++) { cin >> x[i] >> y[i] >> d[i]; } } void solve() { V = N + M; E = R; for (int i = 0; i < E; i++) { es[i] = (edge){x[i], N + y[i], -d[i]}; } printf("%d\n", 10000 * (V) + kruskal()); } int main(int argc, char const* argv[]) { read(); solve(); return 0; } ```cpp ### Layout 牛を頂点と考え, 牛の番号, 仲の良さ, 仲の悪さをコストつきの辺として最短経路を求める問題. 発想としては, 全てを制約条件に落としこんだ結果, 両辺に変数が1つずつしか現れていないことに着目する. 今回は負の辺があるのでベルマンフォード法を用いる. 負閉路が存在するかどうかは, 牛の数だけupdateを行ったあとにも更新があるかどうかで判断する. ```sql #include <iostream> #include <queue> #include <vector> using namespace std; const int MAX_ML = 10000; const int MAX_MD = 10000; const int MAX_N = 1000; const int INF = 99999999; int N, ML, MD; int AL[MAX_ML], BL[MAX_ML], DL[MAX_ML]; int AD[MAX_MD], BD[MAX_MD], DD[MAX_MD]; int d[MAX_N]; bool updated; void read() { cin >> N >> ML >> MD; for (int i = 0; i < ML; i++) { cin >> AL[i] >> BL[i] >> DL[i]; } for (int i = 0; i < MD; i++) { cin >> AD[i] >> BD[i] >> DD[i]; } } void update(int& x, int y) { if (x > y) { x = y; updated = true; } } void bellmanford() { for (int k = 0; k <= N; k++) { updated = false; // i+1からiへコスト0 for (int i = 0; i + 1 < N; i++) { if (d[i + 1] < INF) { update(d[i], d[i + 1]); } } // ALからBLへコストDL for (int i = 0; i < ML; i++) { if (d[AL[i] - 1] < INF) { update(d[BL[i] - 1], d[AL[i] - 1] + DL[i]); } } // BDからADへコスト-DD for (int i = 0; i < MD; i++) { if (d[BD[i] - 1] < INF) { update(d[AD[i] - 1], d[BD[i] - 1] - DD[i]); } } } } void solve() { // 負閉路チェック fill(d, d + N, 0); bellmanford(); if (updated) { printf("%d\n", -1); return; } fill(d, d + N, INF); d[0] = 0; bellmanford(); int res = d[N - 1]; if (res == INF) { res = -2; } printf("%d\n", res); } int main(int argc, char const* argv[]) { read(); solve(); return 0; } ```cpp ## 感想 最後の牛の並びを最短経路問題に変換する方法はむずすぎる….

第3回CTF勉強会 ksnctfの9, 11, 12, 13が課題で, 14が演習問題である. 11が難しいらしい 9 Digest is secure! pcapファイルをダウンロードして, wiresharkでhttp通信をフィルタリングしてみると, digest認証の通信が行われている. ちなみにDigest認証とは、 Digest認証とは、Basic認証と同じくApacheで利用できるアクセス制限です。ユーザーIDとパスワードを求める点までは全く同じですが、入力されたユーザーIDとパスワードをハッシュ関数であるMD5を用いて解析されにくい状態で送信する仕組みです。しかし、Basic認証と比べて後発の機能なので、かつては一部対応していないブラウザがありました。現在ではほとんどのブラウザに対応しているため、Basic認証ではなくDigest認証が使われるケースが増えています。レンタルサーバー比較なび ここで, 認証の際に渡しているパラメータをみてみる. Digest username=“q9” realm=“secret” nonce=“bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b” uri="/~q9/" algorithm=MD5 response=“c3077454ecf09ecef1d6c1201038cfaf” qop=auth nc=00000001 cnonce=“9691c249745d94fc” これから以下のようにresponseが作成される. A1 = ユーザ名 ":" realm ":" パスワード A2 = HTTPのメソッド ":" コンテンツのURI response = MD5( MD5(A1) ":" nonce ":" nc ":" cnonce ":" qop ":" MD5(A2) ) これをみると. パスワードがわからなくてもA1さえわかればサーバーから送られてきたnonceを元にresponseを生成できることがわかる. ここで, A1を得るためにresponseを解読する. MD5は脆弱性が存在し鍵長も短いので復号ツールで復号できてしまう. 追記 後のパケットにA1が帰ってきているので, ツールを使わなくて良い. Qiita:暗号化とハッシュ化に関する基本的な事柄まとめ Hash Toolkit: 復号ツール c627e19450db746b739f41b64097d449:bbKtsfbABAA=5dad3cce7a7dd2c3335c9b400a19d6ad02df299b:00000001:9691c249745d94fc:auth:31e101310bcd7fae974b921eb148099c この結果A1がわかった. ちなみにA1は解読できなかったのでパスワードがわからない. しかし他の全てのパラメータがわかるのでresponseを生成できる. ...

平成最後の日も蟻本の勉強をしてみた. 二分木, 二分探索木, Union-Find木を使った問題を3問解いた. priority_queueを用いる問題 1 expedition ガソリンを補給する回数を最小限に抑える問題. 探索としては, 今あるガソリンで次のガソリンスタンドに辿り着けなかったら, 過去に通過した供給量が一番大きいガソリンスタンドで補給したことにする. ここで, ガソリンスタンドをpriority_queueに入れて, 供給量が大きいもの順に並べていた. #include #include using namespace std; const int MAX_N = 10000; int N, L, P; int A[MAX_N + 1], B[MAX_N + 1]; void read() { cin >> N >> L >> P; for (int i = 0; i < N; i++) { cin >> A[i]; } for (int i = 0; i < N; i++) { cin >> B[i]; } } void solve() { A[N] = L; B[N] = 0; priority_queue que; int ans = 0, pos = 0, tank = P; for (int i = 0; i <= N; i++) { int d = A[i] - pos; // ガソリンを補給 while (tank - d < 0) { if (que.empty()) { puts("-1"); return; } tank += que.top(); que.pop(); ans++; } tank -= d; pos = A[i]; que.push(B[i]); } printf("%d\n", ans); } int main(int argc, char const *argv[]) { read(); solve(); return 0; } ```cpp ### 2 fence repair なるべく長い板を切らせないように目的の板の集合を手に入れる問題. ナイーブに実装すると`O(N^2)`時間になってしまうが, `priority_queue`を用いれば`O(NlogN)`時間になる. ```cpp const int MAX_N = 10000; int n, l[MAX_N]; void solve() { cin >> n; for (int i = 0; i < n; ++i) { cin >> l[i]; } LL ans = 0; priority_queue, greater > que; for (int i = 0; i < n; i++) { que.push(l[i]); } while (que.size() > 1) { int l1, l2; l1 = que.top(); que.pop(); l2 = que.top(); que.pop(); ans += l1 + l2; que.push(l1 + l2); } printf("%lld\n", ans); } int main() { solve(); return 0; } ```cpp #### `priority_queue`の小さい順 ```cpp priority_queue<int, vector<int>, greater<int> > que; ```cpp このように宣言する. ### 3 食物連鎖 複数の情報から矛盾している情報の数を求める. 食物連鎖の関係に矛盾がないことを調べるのにUnion-Find木を用いる. 情報を見ると, 同じ種類に属するか捕食被食の関係にあるという情報だけで種類を特定できない. そこで, 3通りのUnion-Find木を作って1つの木が同時に実現するということにする. 以下がUnion-Find木の実装である. ```cpp // union find // -------------------------------------------- int par[MAX_N]; int depth[MAX_N]; // 初期化 void init(int n) { for (int i = 0; i < n; i++) { par[i] = i; depth[i] = 0; } } // 木の根を返す int find(int x) { if (par[x] == x) { return x; } else { return par[x] = find(par[x]); } } // 木を併合する void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (depth[x] < depth[y]) { par[x] = y; } else { par[y] = x; if (depth[x] == depth[y]) depth[x]++; } } bool same(int x, int y) { return find(x) == find(y); } int N, K; int T[MAX_K], X[MAX_K], Y[MAX_K]; void solve() { cin >> N >> K; for (int i = 0; i < K; i++) { cin >> T[i] >> X[i] >> Y[i]; } init(N * 3); int ans = 0; for (int i = 0; i < K; i++) { int t = T[i]; int x = X[i] - 1, y = Y[i] - 1; // 0...N-1 // 正しくない番号 if (x < 0 || x >= N || y < 0 || y >= N) { ans++; continue; } if (t == 1) { // xとyは同じ種類という情報 if (same(x, y + N) || same(x, y + N * 2)) { ans++; } else { unite(x, y); unite(x + N, y + N); unite(x + N * 2, y + N * 2); } } else { if (same(x, y) || same(x, y + N * 2)) { ans++; } else { unite(x, y + N); unite(x + N, y + N * 2); unite(x + N * 2, y); } } } printf("number of wrong info is %d\n", ans); } int main() { solve(); return 0; } ```cpp ## 感想 Union-Find木を知らなかったので, 食物連鎖の実装が綺麗でわかりやすかった. これも標準のライブラリがあればいいのに…

アルゴリズム活用力は, 主にコーディングの試験の際に見られるところであり, webアプリやモバイルアプリを作るのにはあまり必要ないかもしれない. しかし, 将来転職する際にAtcoderである程度の成績を納めていたら強いのではという理由と, 単に楽しいからという理由で蟻本の中級くらいやりたいなと思っている. ってか, 今日のAtcoder全然解けへんくて萎えた… 今回は, 2_3 値を覚えて再利用"動的計画法"を勉強した. 01ナップサック問題 dpを使った動的計画法の初歩が書かれていた. 全探索を行うとO(2^n)かかってしまうところが, メモ化によりO(nW)の計算量で済む. この問題のコツは, 品物と重さを引数として価値の総和を出した時に計算結果を残しておくという発想から. const int MAX_N = 100; int n, W; int w[MAX_N], v[MAX_N]; // dp[i+1][j]: i番目までの品物から重さの総和がj以下となるように選んだ時の, // 価値の総和の最大値 int dp[MAX_N + 1][MAX_N + 1]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } cin >> W; for (int i = 0; i < n; i++) { for (int j = 0; j <= W; j++) { if (j < w[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]); } } } printf("max sum value is %d\n", dp[n][W]); return 0; } ```cpp #### 参考: メモ化テーブルを初期化する方法 ```cpp memset(dp, -1, sizeof(dp)); ```cpp ってな感じで, 0と-1ならば初期化できる. 1はできない. ### 最長共通部分列問題 この問題のコツは, 2つも文字列を引数とした計算結果をメモ化するところである. 最初のうちはDPテーブルをかくと漸化式が浮かびやすいかなと思う. ```cpp const int MAX_N = 1000; int n, m; char s[MAX_N], t[MAX_N]; int dp[MAX_N][MAX_N]; int main() { cin >> n >> m >> s >> t; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (s[i] == t[j]) { dp[i + 1][j + 1] = dp[i][j] + 1; } else { dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]); } } } cout << "max value is " << dp[n][m] << endl; return 0; } ```cpp ### 個数制限なしのナップサック問題 個数制限がなくなったことで, 愚直に計算するとforループがもう一つ増えてしまう. そこで無駄に計算を行なっている箇所を探して, 漸化式を簡単にする. コツとしては, DPテーブルをみて漸化式の動きをみて, 簡単になる箇所がないかを探すのみだと思う. #### 参考: 偶奇を考えた配列の再利用 ```cpp for (int i = 0; i < n; i++) { for (int j = 0; j <= W; j++) { if (j < w[i]) { dp[(i + 1) & 1][j] = dp[i & 1][j]; } else { dp[(i + 1) & 1][j] = max(dp[i & 1][j], dp[(i + 1) & 1][j - w[i]] + v[i]); } } } ```cpp `(i + 1) & 1`の使い方がめちゃうまい気がする… こうして, 2行分のデータを確保できる. ### 01ナップサック問題その2 重さの制約条件が緩くなって, Wが10^9まで飛んでしまった時は, Wでforループを回したくなくなる. そんなときは, メモ化けする対象を入れ替えることでうまくいく. メモ化の値に大きくなるものを入れるのがコツな気がする. ```cpp const int MAX_N = 100; const int MAX_V = 100; const int INF = 99999999; int n, W; int w[MAX_N], v[MAX_N]; // dp[i+1][j]: i番目までの品物から価値の総和がjとなるよう選んだときの, // 重さの総和の最小値 そのような解が存在しない場合は十分大きな値INF int dp[MAX_N + 1][MAX_N * MAX_V + 1]; int main() { // 入力値の読み込み cin >> n; for (int i = 0; i < n; i++) { cin >> w[i] >> v[i]; } cin >> W; // 解く fill(dp[0], dp[0] + MAX_N * MAX_V + 1, INF); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= MAX_N * MAX_V; j++) { if (j < v[i]) { dp[i + 1][j] = dp[i][j]; } else { dp[i + 1][j] = min(dp[i][j], dp[i][j - v[i]] + w[i]); } } } int res = 0; for (int i = 0; i <= MAX_N * MAX_V; i++) { if (dp[n][i] <= W) { res = i; } } printf("max sum value is %d\n", res); return 0; } ```cpp ### 個数制限付き部分和 bool値をメモ化けするのは無駄がある. そこで大きな値である残りの`a_i`を入れることで漸化式が改善されて計算量を落とすことができる. ```cpp const int MAX_N = 100; const int MAX_K = 100000; int n; int K; int a[MAX_N]; int m[MAX_N]; // dp[i+1][j]: i番目まででjを作る際に余る最大のi番目の個数(作れない場合は-1) int dp[MAX_K]; int main() { cin >> n; for (int i = 0; i < n; i++) { cin >> a[i] >> m[i]; } cin >> K; memset(dp, -1, sizeof(dp)); dp[0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j <= K; j++) { if (dp[j] >= 0) { dp[j] = m[i]; } else if (j < a[i] || dp[j - a[i]] < 0) { dp[j] = -1; } else { dp[j] = dp[j - a[i]] - 1; } } } if (dp[K] > 0) { printf("answer is YES\n"); } else { printf("answer is NO\n"); } return 0; } ```cpp ### 最長増加部分列問題 案外奥が深い問題. 部分文字列の候補があがってくるのでそれをメモ化すると`O(n^2)`で解くことができるが, 候補よりも, 最終要素がなにであるかに着目すると`O(n \log n)`で解くことができる. ここらへんは地頭の良さ. #### 参考: lower_bound ```cpp fill(dp, dp + n, INF); for (int i = 0; i < n; i++) { * lower_bound(dp, dp + n, a[i]) = a[i]; } printf("%ld\n", lower_bound(dp, dp + n, INF) - dp); ```cpp ってな感じで, ソートされた列aから二分探索で`a_i <= k`となりような最小の`a_i`のポインタを求めることができる. ### 分割数 最適化だけでなく場合の数にも応用. ```cpp const int MAX_N = 1000; const int MAX_M = 1000; int n, m; int M; int dp[MAX_M + 1][MAX_N + 1]; int main(int argc, char const *argv[]) { cin >> n >> m; cin >> M; dp[0][0] = 1; for (int i = 1; i <= m; i++) { for (int j = 0; j <= n; j++) { if (j >= i) { dp[i][j] = dp[i - 1][j] + dp[i][j - i]; } else { dp[i][j] = dp[i - 1][j]; } } } printf("%d\n", dp[m][n] % M); return 0; } ```cpp ### 重複組み合わせ これはめちゃめちゃ難しかった. これも, - 何をメモ化するか - 漸化式が作れるように - 計算量が多くならないように - 1つ前の値を意識する - DPテーブルから漸化式を導き出す みたいなところが大事である. ```cpp const int MAX_N = 1000; int n, m; int a[MAX_N + 1]; int M; int dp[MAX_N + 1][MAX_N + 1]; int main(int argc, char const *argv[]) { cin >> n >> m; for (int i = 0; i < n; i++) { cin >> a[i]; } cin >> M; // 1つも選ばない方法は常に1通り for (int i = 0; i <= n; i++) { dp[i][0] = 1; } for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (j - 1 - a[i] >= 0) { dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j] - dp[i][j - 1 - a[i]] + M) % M; } else { dp[i + 1][j] = (dp[i + 1][j - 1] + dp[i][j]) % M; } } } printf("%d\n", dp[n][m]); return 0; } ```cpp ## 感想 蟻本なかなか重たい. 結構な練習を積まないと身につかない. やっぱり初級編だけ終わらせようかなと思ってきた…

リアルタイム性に厳しいアプリケーションに対する通信遅延を考慮した実装と通信遅延を抑えるための研究 from Takaaki Sawa

前回は, CpawCTF2の1問を解いたが難易度が高かったので, ksnctfをみんなで解くことにした. 今回の課題は2, 3, 5, 6である. write up [2] Easy Cipher EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT. 見るからにシーザ暗号なので, 文字をずらすことを考える. 文字コードはUnicodeに従うとして, 空白の文字コードは32 大文字の文字コードは65~90 小文字の文字コード97~122 である. これを加味して以下のような解読するための関数をpythonでかく. # シーザー暗号の解読 def decrypt(text, rot): decrypt_text = '' for ch in text: # 文字コードに変換 code = ord(ch) if code == 32: # 空白ならそのまま出力 decrypt_text += ch continue if code <= 90: # 小文字 code += rot if code > 90: code = code - 90 + 64 else: # 大文字 code += rot if code > 122: code = code - 122 + 96 # 文字に変換 decrypt_text += chr(code) return decrypt_text text = "EBG KVVV vf n fvzcyr yrggre fhofgvghgvba pvcure gung ercynprf n yrggre jvgu gur yrggre KVVV yrggref nsgre vg va gur nycunorg. EBG KVVV vf na rknzcyr bs gur Pnrfne pvcure, qrirybcrq va napvrag Ebzr. Synt vf SYNTFjmtkOWFNZdjkkNH. Vafreg na haqrefpber vzzrqvngryl nsgre SYNT" for i in range(1, 26): if decrypt(text, i).find("FLAG") != -1: print(decrypt(text, i)) # ROT XIII is a simple letter substitution cipher that replaces a letter with the letter XIII letters after it in the alphabet; ROT XIII is an example of the Caesar cipher9 developed in ancient Rome; Flag is FLAGSwzgxBJSAMqwxxAU; Insert an underscore immediately after FLAG また, ROT13はPythonに実装されているので一瞬で解読できる. ...

はじめに… これをといてみます CTFとはこんな感じでハッキングするゲームである。 目的 ゲーム感覚で楽しみながらセキュリティに強くなる 実際に解いてみよう 今回解くのは以下の問題. CpawCTF2 [2] PRANK Yesterday, someone played a Telenet prank and left this file on my machine. ziiiiiiiiiiiiiip.zipI hope this pcap file will help you. prank.pcap 圧縮ファイルとパケットファイルが入っている. 圧縮ファイルを見ると, 0のパスワードを要求される. パケットファイルはTCPとtelnetの通信が行われている. 解法 Telnetは、ネットワークに接続された機器を遠隔操作するために使用するアプリケーション層プロトコル。 オフィスのデスクにいながら、マシンルームにあるサーバ、ルータ等の機器をパソコン上で操作できます。 PCにはtelnetクライアント、ルータなどの機器にはtelnetサーバのサービスが有効であることが前提ですネットワークエンジニアとして らしいので, telnetの中身を覗いたらいろんなコマンドがわかってパスワードがわかるんじゃないかという気持ちでパケットを見る. パケット1つ1つのData部を見ればいいのだが日が暮れるので, TCP streamを見る. 最後に圧縮の操作をしてるんじゃないかと思ってみたらビンゴ. そのパスワードを使って圧縮ファイルを開くとめちゃめちゃいろんなファイルがある. なんかtelnetを眺めているとmvとかの操作でいろんなファイルができている. そこで, 最初にあるflag.txtにフラグがあるんじゃないかと予想して追ってみる. すると flag.txt があるファイルに変換されている. それを見ればビンゴ. 感想 いいぐらいの難易度だった.

背景 自分は現在院生2回生で, 4回生のころから京都のゲーム・Web会社で働いている. 今も細々と続けている中で, Ruby on Railsに触れる機会があったのでその知見を貯めておく. 今回は多対多の関連付けと, その使い方を紹介する. データ構造 このアプリケーションには, userとgroupの定義があって, userは複数のgroupに所属することができて, groupは複数のuserを持つ. よって中間テーブルを用いて多対多の関連付けを定義する. schema.rb ActiveRecord::Schema.define(version: 20_190_219_052_352) do create_table "group_users", options: "ENGINE=InnoDB DEFAULT CHARSET=utf8", force: :cascade do |t| t.bigint "user_id", null: false t.bigint "group_id", null: false t.index ["group_id"], name: "index_group_users_on_group_id" t.index %w[user_id group_id], name: "index_group_users_on_user_id_and_group_id" t.index ["user_id"], name: "index_group_users_on_user_id" end create_table "groups", options: "ENGINE=InnoDB DEFAULT CHARSET=utf8", force: :cascade do |t| t.string "name", null: false t.integer "status", default: 1, null: false end create_table "users", options: "ENGINE=InnoDB DEFAULT CHARSET=utf8", force: :cascade do |t| t.string "name", null: false end end テーブル名をgroup_usersにして中間テーブルを作る. このテーブルをもとにgroupからuser, userからgroupを参照する. ここでindexが3つ貼られているが, 以下のようにして簡単に貼ることができる. create_group_users.rb class CreateGroupUsers < ActiveRecord::Migration[5.2] def change create_table :group_users do |t| t.references :user, null: false, foreign_key: true t.references :group, null: false, foreign_key: true t.timestamps end add_index :group_users, %i[user_id group_id] end end 関連付け 以下がそれぞれのモデルである. ...

背景 自分は現在院生2回生で, 4回生のころから京都のゲーム・Web会社で働いている. 今も細々と続けている中で, Ruby on Railsに触れる機会があったのでその知見を貯めておく. また, Ruby on Railsは型が決まった書き方があるので, 少ない行数に多くの情報を詰め込むことができて, 書き終わった後の見通しがとてもいいと思う. そんなオシャレな書き方を少し紹介したい. 使用するデータのスキーマとモデル 今回紹介するのは, SNSアプリのAPIの中身の一部である. 以下に, 端末の情報を持つdeviceテーブルと, ユーザーの情報をもつuserテーブルを定義する. schema.rb ActiveRecord::Schema.define(version: 20_190_219_052_352) do create_table "devices", options: "ENGINE=InnoDB DEFAULT CHARSET=utf8", force: :cascade do |t| t.bigint "user_id" t.string "uuid" t.integer "user_agent" end create_table "users", options: "ENGINE=InnoDB DEFAULT CHARSET=utf8", force: :cascade do |t| t.string "email", null: false t.string "password_digest", null: false end end ```ruby `user`と`device`の関係は1対多であり, `belongs_to`と`has_many`で関連付けされている. 以下にそれぞれもモデルを示す. user.rb ```ruby class User < ApplicationRecord has_many :devices, dependent: :nullify end Device.rb class Device < ApplicationRecord belongs_to :user, optional: true # deviceとuser_idを紐づける def update_user_id(user) user.devices << self end def shape_response { uuid: uuid } end end オシャレな文法たち 上記データ構造をもとにおしゃれな文法たちを紹介する. ...

背景 エディタもTeXも知らない状況で, LaTeXを使ってレポートを書く際に, 環境構築に苦労する. そこで, Atomを使ってLaTeXがかけるようあ環境を整えた. Atomを使った理由は, Sublimeの人気が落ちていそうな気がしているのと, VSCodeでLaTeXが書きにくかったからである. あとSublimeに飽きてきたのもある. ちょっと重たいのが難点. 方法 TexLiveをインストールする http://mirror.ctan.org/systems/texlive/tlnet/install-tl.zipにアクセスしてインストールする. めちゃめちゃ時間がかかる. 3時間くらいかかっていたかも. 全てデフォルトの設定にしておく. 自動的にPATHを通してくれるが, 動かなかった時はこちらを参照してPATHを確認する. 注意点 他にもいろんなtexに関するソフトがあったが, これが一番主流で新しいそうだと勝手に判断した. Atomをインストールする https://atom.io/にアクセスしてダウンロードする. すでにダウンロードしている場合は, Atomを再起動しないとPATHが反映されないため気をつける. Atomにパッケージをインストールする 以下の3つのパッケージをインストールする. language-latex .texファイルのテキストを色分けしてくれるためのもの pdf-view Atom上でpdfを出力するためのもの. ちょっと拡大縮小がやりにくい. latex compileするためのパッケージ. Settingsから Build on Saveをtrueにしておく. 保存したと同時にcompileされる. Open Result after Successful Buildをtrueにしておく. compileと同時にpdfが開かれる. Openerをpdf-viewにしておく. これでAtom上でpdfが開かれる. AtomでTeXを編集する いろいろインストールしたらとりあえずAtomを再起動するのがいいかも. そして適当な.texファイルを作って, 適当にテキスト編集して保存すると, compileされたものが出現する. 感想 TeXLiveがばり重かったので, もっと軽いものが存在するかもしれない…