日記

のみろぐ

主に競プロ日記です

競技プログラミング

AtCoderにおける言語ごとの提出率

まえがき 調査結果 C++で競技プログラミングをすることの利点 結論 提出言語ランキング詳細 調査について 調査したもの 使用したもの 調査方法 ソースコード まえがき C++は競技プログラミングの役に立つ Advent Calendar 2018の7日目を担当しました!! AtC…

AtCoder Virtual Contest Tweet ButtonっていうChrome拡張作ったよ!!

AtCoder Virtual Contest Tweet Button AtCoder Virtual Contest Tweet Button まえがき 作ったものについて 概要 作った動機 開発ログ 拡張機能の大枠を作る HTMLからコンテスト情報を取得する アイコンのクリックを検知する ツイート画面を開く HTMLから取…

LeetCode110

LeetCode110 A問題「Reorder Log Files」 問題概要 考察 解法 コード 感想 B問題「Range Sum of BST」 問題概要 考察 コード 改善 知見 C問題「Minimum Area Rectangle」 問題概要 考察 コンテスト中の考察 理想の考察 コード 要点 情報の重複を避ける setの…

Future Contestを無料運用にした

まえがき 使ってるもの クラウド 言語 アーキテクチャ やったことを簡潔に お金がやばくなる 無料運用する方法をググってみる 自分でapp.yamlを書いてみる お金が減り続ける お金が減り続ける2 GAEの動作環境 スタンダード環境を試してみる Future Contestを…

初めてWebサイトを作ってみた

まえがき 成果物 開発に至った経緯 機能とか 処理の流れ 言語 クラウド 対象サイト コンテスト情報の収集 使ったツールまとめ 情報取得方法まとめ Codeforces CS Academy AtCoder yukicoder サーバー 見た目 favicon その他 時間の表示がおかしい エラー処理…

DPL_1_C「ナップザック問題」

DPL_1_C「ナップザック問題」 考察 DPに使いそうな値を考える 今回は01ナップザックみたいに何個目まで選んだかという情報は必要無い 価値と重さが分ればいいかなーってなる 価値と重さだけわかれば良いので1次元のDPでできそう 同じ種類の荷物は何個でも使…

DPL_1_B「0-1 ナップザック問題」

DPL_1_B「0-1 ナップザック問題」 DPL_1_B「0-1 ナップザック問題」 解法 漸化式 部分的に見る コード 要点 解法 上図のようなDPテーブルを用意する テーブルをすべて$0$で初期化する(グローバルに宣言していれば初期化する必要は無い) 漸化式を立て、それを…

ABC040-C「柱柱柱柱柱」

ABC040-C「柱柱柱柱柱」 解法 「$dp[i]$:$i$手目の最小コスト」というDPテーブルを作る 後はDPする コード 集めるDP #include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = 1e15; int N; ll a[111111]; ll dp[111111]; // dp[i]: i+1手目の</bits/stdc++.h>…

ABC099-C「Strange Bank」

ABC099-C「Strange Bank 」 ABC099-C「Strange Bank 」 考察 コンテスト中の考察 理想の考察 コード 要点 感想 考察 コンテスト中の考察 価値の大きい金から使っていく貪欲で解けそう 貪欲だと上手くいかない... もしかしたらDPでは?→DP書けない 理想の考察…

DPログ

解いたDPの解説記事を列挙していきます 逐次更新 DP問題投げてくれると嬉しい 1次元DP DPL_1_A「コイン問題」 ABC099-C「Strange Bank」 ABC040-C「柱柱柱柱柱」 DPL_1_C「ナップザック問題」(2次元でもできるらしいがよく分からん) 2次元DP DPL_1_B「0-1 ナ…

DPL_1_A「コイン問題」

DPL_1_A「コイン問題」 DPL_1_A「コイン問題」 考察 解法 漸化式 おまけ コード 要点 類題 感想 考察 価値の高いコインから順番に使う貪欲法で解けるのでは? でも、ちょうど$n$円払いたいので、貪欲ではうまくいかない時がある。 例えば、$n=10, m=4, c = {…

ABC045-D「すぬけ君の塗り絵 」

ABC045-D「すぬけ君の塗り絵 / Snuke's Coloring 」 ABC045-D「すぬけ君の塗り絵 / Snuke's Coloring 」 考察 細かいこと 解法 コード 差分の列挙について 要点 感想 考察 愚直に考えると、$HW$の盤面を用意してすべての座標に対し$9 \times 9$を全探索する…

AtCoderで水色になるまでにしたこと

まえがき 書きたいことはたくさんあるけど水色になるまでにやったことだけに絞って書きました。 必要なアルゴリズムなどについては他の方が書いているので省きました。(追記) 以下に書いたことは個人の感想です。まさかり担いでる人は退場するか地面に置く…

RUPC2018参加記

まえがき 実力的に緑コーダーが参加して良いのかわからなかったけど、説明欄に「だれでも参加おっけー(意訳)」と書いてあったので参加した。 いろいろあって書くのが遅れたので記憶があいまい。やっぱすぐ書くべきだね。うん。 1日目 コンテスト前 自己紹…