matthew as a q.

競技プログラミングメイン

std::setの使い方

問題 AGC 022 A問題。 A - Diverse Word 解法のポイントとsetの使いどころ 文字数が26文字のとき、後ろから見て最長の昇順文字列(接尾文字列)を取得し、最長の昇順文字列の1つ手前の文字より大きい中で接尾文字列に含まれる一番小さな文字を最後に付け足し…

clang-format on WSL on Windows with Visual Studio Code

この記事が助けになるかもしれない人 Windows 10上のVisual Studio CodeからWSLのUbuntuにremote接続して開発を行っている人が、clang formatを適用する。 適用方法 WSL上のUbuntuにclang-formatをインストールする必要がある。 sudo apt-get update sudo ap…

0 1 BFS

0 1 BFSとは betrue12.hateblo.jp 例題 D - Wizard in Maze 実装例 隣への移動はコスト0、ワープでの移動はコスト1なので、 隣への移動時はdequeの前に、ワープでの移動時はdequeの後に詰めることで、コストの低いところから探索を行うことができる。 ただし…

要復習リスト

ABC C - Repsept

Atcoder Beginner Contest 174(バチャ)

C問題 大きな数を扱うときに文字列として扱う以外の方法を学んだのでメモ。 等比数列として考える 今回のC問題のi番目は、 と書ける。 大きな数の除算 ABC174 C問題のEditorial より引用。 https://img.atcoder.jp/abc174/editorial.pdf などといった巨大な…

ダイクストラ法と経路復元

蟻本ベースにサンプルコードをきちんと書いたので、メモを残しておきます。 コード struct edge { public: int to; int cost; }; // O(|E|(log|V|)) void dijkstra(std::vector<int> &dist, const std::vector<std::vector<edge>> &graph, int s) { typedef std::pair<int, int> P; std::prior</int,></std::vector<edge></int>…

競技プログラミングtips(特定範囲の条件満たす要素数え上げ)

想定問題形式 「L以上、R以下の整数値のうち、条件にあてはまるものを数えよ。」というような形式を想定。 取り組み方 1..L-1、1...Rと分けて、(1..Rで条件を満たす数) - (1..L-1で条件を満たす数) として計算

ABC161

結果 3完(A, B, C)でした。 #ABC161, A:swap、B:整数除算にハマり4WA。次は移項して掛け算でやる。C: n,k大小で場合分けしたけど必要なかった。D:lunlun数の木を作ってBFS。 E、F:間に合わず— mato (@mmatthew_43) April 4, 2020 Dは方針合ってるも、間に合…

Offline端末にVisual Studio Code+MinGWでC++開発環境を構築する

これは何? インターネットに繋がらない環境に MinGWのgccコンパイラを使って Visual Studio Codeで C++の開発環境 を作るときに、時間のかかった箇所のメモ。 全体の流れ 以下の公式ガイドに従う。 code.visualstudio.com Visual Studio CodeのC++プラグイ…

field型の幅優先探索(ABC151 D Maze Master)

問題 D - Maze Master 提出 Submission #9662770 - AtCoder Beginner Contest 151 方針 各マス起点で幅優先探索し、たどれる箇所の距離のmaxを保存。 field型の幅優先探索をきちんと意識して初めて書いた気がする!

1月前半に学んだ英語フレーズ

練習方針 Listen to more English. とにかくまずは聞きましょう。聞いて知らない単語をメモしてリスト化しておきましょう。 speak and practice to use. リスト化した表現は、次の練習の際に使えるようにしてみよう。 Read aloud. 読むときは大きな声で言う…

Atcoder Beginner Contest 151参加記

結果 A B C D E F A - Next Alphabet B - Achieve the Goal C - Welcome to AtCoder D - Maze Master E - Max-Min Sums F - Enclose All AC AC AC - - - ■ ■ ■ - - - D maze master 全探索して最長となる距離を保存すれば良さそうとまでは思えたのですが、 …

doubleが整数かどうかの判定

doubleが整数になるかの比較方法を知らなかったのでメモ。 方法 以下のラムダ式を用意して使用。 auto isInteger = [](double x) -> bool { return std::floor(x) == x; }; 問題文 ABC133 B Good Distance 計算した距離が整数になる点の組み合わせを数える。…

Atcoder Beginner Contest 148

A やるだけ。 Submission #9243751 - AtCoder Beginner Contest 148 B std::string組み合わせシミュレーション。 Submission #9244107 - AtCoder Beginner Contest 148 C LCM. Submission #9244171 - AtCoder Beginner Contest 148 D LISを作る。LISの先頭が…

12月後半に学んだ英語フレーズ

12/18 理解度が異なると、物事進めづらいので。。 If the UNDERSTANDING of the people in the meeting are different from each other, we could not proceed effectively. 同じページを見て進めていく、という表現で、同じ認識で進めることを表している。 …

12月前半に学んだ英語フレーズ

12/1 紅葉に感動した I was impressed with autumn leaves. タスクを振られたら、より早めに手をつけるべき。 When you are assigned with some tasks, you should begin them at an earlier time. 期限までに終わらせてもらえますか? Can you finish your …

LAN内端末のIPを調べる

環境 接続元:Windows 10 Pro(1909) 接続先:Windows 10 Pro(1909) リモートデスクトップ 接続するにはLAN内のプライベートIPアドレスが必要。 そこでLAN内(192.168.1.0/24)のIPアドレスすべてにpingを飛ばし、返答が返ってきた端末のIPアドレス一覧を表示す…

根から辿る全探索

木上の累積和で、根から足しこむところで詰まっていたので、そこ含めてメモとして記録。 memo void dfs(int thisNode, int parent, vector<vector<int>>& graph, vector<int>& c) { for (auto nextNode : graph[thisNode]) { if (nextNode == parent) { continue; } c[nextNod</int></vector<int>…

bit全探索

memo for (size_t bit = 0; bit < (1 << (s.size() - 1)); bit++) { for (size_t i = 0; i < s.size() - 1; i++) { if (bit & (1 << i)) { // bitが立っているとき // 数字の区切りでaccumulate等 } else { // bitが立っていない場合 // 位を挙げて今回の計…

フェルマーの小定理を用いたmod p上の逆元

フェルマーの小定理 が互いに素な自然数のとき、 上、の逆元は 参考 フェルマーの小定理の証明と例題 | 高校数学の美しい物語 分数と小数から広がる整数の世界 ~フェルマーの小定理からアルチン予想まで~ (数学への招待)作者: 中島匠一出版社/メーカー: 技術…

Atcoder Beginner contest 130 E - Common Subsequence

問題概要 N個の整数列を与えられて、その部分列のうち、Kを超える部分列を数え上げる。 解法 しゃくとり法。 しゃくとり法解説記事 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita しゃくとり法のテンプレ書き方の参考 尺取りは書き方…

Atcoder Beginner Contest 131参加記

問題 A - Security 連続してたらBad。 Submission #6056333 - AtCoder Beginner Contest 131 B - Bite Eating 味の絶対値の小さいものを食べる。 Submission #6060148 - AtCoder Beginner Contest 131 C - Anti-Division all - (Cの倍数の数 + Dの倍数の数 -…

Diverta Programming Contest 2参加記

問題総評 A N-K Submission #5920234 - diverta 2019 Programming Contest 2 B 一番多く存在する差の組み合わせの数を数えて、全体から引く。 Submission #5930048 - diverta 2019 Programming Contest 2 C 解説と他の方の提出を見ての理解。 ans = max - mi…

計算量削減メモ

# 事前処理で定数時間化 ## 題材 https://atcoder.jp/contests/abc129/tasks/abc129_d ## 具体的には なりでは、各地点に対して上下左右の探索が必要で、O(HW(H+W))となり、H、Wが2000以下の正の整数のため、時間内に計算間に合わず。 各地点での上下左右の…

DateTime.ToShortDateStringの注意点

C#

## DateTime.ToShortDateStringとは DateTime型を、実行端末のデフォルトのCultureInfoに沿ってstring型に変換するメソッド。 ## 使い方 > DateTime today = DateTime.Now; > string todayStr = today.ToShortDateString(); ## 注意点 CultureInfo依存なので…

配列の初期化

C#

forを使わない初期化方法 int nrange = Enumerable.Repeat(1, n + 1).ToArray(); int narray = (new int[n]).Select(e => 1).ToArray();

Atcoder Beginner Contest 121

atcoder.jp A. White Cells 残りは長方形やるだけ。 B. Can you solve this? 各行計算、判定。 C. Energy Drink Collector 価格の低いほうから買えるだけ買う。 D. XOR World XOR演算の性質に気付ければO(1)。 詳しくはeditorial参照。 ポイントは以下。 同…

仮想通貨とふるさと納税のe-taxを使った確定申告(2019年版)

これは何? 仮想通貨とふるさと納税の確定申告を行ったので、来年の自分に向けての概要メモ。 何をしたら納税完了か 以下を全て完了したら終了 確定申告をe-taxで提出(納める所属税額を確定) 所得税を納付(国への税金) 住民税を納付(市区町村への税金。確定…

東京都不動産取引価格情報[EDA]

# これは何? 国土交通省提供の不動産取引価格情報(H17~直近)を眺めたメモ。 # データ 土地総合情報システム# df.shape (3803, 30) # df.columns Index(['No', '種類', '地域', '市区町村コード', '都道府県名', '市区町村名', '地区名', '最寄駅:名称', '…

read_csvで日本語csvを読み込む(python3.5.3)

# 背景 pandasで日本語データを扱わないといけなくなったが、ナチュラルにread_csvを実行するだけでは読み込めない。# 解決策 read_csvでengine='python'オプションを渡す import pandas as pd df = pd.read_csv(target_path, engine='python')# 参考リンクg…