Fragments
隣接行列から最小全域木を隣接リストとして構築するPrim法の実装
概要Prim法を用いて、与えられたグラフの最小全域木（MST）を構築する計算量に影響しないため、最小全域木の重みの合計も同時に計算する優先度付きキューを使わないバリエーションのPrim法入力: グラフの頂点数: グラフの隣接行列。辺がない場…
ABC 454 (A,B,C,D問題)
AtCoder Beginner Contest 454の記録A問題B問題で一意な服の種類の数を計算すると楽C問題をエッジとした有向グラフの、始点ノードからの到達可能ノードの数を答えるBFSで実装DFSの方が楽かもD問題のをに置き換えてとで…
ABC 403 D - Forbidden Difference
問題: https://atcoder.jp/contests/abc403/tasks/abc403_dのうち、で割った剰余が異なる要素は互いに影響しないので、別々に考える例として、剰余が0の場合を考えるどの数字を削除するべきかは、出現個…
ABC 402 C - Dislike Foods
問題: https://atcoder.jp/contests/abc402/tasks/abc402_c食材から、それが含まれる料理全てへのマップをあらかじめ計算して、苦手ではなくなった食材を消していくというアプローチ時間計算量がなので、…
ABC 402 D - Line Crossing
問題: https://atcoder.jp/contests/abc402/tasks/abc402_dから、同じ傾きであれば同じ2点となるように線を平行移動し"正規化"した2点を求め、その個数を今ある直線の個数から除外し加算する、という…
ABC 401 D - Logical Filling
問題: https://atcoder.jp/contests/abc401/tasks/abc401_dまず、の隣のはで確定できるに個のがすでにある場合は、すべてのはで確定できるのの個数が個以下の場合が奇数長でからなる、例えばであり、であ…
ABC 400 D - Takahashi the Wall Breaker
問題: https://atcoder.jp/contests/abc400/tasks/abc400_dの位置から可能な遷移をが道ならば、コスト0でが壁ならば、コスト1でおよびと考えると、ダイクストラ法で解ける ()同じ場所は2回通らない…
ABC 399 D - Switch Seats
問題: https://atcoder.jp/contests/abc399/tasks/abc399_dのの例に注目すると、1つ目の1の右隣の要素(2)を1の2つ目の出現とswapするととなってペアにできることがわかるこのことから、ある数…
exiftoolでGPS情報を削除する
CLIから画像のEXIFを操作できるツールとしてexiftoolがあるexiftoolで画像のGPS情報を削除するには、を指定するカレントディレクトリの全てのJPEGファイルのGPS情報を削除する例:なお、ファイルのバックアップがとして保存…
Dockerのボリュームをtarにアーカイブする
ボリュームの中身をマウントし、中身をで固めて保存するコマンドの例ボリューム名はで確認するtar.gzにアーカイブする場合バックアップカレントディレクトリにとして作成される復元ボリュームの中を空にしたのち、アーカイブを展開tar.zstにアー…
ローカルサーバー監視ツールBeszelを入れてみる
サーバーが増えてきたので、ふとサーバー監視ツールを試したくなったBeszelというのが新しくて良さそう、ということでインストール基本的にはGetting Startedに従えば良い。Docker Composeで入れてみる指示通りを作る。た…
Gitで空のInitial commitを作る
まだフォルダ構成とかは決まってないけど、とりあえずリポジトリを初期化したい場合があるはデフォルトでは変更がない場合はコミットを作らせてくれない:オプションを使うと、この挙動を回避して空のInitial commitを作ることができる:はIn…
GCCの--coverageはデフォルトではスレッドセーフではない
環境GitHub Actions上のGCC 13.3.0C++でスレッドを使うテストを書いたところ、CIで以下のエラーが出た:カバレッジの値が負の値になっており、GCOVがレポートのパースに失敗しているカバレッジは次のオプションで取得してい…
Goのgoroutineはノンブロッキング
Goには、JavaScriptやC#などのような/の概念が存在しない。つまり、コードは同期的に書かれている。それでは、どのようにノンブロッキングIOを実現しているのか？Goはこの問題をgoroutineという名の軽量スレッドで解決している実…
C99の複合リテラルはC++にはない
C++を書いていたら、GitHub Copilotが関数の引数としてという見慣れない構文を提案してきたはC99の複合リテラル（Compound literal）というやつらしい。複合リテラルはlvalueなので、でアドレスを取れるCompo…
Rustの構造体メンバは、メモリ上で順番に並ぶとは限らない
Rustコンパイラは、構造体のメンバをメモリ効率が良いように自動で並び替える例:もしこのような並び替えが好ましくない場合、構造体にを付与することで並び替えを防げる:
git cleanの使い方
gitでtrackされていないファイルやignoreされているファイルを一括で消すコマンドでdry run、削除対象のファイルを確認することができるtrackされていないファイルを全て消す強制的に消す（force）ディレクトリも消すigno…
Node.jsのC++アドオンを作る【CMake.js】
Node-APIを使ってC/C++のアドオンを作る、つまり、JavaScriptからC/C++を呼び出したい場合、以下の2つのいずれかのビルドシステムを用いる（少なくとも、公式ドキュメントを読む限りはこの2つ）node-gypCMake.j…
QuickJS-NGでC++からJavaScriptを実行する
Fabrice Bellard氏らによる軽量JavaScriptエンジンQuickJSのコミュニティフォークがQuickJS-NGいずれもC言語で書かれているES2023など新しめの言語仕様も網羅されているQuickJS-NGではCMake…
Java 25で追加されたjava.lang.IOクラス
Java 25で、という手軽に使えるIOユーティリティが追加されているIO (Java SE 25 & JDK 25)主に、3つの操作が提供されている:: をに出力: をに出力、改行あり: 文字列をプロンプトとして表示し、から一行入力jsh…
ABC342 D - Square Pair
問題: https://atcoder.jp/contests/abc342/tasks/abc342_dが平方数であるということは、素因数分解してのように書ける、ということは素数つまり、指数を2の倍数に揃えれば良いつまり、「を素因数分解し…
ABC 344 D - String Bags
問題: https://atcoder.jp/contests/abc344/tasks/abc344_dステップ目までで、文字列を構築するコスト、ただしできないならと定義各について、、それ以外はで初期化が以上であるとき、に追加コストなしで…
CMakeでlibpngにリンクする
環境MacBook Pro (2021)macOS 15.1.1CMake 3.31.5CMakeでを使ってlibpngをリンクする試みlibpngはzlibに依存しているため、まずはzlibを持ってくる必要がある最新リリースはv1.3.1…
ExcelでBOMなしUTF-8のCSVファイルを開くと文字化けする
環境macOS 15.1.1Microsoft® Excel for Mac 16.103.2 (25112216)Microsoft Excelで、UTF-8 (BOMなし)で保存されたCSVファイルを開くと文字化けする文字化けを防ぐには…
ABC 404 C - Cycle Graph?
問題: https://atcoder.jp/contests/abc404/tasks/abc404_cはサイクルグラフ は連結かつ全ての頂点の次数が2 が成り立つ、という仮説で書いたらあってたっぽい提出: https://atcoder…
ABC 398 D - Bonfire
問題: https://atcoder.jp/contests/abc398/tasks/abc398_d煙の位置を移動させるのではなくて、焚き火と高橋君が移動していると考える煙の位置はで記録すればOKだが、の場合はハッシュ関数が必要提出:…
ABC 396 D - Minimum XOR Path
問題: https://atcoder.jp/contests/abc396/tasks/abc396_dが小さいので、で経路を列挙すれば間に合うで中継地点の順番を列挙して、で最初から何個の中継地点を通るかを列挙する実装にしたでもDFSの方…
ABC 408 C - Not All Covered
問題: https://atcoder.jp/contests/abc408/tasks/abc408_cimos法でできることはすぐわかったけど、書き方を忘れてたというか、Cでもimos法出るんだ提出: https://atcoder.j…
ABC 406 C - ~
AtCoder最近やってなかったので過去問練習問題: https://atcoder.jp/contests/abc406/tasks/abc406_cこの問題のチルダ型とは、上がって下がって上がる部分列のこと単調増加する部分列、単調減少す…