Study

研究室の人たちを誘って出場したんですが, 自分は一問も解けずにチームの人らがめっちゃ解いてくれました… 自分が解けなかった問題を先輩の解説やふるつきさんとやっていく気持ちさんのwriteupをみて, 復習します。 [Web] Spy # auth.calc_password_hash(salt, password) adds salt and performs stretching so many times. # You know, it's really secure... isn't it? :-) hashed_password = auth.calc_password_hash(app.SALT, password) if hashed_password != account.password: return render_template("index.html", message="Login failed, try again.", sec="{:.7f}".format(time.perf_counter()-t)) この最後の"{:.7f}".format(time.perf_counter()-t)がみそ。ハッシュ化は時間のかかる処理なので, 実行時間の違いによってDBにレコードが存在するかがわかる。 [Web] Tweetstore limit, ok := r.URL.Query()["limit"] if ok && (limit[0] != "") { sql += " limit " + strings.Split(limit[0], ";")[0] } SQLインジェクションってことはわかっただけで時間が解けた問題。最初UNION ALL句でpg_userを覗けば終わりだと思ったのだが, limit句の後ろでUNION ALL句をつけるにはselect文全体に()が必要らしい… 答えはlimit句内でサブクエリを使う方法。limitのクエリパラメータを(select ascii(substr(usename,1,1)) from pg_user limit 1 offset 1)みたいにすれば表示された件数がusenameの1文字目のasciiコードになる。めちゃCTFっぽい。 ...

硬貨の問題 const int v[6] = {1, 5, 10, 50, 100, 500}; int c[6]; int A; void solve() { int ans = 0; for (int i = 5; i >= 0; --i) { int t = min(A / v[i], c[i]); A -= t * v[i]; ans += t; } printf("%d\n", ans); } ```cpp ### 区間スケジューリング問題 ```cpp const int MAX_N = 100000; int N, s[MAX_N], t[MAX_N]; pair<int, int> itv[MAX_N]; void solve() { for (int i = 0; i < N; ++i) { itv[i].first = t[i]; itv[i].second = s[i]; } sort(itv, itv + N); int ans = 0; int t = 0; for (int i = 0; i < N; ++i) { if (t < itv[i].second) { t = itv[i].first; ans++; } } printf("%d\n", ans); } ```cpp ### Best Cow Line ```cpp int N; char s[100000]; void solve() { cin >> N; for (int i = 0; i < N; ++i) { cin >> s[i]; } int a = 0, b = N - 1; while (a <= b) { //左からと右からを比較 bool left = false; for (int i = 0; a + i <= b; ++i) { if (s[a + i] < s[b - i]) { left = true; break; } else if (s[a + i] > s[b - i]) { left = false; break; } } if (left) { putchar(s[a++]); } else { putchar(s[b--]); } } putchar('\n'); } ```cpp ### Saruman's Army ```cpp int n, r; int x[1010]; void solve() { cin >> n >> r; for (int i = 0; i < n; ++i) { cin >> x[i]; } sort(x, x + n); int i = 0, ans = 0; while (i < n) { int s = x[i++]; while (i < n && x[i] <= s + r) { i++; } int p = x[i - 1]; while (i < n && x[i] <= p + r) { i++; } ans++; } printf("%d\n", ans); } ```cpp ### Fence Repair ```cpp int n, l[50010]; void solve() { cin >> n; for (int i = 0; i < n; ++i) { cin >> l[i]; } LL ans = 0; while (n > 1) { int mii1 = 0, mii2 = 1; if (l[mii1] > l[mii2]) { swap(mii1, mii2); } for (int i = 2; i < n; ++i) { if (l[i] < l[mii1]) { mii2 = mii1; mii1 = i; } else if (l[i] < l[mii2]) { mii2 = i; } } int t = l[mii1] + l[mii2]; ans += t; if (mii1 == n - 1) { swap(mii1, mii2); } l[mii1] = t; l[mii2] = l[n - 1]; n--; } printf("%lld\n", ans); } ```cpp

最近蟻本の初級編をやり直したのだが2-1と2-2の記事がなかったので一応貼り付けとく 部分和問題 bool dfs(int i, int sum) { if (i == n) { return sum == k; } if (dfs(i + 1, sum)) { return true; } if (dfs(i + 1, sum + a[i])) { return true; } return false; } void solve() { if (dfs(0, 0)) { cout << "Yes" << endl; } else { cout << "No" << endl; } } ```cpp ### Lake Counting ```cpp int n, m; char field[110][110]; void dfs(int x, int y) { //置き換える field[x][y] = '.'; for (int dx = -1; dx <= 1; ++dx) { for (int dy = -1; dy <= 1; ++dy) { int nx = x + dx; int ny = y + dy; if (0 <= nx && nx < n && 0 <= ny && ny < m && field[nx][ny] == 'W') { dfs(nx, ny); } } } } void solve() { int res = 0; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (field[i][j] == 'W') { dfs(i, j); res++; } } } printf("%d\n", res); } ```cpp ### 迷路の最短路 ```cpp char maze[MAX_N][MAX_N + 1]; int n, m; int sx, sy; int gx, gy; int d[MAX_N][MAX_N]; //移動４方向ベクトル int dx[4] = {1, 0, -1, 0}; int dy[4] = {0, 1, 0, -1}; // (sx, sy)から(gx, gy)への最短距離を求める // たどり着けないとINF int bfs() { queue<P> que; //全ての点をINFで初期化 for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { d[i][j] = INF; } } //スタート地点をqueに入れて距離を0にする que.push(P(sx, sy)); d[sx][sy] = 0; //キューが空になるまでループ while (que.size()) { //キューの先頭を取り出す P p = que.front(); que.pop(); //ゴールなら終了 if (p.first == gx && p.second == gy) { break; } //移動4方向ループ for (int i = 0; i < 4; ++i) { //移動した後の点を(nx, ny)とする int nx = p.first + dx[i]; int ny = p.second + dy[i]; //移動が可能か //すでに訪れていないか if (0 <= nx && nx < n && 0 <= ny && ny < m && maze[nx][ny] != '#' && d[nx][ny] == INF) { //移動できるならばキューに入れて、距離を代入 que.push(P(nx, ny)); d[nx][ny] = d[p.first][p.second] + 1; } } } return d[gx][gy]; } void solve() { int res = bfs(); printf("%d\n", res); } ```cpp

最近atcoderをやっていることをツイートしたら, めちゃめちゃ頭のいいFさんにお声がけいただいて,つよつよエンジニア学生Aくんも誘って, 競プロの勉強会をすることにしました。 僕はそんなに頭がよくなく理解が遅いかつ実装が遅いのでなかなか恐れ多い勉強会ですが, 頑張って食らいついていこうと思っております。 僕はC++を使っていて, FさんとAくんはPythonを使ってます。 Fさんは来週からC++使うそうです。あっという間に抜かされそうです。 今週はatcoder150を解きました。 D - Semi Common Multiple 長さ N の偶数からなる正の整数列 A = a_1, a_2, …, a_N と、整数 M が与えられます。 任意の k ( 1 ≤ k ≤ N) に対して以下の条件を満たす正の整数 X を A の「半公倍数」と定義します。 X = a_k * (p + 0.5) を満たす負でない整数 p が存在する。 1 以上 M 以下の整数のうちの A の半公倍数の個数を求めてください。 半公倍数の理解に時間がかかった。Aの要素が2で割れる回数が全て等しくなければならないというところがミソ。 E - Change a Little Bit 0, 1からなる長さ N の異なる 2 つの数列 S , T に対し、関数 f (S , T) を以下のように定めます。 S に対し以下の操作を繰り返して T と等しくすることを考える。このとき行う操作のコストの和として考えられる最小の値が f(S , T) である。 S_i を ( 0 から 1 、もしくは 1 から 0 に) 変更する。この操作のコストは、変更の直前に S_j ≠ T_j ( 1 ≤j ≤N) であったような整数 j の個数を D として、 D * C_i である。 0 , 1 からなる長さ N の異なる 2 つの数列の組 (S , T) は 2^N × ( 2^N − 1) 通り考えられます。これらすべてに対する f( S , T) の和を 10^9 + 7 で割った余りを計算してください。 ...

小学生の時にWindowsXPを触った時は, PCというものの中身をいつか全部理解したいなとか思ってました。天才少年です。 そんな夢をかなえるためにOSを作っちゃおうと思い, 作って理解するOS - x86系コンピュータを動かす理論と実装という本に取り組むことにしました。その第3部から実装が始まるのですが, ハマりポイントがたくさんあると思うのでメモしていこうと思います。 docker, vagrantでは動かなかった 詳しいエラーを忘れてしましましたが, display Xに関する部分でエラーが起きてしまいます。 本ではWindows上で実装しているのですが, Macに問題が起きると嫌なので最初仮想環境でやろうと頑張ってましたが, GUIを起動する感じなのでだめでした。解決策になってないのですが諦めてParallels上でWindows10を動かす力技に取り組むことにしました。 文字コードがShift-JIS これはビビった。UTF-8じゃないんや。 iodebugをUnloadする 本の通り進めてもハマるところがここ。Plugin Control > Edit > iodebug > Unloadすればいけた。

vuejsの気になったところ watcherの注意点 wacherの中ではthisを使えない。なるべくcomputedを使う。 watch: { counter() { const vm = this; setTimeout(() => { vm.counter = 0; }, 3000); }, }, v-onディレクティブでの注意点 <!-- method event handler。vue側がいい感じに解釈 --> <button @click="countUp">+1</button> <!-- javascript式 --> <button @click="countUp()">+1</button> v-showの特徴 display: noneのcssがかかる 全てdomに追加されるため初期描画が遅い 要素を削除せずにcssをかけるだけなので描画の切り替えが早い elseがない v-forの特徴 要素の変更が最小限になるようになるべく再利用する 予期しないバグを生む可能性があるので, key属性をつける 仮想ノード createElemetで作られているのは仮想DOMを作るための仮想ノードである。いわゆるDocument Object Modelではなくjavascriptのオブジェクトである。 new Vue({ data: { name: "tak", }, render(createElement) { return createElement("h1", "hello, " + this.name) } }).$mount("#app3"); 仮想DOM DOMの変更を高速に反映するための仕組み。DOMを直接変更するには時間がかかるので, 仮想DOMを変更し前の仮想DOMとの差分を反映して高速に描画する。 Babel JavaScriptのコードを新しい書き方から古い書き方へと変換するツール Webpack webpackは、モジュールを束ねるツールです。 モジュールとは、プログラム内のJavaScriptファイル（以下：jsファイル）やsassファイルなどのことです。webpackを使うことで、複数のjsファイルをひとつのjsファイルにまとめたり、複数のsassファイルをひとつのsassファイルにしたりできます。 ...

Dockerの忘れそうなところをメモ。 Dockerコンテナの実行 docker run pull, create, startを一気にやっちゃう -v /User/takaaki/html:/usr/share/nginx/html:ro バイトマウントする。roとかだとread onlyオプションをつけることができる。 -rm コンテナを停止したときに削除する。 -d バックグランド実行 -e AUTHOR="Takaaki" 環境変数を設定できる。 --link static-site:ss リンク先に通信できるようになる。リンク先の環境変数を追加できる。 docker build イメージを作成。引数にビルドコンテキストを指定。 ビルドコンテキスト…イメージが参照する範囲を指定する。ここで指定した範囲がDocker Hubにpushされるため小さい方がいい。Dockerfileがあるディレクトリの場所でもある。 docker create イメージからコンテナを作成。 -i コンテナの標準入力を取得して双方向に接続. -t コンテナ内にtty(eletypewriter)を割り当てる。 docker cp 文字通りコピー。ホストからコンテナ、コンテナからホストどちらにもできる。 docker add これは文字通りではない。tarを自動で展開したりURLからダウンロードしたりする処理が走る。cpが推奨される。 docker pause, docker unpause docker stop, docker start docker inspect docker rmi イメージを削除。 docker rm コンテナを削除。 docker attach コンテナに接続される。exitで抜けるとstopされる。itで実行していたならばctrl + p, ctrl + qで抜けるとstopされない。 docker exec コンテナ内でコマンドを実行。docker exec -it {image} /bin/bashとしてbashを実行するのによく使われ、exitで抜けてもstopされないため安全であり推奨される。 ...

久しぶりにテーマを更新したらPrism.jsが消えちゃってたのでいれなおしました。参考にしたのは以下のサイトです。 WordPressでPrism.jsを使いコードのシンタックスハイライトを行う方法 https://stupiddog.jp/note/archives/718 Prism.jsのダウンロード https://prismjs.com/download.htmlに行って自分の好みのjsとcssをダウンロードします。僕は以下のように設定しました。 themes=prism-tomorrow&languages=markup+css+clike+javascript+bash+c+cpp+cmake+css-extras+diff+django+git+go+haskell+http+java+javadoc+javadoclike+javastacktrace+jsdoc+js-templates+json+jsonp+json5+julia+kotlin+latex+makefile+markdown+markup-templating+nginx+perl+php+phpdoc+php-extras+python+r+jsx+tsx+ruby+rust+sqf+sql+swift+typescript+vim+yaml&plugins=line-highlight+line-numbers+show-invisibles+autolinker+wpd+custom-class+file-highlight+show-language+jsonp-highlight+highlight-keywords+remove-initial-line-feed+inline-color+previewers+autoloader+keep-markup+command-line+unescaped-markup+normalize-whitespace+data-uri-highlight+toolbar+copy-to-clipboard+download-button+match-braces+diff-highlight+filter-highlight-all+treeview やり過ぎた感あります。 WordPress内に配置 最初適当に配置してヘッダーいじればいいやと思って、Cyberduck繋いでうろちょろしてたんですが, WordPressが提供している方法があるそうです。以下のディレクトリに配置しました /public_html/wp-content/themes/baskerville/js/prism.js /public_html/wp-content/themes/baskerville/prism.css cssはディレクトリがなかったのでbaskerville直下に入れてみました。 ヘッダーで読み込む public_html/wp-content/themes/baskerville/functions.phpのファイルに追記しました。 /* --------------------------------------------------------------------------------------------- For Prism (2020/4/18, Takaaki Sawa) --------------------------------------------------------------------------------------------- */ function my_enqueue_scripts() { $theme_uri = get_template_directory_uri(); wp_enqueue_script( 'prism-js', $theme_uri . '/js/prism.js', array('jquery'), false, true ); wp_enqueue_style( 'prism-css', $theme_uri . '/prism.css'); } add_action( 'wp_enqueue_scripts', 'my_enqueue_scripts' ); 最後に ってな感じです。ブログ書くのってめんどくさいですね。

udemyの教材で正規表現の勉強をした。いままでなんとなく書いていたたが, これからはなんでもかける気がする… 基本的な記号 = 文字または数字を1文字分指定する ^(キャロット) = 直後の文字または数字を指定しない -(ハイフン) = 文字数字の範囲を指定する (バックスラッシュ) = 直後のメタ文字を単なる文字として扱う . (ワイルドカード) = なんでもよし |(パイプ) = 左右のどちらかにマッチするか判定する ()(丸かっこ) = 正規表現をグループ化する 数量詞 繰り返したいパターンの直後におく +(プラス) = 1回以上の繰り返し *(アスタリスク) = 0回以上の繰り返し ?(クエスチョンマーク) = 入力なしか1文字のみ {n} = n回の繰り返し {n, } = n回以上の繰り返し {n, m} = n回以上, m回以下の繰り返し 一致方法 最長一致(デフォルト) 最短一致 ?を数量詞の最後につける 区切り ^ = カバーする範囲の先頭を行頭に指定 $ = カバーする範囲の最後を行末に指定 \b = スペースや改行による単語の区切り 前後につけて単語を見つける \B = \b以外の区切り 単語の中の文字列を見つける 1文字のメタ文字では機能が逆になる ショートコード [0-9] = \d [^0-9] = \D [a-zA-Z0-9_] = \w [^a-zA-Z0-9_] = \W \n = 改行 \t = タブ \r = リターン \f = 改ページ [\n\t\r\f ] = \s [^\n\t\r\f ] = \S 修飾子 g(global) = マッチする結果すべてを抽出 i(case-insensitive) = 大文字と小文字を区別しない m(multiline) = ^と$の挙動を変え, 複数行を対象にする 日本語 ひらがな [ぁ-ん] [\u3041-\u3096] [\x{3041}-\x{3096}] カタカナ [ァ-ヶ] [\u30A1-\u30FA] [\x{30A1}-\x{30FA}] 漢字 [亜-煕] [々〇〻\u3400-\u9FFF\uF900-\uFAFF]|[\uD840-\uD87F][\uDC00-\uDFFF] [々〇〻\x{3400}-\x{9FFF}\x{F900}-\x{FAFF}]|[\x{D840}-\x{D87F}][\x{DC00}-\x{DFFF}] 半角文字以外 [^\x01-\x7E] 応用 フリーダイヤル /0120-((\d{2}-\d{4})|(\d{3}-\d{3}))/ 市街局番 /\d{2, 4}-\d{2, 4}-\d{4}/ 携帯番号 /(090|080|070)-\d{4}-\d{4}/ URL /http[s]?://[\w/%&$#?()=~+-]+/ メールアドレス /[\w-]+@([/w-]+.)+[a-zA-Z]{2, } 感想 とりあえず正規表現が使えそうだったらこのページを参考に書いてみようと思う. ...

今まで学んだことを生かして4問解いてみた. 答えと全然違う実装をしたくないので, 問題を読んで実装の流れを考えたら答えをみるという流れでやってみた. Minimum Scalar Product (2008 Round1A A) 2つのベクトル成分を自由に入れ替えて内積を最小にする問題. 最初は数の正負を考えて, 正の数で絶対値が大きいものには負の数で絶対値が大きいものと積を取るようにみたいなことを考えていたが, シンプルに2つの成分を順と逆順でソートすればよかった. const int MAX_N = 800; typedef long long ll; int n; int v1[MAX_N], v2[MAX_N]; void solve() { sort(v1, v1 + n); sort(v2, v2 + n); ll ans = 0; for (int i = 0; i < n; i++) { ans += (ll)v1[i] * (ll)v2[n - i - 1]; } printf("%lld\n", ans); } ```cpp ### Crazy Rows (2009 Round2 A) 行をバブルソートする問題. 行列が与えられて下三角行列がどうとか難しい話をしているが案外簡単で, 上から順に行を埋めていくことを考える. 動かす行は上の行にすることで, 動かす操作数を最小化する. 実装のポイントとしては`a[i]: i行目の最後に現れる1の位置-1 ~ N-1`を定義することで行列より扱いやすくしている. また, 配列の要素を入れ替える`swap`をうまく使って再帰的な処理を実現している. ```cpp void solve() { int res = 0; // 配列にする for (int i = 0; i < N; i++) { a[i] = -1; for (int j = 0; j < N; j++) { if (M[i][j] == 1) { a[i] = j; } } } for (int i = 0; i < N; i++) { int pos = -1; // i + 1行目に移動する行番号 for (int j = i; j < N; j++) { if (a[j] <= i) { pos = j; break; } } // 実際にスワップ for (int j = pos; j > i; j--) { swap(a[j], a[j - 1]); res++; } } printf("%d\n", res); } ```cpp ### Bribe the Prisoners (2009 Round 1C C) 囚人の問題. 普通に問題として面白かった. アルゴリズムのポイントとしては, 空き部屋の概念と端の概念を一緒にしていかに再帰を実現するか. 実装のポイントとしては, 動的計画法を用いるために`dp[MAX_Q + 1][MAX_Q + 2]: (i, j)を解放するのに必要な金貨`を定義して使うところ. dpがどういう動きをするのかが最初わかりにくいので具体的な例でdpテーブルを埋める作業をしてみる. 幅が小さい順に調べるモチベーションがわかる. ```cpp const int MAX_Q = 100; int P, Q, A[MAX_Q + 2]; // (i, j)を解放するのに必要な金貨 int dp[MAX_Q + 1][MAX_Q + 2]; void solve() { // 簡単のため端をAに追加する A[0] = 0; A[Q + 1] = P + 1; // 初期化 for (int q = 0; q <= Q; q++) { dp[q][q + 1] = 0; } // 幅が小さい順にdpを埋めていく for (int w = 2; w <= Q + 1; w++) { for (int i = 0; i + w <= Q + 1; i++) { int j = i + w; int t = INT_MAX; // 最初に解放する囚人を全て試し最小コストのものを探す for (int k = i + 1; k < j; k++) { t = min(t, dp[i][k] + dp[k][j]); } // 最初の解放では解放する囚人にかかわらずA[j] - A[i] - 2の金貨が必要 dp[i][j] = t + A[j] - A[i] - 2; } } printf("%d\n", dp[0][Q + 1]); } ```cpp ### Millionaire (2008 APAC local onsites C) お金の掛け方が整数に限られていないので, 全探索ができない. ここで, ラウンドが1回しかなかった場合, 金額によって0%, P%, 100%の3つの確率に分けられることに気づく. さらに2ラウンドの場合は, 5つの確率に分けられる. この考えかたを動的計画法で実装する. 実装のポイントとしては, iラウンド目の確率はi-1ラウンド目の確率をもとに計算するので, 2つの配列`prv`と`nxt`を用意してうまく使うところにある. i-1ラウンド目の状態から正解・不正解する場合を確率の独立性を生かして考える. ```cpp typedef long long ll; const int MAX_M = 15; int M, X; double P; double dp[2][(1 << MAX_M) + 1]; void solve() { // n = 2^M int n = 1 << M; double \*prv = dp[0], \*nxt = dp[1]; memset(prv, 0, sizeof(double) * (n + 1)); // 既に100万円持っていれば確率1 prv[n] = 1.0; for (int r = 0; r < M; r++) { for (int i = 0; i <= n; i++) { int jub = min(i, n - i); double t = 0.0; for (int j = 0; j <= jub; j++) { t = max(t, P * prv[i + j] + (1 - P) * prv[i - j]); } nxt[i] = t; } swap(prv, nxt); } // 全勝した場合の金額 / 100万円 int i = (ll)X * n / 1000000; printf("%.6f\n", prv[i]); } ```cpp ### 感想 アルゴリズムに落とし込むところは発想力, そのあとの実装は再帰などをどう実現するかの数学力が必要なのではないかと思った.