概要 最近F - Construct HighwayやA - Reachable Townsが立て続けに解けなくて悲しかったので、お互いに共通する「UnionFindの各連結成分が変数を持っていて、mergeするときにその変数を使ってなんかする」みたいな問題をすっとかけるようにしたいなと思い、…
C++における割り算問題はなかなか難しく、どのように実装するか悩ましい。時々競プロで出題されるが、負の整数に対して切り上げ、切り捨てを含む割り算の記事がないような気がしたので、せっかくなのでここにまとめておく。 結論 のとき、 (切り捨て), (切り…
将来のコーディング試験に備えて。そのうちfenwick treeとかほかのも書くかもしれない。(typedef long long ll;とかrepマクロの定義は省略する) あくまで自分のための備忘録なので、初めて組む人はこっち見た方がいいと思う Union-Find Tree を理解する!素…
AtCoderの気になった問題やコードの間違いなどをどこかに書きつけたいと思っていて、Google SpreadsheetやGoogle Documentを使ってみたが、どうもなんか違うなーという気がしたのでこっちに一言だけコメントを付けてまとめてみることにした。markdown形式で…
ファイル名の交換コマンド: mvswap - シリコンの谷のゾンビ ほぼこの方の通りに設定したが、Ubuntu(WSL)ではmktempが使えなかったのと、その他もろもろエラーを吐かれたので以下のようにコードを変更した: #!/bin/sh TMPNAME=".tmp-hoge-fuga-piyo" if [ $#…
タイトル通り。例えば、vector型のコンテナのイテレータに対する引き算は次のようになる。 vector<int> b(10); cout << b.at(3) - b.at(1) << endl; // 2 これを使って、例えばlower_boundの返り値のイテレータを引き算し、下限と上限の間に存在する要素数を計算</int>…
いままで全然論理演算子を使っていなかったのでここで不意打ちを食らって全然通らなくて悩んでいたのでまとめてみた。 基本的に、 代入系 < 論理OR, AND < ビットOR, NOT, AND < 関係演算子 < ビットシフト < その他のやつ(四則演算てきな) と覚えてお…
D - Lucky PIN 解説のおまけ問題にもあるが,100 x N程度の計算量で解くようなコードを生成できた…と思う。 が仮にというような数列だった場合,暗証番号の一桁目を全探索していくときに,2回目のについては見る必要がない。なぜなら,一回目のを一桁目とす…
例えばの桁数をループを回しながら数えていくとき(かぞえた桁数は配列digitsにしまうものとする)。 #define _USE_MATH_DEFINES #include "bits/stdc++.h" using namespace std; #define rep(i, n) for (ll i = 0; i < (ll)(n); i++) typedef long long ll; i…
昨日受けたので復習。 問題A, B A - Square Inequality B - Intersection についてはすぐ実装が終わった。AOJのITP1をすべてこなしたおかげで力がついたかもしれない。せっかくなのでB問題に使ったmax_elementとmin_elementの使い方を復習しておく。 vector<int> </int>…
vector<long long>型やvector<double>型の配列 x の総和を求めるときに, std::accumulate(x.begin(), x.end(), 0); とすると誤差がおおきくなったり,オーバーフローしたりする。std::accumulateの仕様として第三引数の型で値が帰ってくるらしい。なので正しくはそれぞれ std::</double></long>…
タイトルの通り。僕のAndroid端末のChromeの環境だけなのかもしれないが、MathjaxのRendererがHTML-CSSでは表示がずれてしまい、数式と文章と覆い被さってしまう。だから、端末やブラウザごとにMathjaxのRendererを変更することにした。 まず、はてなブログ…
いきなり数学でも音楽でも音ゲーでもないが、一応備忘録なので。今のブログのデザインはBordeauxをつかっているのだが、ブログタイトルもブログの説明文(タイトル下)も、更にその下の記事のタイトルも左詰まりではなんだか格好わるい。 そこで、なんとかブ…