[展開する] 上を表示するためのHTMLは次の通りです．
<pre><code class="language-cpp" src="./sample.cpp"></code></pre> 端的には<pre><code>にsrc属性を追加します．
動機 最近はもっぱらラップトップでブログを書くわけですが，画面が小さく1，エディタとプレビューでいっぱいいっぱいになってしまいます．こんな状態でスニペットを含むMarkdownを開いた光景は，JR武蔵小杉駅の南武線ホームを彷彿とさせます．
スニペットを省略できれば全体の見通しが良くなることはもちろん，メンテナンス性の向上(?)も期待されます．どっかの数学者も言ってましたね．「ソースコードは分割せよ」って．
流れ jQueryを読み込む DOMの書き換え Markdown jQueryを読み込む 今回はjQueryを使うことにします．<head>内で読み込み．
<head> <script src="https://ajax.googleapis.com/ajax/libs/jquery/3.3.1/jquery.min.js"></script> <head> DOMの書き換え [展開する] メモ indexと書いたが実際は何を指しているのか不明．なんだろう． Markdown 今回の記事のソースコードはこんな感じ．
--- title: "ブログ記事中のスニペットを外部参照する" date: 2019-03-27T10:00:00+09:00 draft: false topics: ["Programming"] tags: ["jQuery", "HTML"] --- <pre><code class="language-cpp" src="./sample.cpp"></code></pre> 上を表示するためのHTMLは次の通りです． ```html <pre><code class="language-cpp" src="./sample.cpp"></code></pre> ``` 端的には`<pre><code>`に`src`属性を追加します． ## 動機 最近はもっぱらラップトップでブログを書くわけですが，画面が小さく[^1]，エディタとプレビューでいっぱいいっぱいになってしまいます．こんな状態でスニペットを含むMarkdownを開いた光景は，JR武蔵小杉駅の南武線ホームを彷彿とさせます． スニペットを省略できれば全体の見通しが良くなることはもちろん，メンテナンス性の向上(?)も期待されます．どっかの数学者も言ってましたね．「ソースコードは分割せよ」って． ## 流れ - [jQueryを読み込む](#jQueryを読み込む) - [DOMの書き換え](#DOMの書き換え) - [Markdown](#Markdown) ## jQueryを読み込む 今回はjQueryを使うことにします．`<head>`内で読み込み． ```html <head> <script src="https://ajax.
URL https://community.topcoder.com/stat?c=problem_statement&pm=15257
概略 単純無向グラフ $G$ が与えられる．$G$ の橋を含まないような誘導部分グラフのうち，頂点数が最大となるものを求める．
方針 要は，$G$ から橋だけを残したグラフについての最大独立集合問題である．このグラフは明らかに森であるから，木DPが使える．
参考 制約が甘いので橋の検出にはUnionFindを使う．各辺ごとにそれを除いたグラフを構築し，端点の連結性を判定する．
[展開する] 反省 本番では橋の検出までしかできなかった．最大独立集合問題であることにはなんとなく気付いていたが，名前だけが先走った．「NP困難じゃん…」
dp等の初期化も忘れずに．
実行結果 小さいかもしれませんね．すみません．
先に この記事は下記事の内容をパクったと言っても過言ではありません．
もはや写経ですが勉強記録用なので．
動機 時の流れか，我が家では4月から新聞の購読を停止することになりました．非常に残念であります．かくいう私も，新聞をまともに読んでいたのはGコードが消えるか否かのころまでだったと思います．今ではラテ欄とスポーツ欄に隔月で発生する大相撲ぐらいしか読んでいません．あと下世話な週刊誌の広告．
テレビっ子な私はラテ欄の代替を探さなければならないわけですが，Webの番組表の扱いにくさは厳しいものがあります．あの縦長どうにかなりませんか．あの中で見たい番組を探すのは至難の技でしょう．こんな状態なので最低限，自分が興味のある番組くらいは抑えておきたいわけです．スクレイピングはPythonでかじっているので苦労はしないと思うのですが．
流れ 手作業でのURL取得 スクレイピングと整形 Slackへの通知 実行 手作業でのURL取得 番組を探す — Gガイド.テレビ王国で見たい番組のキーワードや芸能人の名前を入力しURLを生成します．ここ一番ダサいです．試しに地上波+金属バット1で検索します．
https://tv.so-net.ne.jp/schedulesBySearch.action?condition.genres[0].parentId=-1&condition.genres[0].childId=-1&stationPlatformId=1&condition.keyword=%E9%87%91%E5%B1%9E%E3%83%90%E3%83%83%E3%83%88&submit=%E6%A4%9C%E7%B4%A2&descriptive=true
このURLとページのソースを元にスクレイピングしていきます．url.jsonには後で使う情報を入れておきます．
url.json [展開する] スクレイピングと整形 TV_scrape.js [展開する] メモ ライブラリはcheerio-httpcliを使う．requireはimportみたいなものだろうか． 関数名の前にasyncを置くと内部でawaitが使える．awaitは待機と例外処理を担う？ index側からfetchにURLを投げる． タグはそのまま，idは#，classは.を付けて表現する． module.exportsは外から呼んだときに使えるようにするもの？ Slackへの通知 slack.js [展開する] メモ 一言一句違わず申し訳ない気持ちになる． やっていることは単純だが一から書くとなると… index.js 通知といったら瓦版なのでチャンネル名は#瓦版です．fetchの前にawaitを入れないとエラーを吐くので気を付けます(1敗)．
[展開する] 実行 node index.js 角界のロボコップ
他にやりたいこと AWSで定期的に実行． Slackのslash-commandを用いた検索条件の追加削除． 今回はここまで．
金属バット (お笑いコンビ) — Wikipedia
[return]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11295
概略 $N$ 日間だけ開くレストランがある．メニューは $M$ 種類あり，その値段は日ごと，メニューごとに異なる．
また，注文するメニューは $7$ 日前と同じでなくてはならない．
1日1回注文をするとして，財布の限り粘るとすると何日間粘ることが出来るか．
方針 サンプル1を見ると，1日だけいる場合と8日いる場合とでは，取る料理の種類が異なることがわかる．なので日を進めるたび，曜日( $7n$ 日前)の料理をおさらいして最小コストを再計算してやるとよい．
7日目まではソートして一番左にくるやつを選ぶ．以降は曜日でかかったコストをいったんbudgetに戻してから再計算．この方法だと貪欲にやってる感が強いので見通しはいい．
[展開する]
これ本家のカテゴリが Recursion なんですけど，どうなんですかね．
URL https://community.topcoder.com/stat?c=problem_statement&pm=11485
概略 ウサギとネコが合わせて $N$ 匹いる．彼らの身長は互いに異なる．
1匹ずつに次の質問をする． 「あなたと同じ種類で，あなたよりも身長が高い動物は何匹いるか？」
彼らの回答が全て正しいものとするとき，それを構成するウサギまたはネコの割り当ては何通りあるか．
補足 {0,0,1,1,2}という回答が得られたとき，ウサギをR，ネコをCとすると，
{R,C,R,C,R} {R,C,R,C,C} {R,C,C,R,R} {R,C,C,R,C} {C,R,R,C,R} {C,R,R,C,C} {C,R,C,R,R} {C,R,C,R,C} の8通りが考えられます．
方針 $2^{40}$ をシミュレートすることはまず無理．
とりあえずanswersをソートしてみる．ウサちゃんもネコちゃんも同じ身長の同種はいないとのことなので，構築可能であるとき，
answers={0,0,1,1,2,2,…,n-1,n-1,n,n+1,n+2,…,m}
になる．逆にこうでないものは全て弾く必要があってこれが結構面倒．実装ではmapで数えてuniqueを取っている．
各数字へのウサギとネコの割り振り方は，
$$ 2(多いほうがウサギかネコの2通り) \times 2^{n} = 2^{n+1} $$
[展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11464
概略 Lucky numberは $4,7$ のみを含む数字である．
JohnとBrusはゲームをする．先ずJohnが長さjLenの区間を選ぶ．そのあとBrusが長さbLenの区間を「Johnが選んだ区間」の中から選ぶ．Brusが選んだ区間に含まれるLucky numberの数がポイントになる．
Johnがスコアを最大化するように，Brusがスコアを最小化するように戦術をとるとき，最終的なスコアはいくらになるか．
方針 範囲が $[1,4747]$ と狭いので全探索できそう．
Johnはスコアが大きくなるように，Brusはスコアが小さくなるように，それぞれ区間をとるというのがわかりにくい．こういう戦略最適化問題の場合，おおむね先手はエスパーなので，まずBrusの行動から考える．
BrusはJohnの決めた区間のうち，スコアが小さくなるよう更に区間を定める．つまり，Johnの各選択に対してスコアは一意に確定することがわかる．こうなると後は単純で，Johnはこの内スコアが最も大きくなる選択をすればいい．数学でやる1文字固定に近い．
どうせラッキーナンバーは少ないので，2進数を列挙する感覚で全部書き出した．春に受講した，ひたすらカルノー図を書く授業を思い出してちょっと鬱になった．
Brusが全範囲の最小値を必死に探す中，Johnはそのうちの最大値を高みの見物で選ぶ．そんな主従関係が目に浮かぶと書きやすいですね．
[展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11434
概略 $1 \sim N$ のスロットが1列に並んでいる．プレイヤーは常にスロット $1$ の中身しか取得することができない．ゲームの目的は，開始時にスロット $M$ にあった中身を取得することである．
スロットには2通りの操作を行うことが出来る．
Divide $N$ を割り切れる素数 $p$ を選びスロットを $[1,\frac{N}{p}],[\frac{N}{p}+1,\frac{2N}{p}],…$ に分割する．この内，目的のスロットを含む部分列のみを保持する．その後，$N←\frac{N}{p}$とし，スロットの番号を $1 \sim \frac{N}{p}$ に振り直す． Shift スロットを左/右にシフトする．シフトするとスロット番号が $-1/+1$ だけ変化する．スロット $0$ は $N$ に，$N+1$ は $1$ に別途移動する． 最低で何回操作をすれば目的を達成できるか．
方針 全然できなかった．調べたら「DivideとShiftの操作は可換」ということがわかって（証明は知らない）そこからはノーヒントで行けた．これで250ptなんだ…
Shiftは数えるだけなので先にDivideを行う．Divideのやり方は高々、2^(素因数の数)だから全列挙してやればいい．あとは各々についてShiftの回数を求める．
のんきに数えてたらTLEしたので，剰余で考える必要があるのだが，これが難しかった．右にShiftする場合の式がよくわからなくて，手元のサンプルと帳尻を合わせるように書いたら通った（最悪）
[展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11096
概略 $n$ が与えられる．$n$ を下1桁が $4$ または $7$ である正の数の和として表すとき，必要な項数の最小はいくつであるか．構成不可能であれば -1 を返す．
方針 $4+10k,7+10k$ を使うことが出来るので，$n$ が項数 $x$ で構成可能であるとき，$n+10k$ も項数 $x$ で構成可能．したがって $n$ の下1桁に注目してやればいい．
例えば下1桁が $3$ になるような項数最小の構成法は $$ 23 = 4 \times 4 + 7 \times 1 $$ である．これを下1桁 $0 \sim 9$ についてやればよく，結果下図が完成した．
4と7で表せる数の下一桁 最小値未満の数は表せない
[展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11154
概略 $N$ 個の街があり各々には名前がついている．2つの街の合併を繰り返し，最終的に1つにすることを考える．
合併前の街の人口を $i,j (i \leq j)$ とする．
$i < j$ のとき 合併後の街の名前は $j$ を継承する． $i = j$ のとき 合併後の街の名前は $i$ または $j$ を継承する． 最終的に街が1つになったとき，その名前として取り得るものは何通りか．
方針 B - Colorful Creatures — AtCoder Grand Contest 011
サンプル5の解釈を説明する．
ソートして人口の昇順に並べても一般性は失われない．また赤は累積和である．
合併のルールから，自分より人口の少ない街は無条件に取り込めるので全て取り込むことにする．これで増えた人口でも1つ右の街が取り込めなければ，その街が生き残ることはない．最終目標は全ての街を合併することなので，右から赤と黒を判定をしていき，図の点線のように断層ができるまでの数が答え．
[展開する]
URL https://community.topcoder.com/stat?c=problem_statement&pm=11397
概略 perfect sequence とは以下の条件をともに満たす数列である．
全要素が非負整数 全要素の積と和が等しい seq の要素をひとつだけ変更して perfect sequence が作れるかを判定する．
方針 $$ S_i = \frac {\sum_k{seq[k]}} {seq[i]} $$ $$ P_i = \frac {\prod_k{seq[k]}} {seq[i]} $$ とすれば，perfect sequenceが作れる時 $$ S_i + x = T_i \times x ⇔ S_i = (T_i - 1) \times x $$ をみたす $x$ が1つ以上の $i$ で存在する．
ただし以下の点に注意．
変更しないのはダメ． seq のサイズが1なら必ず Yes $T_i - 1 = 0$ のとき0除算で危ない．この場合， $S_i = 0$ であればよい。 最悪のケースだと $T_i \approx 10 ^ {9 \times 50}$になってオーバーフローするからこのコードはダメなはず…だけど，普通に通る．