2次元座標系における点 と点 間のマンハッタン距離 は、 と定義されます。簡単に言うと「斜め移動はできず、縦横方向にしか動けない場合の距離」です。 マンハッタン距離上図では、中央の緑マスからのマンハッタン距離を各マスに記しています。また、中央か…

現状です。7回参加でレート 729 です。レート正常化まであと2回（のはず）。 今回はパフォーマンス 928 でした。ABCDを通して、EはWA、FGExは未解答です。Cで1ペナです。 各問題の感想です。 A 差の絶対値が1か9ならOKです。 B HashSetを使えばOKです。 C 普…

現状です。6回参加でレート 694 です。レート正常化まであと3回（のはず）。 今回はパフォーマンス 1120 でした（自己ベスト更新！）。ABCDEを通して、FGExは未解答です。Bで1ペナ、Eで2ペナです。 各問題の感想です。 A なんか色々書いてますが、要するに書…

双方向リストは、片方向リストと比較して「前後両方のノードへのポインタを持つ」という点が特徴です。C# では LinkedList として実装されています。 双方向リスト 双方向リストは、以下のような特徴を持ちます。 先頭・末尾への要素追加が で可能 (そのノー…

今日はアイデアのメモ書きです。 双方向リストは追加・削除が で可能なデータ構造です。しかし、ある要素が含まれているかを探そうとすると の計算量になります。 ただ、ちょっと工夫すればこれも に落とせそうな上、（若干扱えるデータの範囲は狭くなります…

「エラトステネスの篩」は素数列挙に使われる効率的なアルゴリズムです。 「2」から「対象とする最大値」までを「素数候補」とする 残っている数のうち最小値を「素数」と判定して「素数候補」から除外する 2. で素数と判定した倍数を、全て「素数候補」から…

競技プログラミングでよく使われる「セグメント木」というデータ構造があります。 これは、配列データに対して2のべき乗区間ごとに「合計値」「最大値」など注目したい演算を適用しておき、任意の区間に対する演算結果を で取得できるものです。 セグメント…

今日も ABC に参加しようとしていたのですが、開始10分前くらいに AtCoder が落ちてしまい、結局復旧できないまま中止となってしまいました。 【ABC239】22:00~のコンテストが実施できる見込みが立たないため、本日のコンテストは中止させていただきます。申…

現状です。5回参加でレート 596 です。ここから正しいレートが出るのかと思っていましたが、9回参加しないとダメみたいです。 今回はパフォーマンス 900 でした。ABCを通して、DでWA、EFGExは未解答です。 各問題の感想です。 A これA問題か…？と疑う難易度…

現状です。4回参加でレート530です。ここまでが調整期間で、次回からちゃんとしたレートが出るようになるみたいです。 今回はパフォーマンス974でした。ABCDを通して、EFGExは未解答です。 各問題の感想です。 A 恒例のやるだけ問題です。 前回は3分24秒で通…

今日は「競プロ典型 90問」の第12問を解いていました。atcoder.jp問題概要としては、 のマス目があり、1マス赤塗りするか、現在の状態で指定されたマスから「赤マスである箇所」だけを通って指定されたマスへ移動できるか、という判定を行うものです。愚直に…

今日はいまいち調子が悪く、あんまり進捗ありませんでした。 とりあえず、昨日積み残していた競プロ典型90問の問9をACしました。 atcoder.jp この問題は全探索による解法は浮かんで、でも だから無理だなぁ、と思いました。ただ、とりあえず書けることが大事…

計算量で対数時間 というものをよく見かけると思いますが、これが具体的にどの程度のものか、感覚で理解してみます。 まず大前提として、 の底は（計算機科学においては一般に）2 です。何故 2 なのかというと、分割統治法の考え方で問題サイズを半分にする…

現状です。3回参加でとりあえず茶色に乗りました（5回参加するまでは低めのレートが出るようです）。 前回はパフォーマンスが1091でしたが、今回は772でだいぶ落ちてしまいました。というのも、前回まで4問解けていたのですが、今回は3問しか解けなかったで…

今日は「競プロ典型90問」を解いていました。atcoder.jp 第4問で 行列の出力を求められるのですが、初めは（計算量的に自信があったので）かなり適当に考えて、このような処理を書いていました。 for(var i = 0; i < input.H; i++) { for(var j = 0; j < inp…

仕事でコードを書いていて、ふとラムダ式で再帰処理を書きたくなりました。 privateメソッドやローカル関数で定義すれば良いと言えばそうなのですが、その場限りの微妙に複雑な処理なので変数にバインドしたかった感じです。通常のメソッドでは以下のように…

最近は競技プログラミング用のライブラリをチマチマと作っているのですが、競技プログラミングは「問題に対して適用するアルゴリズムを決めて、ライブラリから引っ張れば良いだけ」…というわけでもありません。 その代表例が動的計画法（DP）の問題だと思っ…

今日は AtCoder で使うであろうユーティリティをチマチマと実装していました。ここ一週間ほどユーティリティの充実を続けているのですが、そろそろライブラリが肥大化してきて実際に競技プログラミングで利用するにはやや厳しくなってきました。というのも、…

前回の記録が出ていたので、とりあえず現状から。 5回参加しないと正確なレーティングが出ないようなので暫定ですが、こんな感じです。パフォーマンスは 983 だったので、このくらいのパフォーマンスを出し続けられれば、およそ緑に着地するはずです。 今回…

プライベートで少し作りたいものが出てきて、その中でパスワードを管理する必要があります。これは、以下の要件をセキュアに満たす必要があります。 ローカルにパスワード集合を保存する パスワード集合は同一のマスターパスワードで平文に復号可能 利用者は…

競技プログラミングを C# で始めたのですが、調べていくうちに C++ では一般的に使われているデータ構造で C# に存在しないものがあると知りました。 例えば、優先度付きキューは .NET 6（2021年11月リリース）で初めて実装されました。これ以前のフレームワ…

先日から苦戦していたリモートデスクトップ設定ですが、結局VPNサーバを立てるのは諦めて、普通にリモートデスクトップできるようにしました。ただ、ポート番号そのままは流石に怖いので、最低限のセキュリティとして適当なものに変えておきました。これで様…

Unity(2020.3.6f1) の話です。計算精度が欲しかったので decimal 型で独自の Vector クラスを作成しました。 これで困ったのは、UnityEditor の Inspector で編集できないということです。どうも Unity の Inspector は decimal 型をサポートしていないらし…

昨日から作成している物理シミュレータに衝突処理を追加しました。今のところ組み込まれているのは 万有引力 球同士の衝突（反発係数固定） です。 上の動画はとりあえず反発係数1にしているのですが、反発係数0.7にすると以下のように、条件によっては一体…

昔から時々宇宙に対する興味が強くなる時期が来るのですが、今はそういう時期なので簡単な物理シミュレータを作ってみています。 描画エンジンは Unity で、計算周りは自前で実装しています。既存のクラスよりもう少し精度が欲しかったので、Vector3double …

本日（2021年12月10日）午前、Javaライブラリ「log4j2」に任意コード実行可能な脆弱性が発見されたというニュースが流れました。 【重要】バニラ、Spigot、Paperなど全Minecraftサーバーでログインに関するライブラリ「log4j2」に任意のリモートコードを実行…

久々に「純粋なブログ」というものを始めてみました。 最近は無為に時間を過ごすことも多く、仕事でもプログラムを書くことが中心なので、言語野が劣化してきた感覚があります。その対策や、日々何か成長していきたいという思いから「ただのブログ」を立ち上…