読書記録・紹介

もうすぐ初期研修が終わるので、(部分的にも)読んで研修医の万人にオススメと思った本をまとめました。研修の途中で出た新しい本もあるが、概ね1年目から読めると思う。あまりにマニアックな本はカットしたが、まだジャンルに偏りがあるかもしれません。多分…

2021 年振り返り (競プロ視点)

何より,働き始めたことで今までのような時間の使い方ができなくなったのでもう競プロは引退かなと思っていたが,意外にも成果が残せた一年だった. 2月 医師国家試験があった.試験の日に opencup があり,discord にいった記憶 3月 ARC writer をした.結…

expander.py スクリプト 自分用

.zshrc に関数を定義 expand-acl a.cpp みたいなのを書くと expanded-a.cpp ができる expand-acl () { dir_cur=$(pwd) echo "${dir_cur}" dir_acl=path-to-ACL-directory echo "${dir_acl}" dup_file=${dir_acl}/dup-$1 cp $1 ${dup_file} echo "file copied…

テンプレ作成コマンド作成

実は今まで毎回直前に解いた問題のコードを貼ったり,なければテンプレを探しに行ったりのですが (え?),流石に事故りそうなので .zshrc に関数書いた ACL あるので atcoder とそれ以外でテンプレ分けてます prepare_atc 1.cpp するとテンプレが 1.cpp に貼…

2021 年の目標

生存 現在 24 年連続成功していて偉すぎる 医学 国家試験に受かる,仕事に適合 (他の人や,自分の数理的能力などに比べると) 明らかに向いてないので長く続けられるかは不明 やっている間は真面目にやりたいと思っているが,変に真面目な部分もあるので病ま…

Codeforces で International Grandmaster になった

これは記念記事を残しておくと "達成" したくなくてコンテストに出なくなるのが防げるのではないかという気持ちで書かれた記事ですレートが上がると...嬉しい!あっとこも 2700 乗ったので頑張りたいね

ARC104 F - Visibility Sequence の別実装例

ネタバレ注意 解説ではボトムアップ (?) に区間を計算していく方法を紹介していましたが、区間を分割していくという視点でも書くことができ、こちらは意識せずとも 4 乗の解法が作れます。少し数え方の方針が違って、区間 [l,r] の中で、-1を見ているような…

topcoder plugin 導入

パソコンを買い替えたらtopcoderできなくなったのでpluginを入れ直したらめちゃくちゃ苦労した、最近の記事も全然なかったので以前のパソコンでは CodeProcessor, FileEdit, TZTester を入れて使っていました (自動で目的のclassを含んだテンプレ、テストコ…

最小費用流についてのちょっとしたメモ

C++

恥ずかしながら、最小費用流をかなりブラックボックスとして利用していたのだが、今まであまり気付いてなかったことたちが少し整理できたので雑なメモを残しておきます。アルゴリズム自体は各種資料を見てください(怠惰) 双対 LP との関係も知る人ぞ知るジャ…

拡張ユークリッドの互除法の解の範囲

Modint を実装する過程で、拡張ユークリッドで得られる解の範囲について気になったことがあったことを思い出したので (かつ、あまり言及されているのを見たことがなかったので) メモを残しておきます。 の解 とします (そうでないときは gcd で割ったり符号…

ICPC 国内予選 2019 参加記

参加記を書き書き。 (激寒) 5年連続チーム catsatmat で参加して国内9位で予選通過しました。 練習 数回しか3人では練習してなかった (国内予選/アジア地区はかなり埋まっていたのでCF gymなど5時間セット中心) あとはopencupにたまに出た (opencupはcamypap…

全国統一プログラミング王決定戦本戦 G - Greatest Journey

コンテストではFで辺のコストをmin(C[i],C[j])だと勘違いして破滅しました(こちらも解けるらしいのですが) サンプルに書いてあるやん(絶望)と最後の方に気付いて悲しいね。Gの解説がア(上級者向け)なのでメモを残しておきます。まず、どういう移動が最適かを…

ACM-ICPC 2018 Asia Yokohama Regional 参加期

チーム catsatmat で参加して ABCDGK の6完12位でした。アジア地区予選には2016年も参加していて11位だったので、今回の結果は残念なものでした。感想文だけ送るのが面倒なので簡単な参加記も残しておくことにしました。参加記を書き書き。まず、チームは ca…

有理数の探し方

この記事は Competitive Programming (2) Advent Calendar 2018 - Adventar の 12/11 分です(の予定でした)連分数展開・Stern–Brocot tree には様々な面白い構造があり、たまにプログラミングコンテストでも出題される割にあまり知らなかった(かつ日本語の記…

ICPC2018国内予選 H問題

今年もチームcatsatmatで出場しました。4位で通過出来て嬉しかったです。 H問題 前原先生の記事 木上のナップサック問題 でだいたいわかりますが、コードを載せておきます。まず、素直な解法として、dp[v][c] := vの部分木についてコストcで得られるmaxとお…

2016-2017 National Taiwan University World Final Team Selection Contest

結構前のコンテストですが、G問題がシンプルだけどどこか新鮮で面白かったので紹介します Dashboard - 2016-2017 National Taiwan University World Final Team Selection Contest - Codeforces 概要 N個(値段:p_i)の空でない部分集合であってK番目に値段の…

ACM-ICPC 2016 Asia Tsukuba Regional 参加記

チームcatsatmatで出場してABCDEFGの7完11位でした。真面目にUSキーボードの練習をしたので今度はJISがわからなくなって困っています。しかし環境に慣れていなかったのはアレかなあ 自分はgeditで頑張りましたまずコンテストパートについて自分はパソコン操…

SA-IS

Suffix Arrayを空間・時間計算量共に線形で構築出来るというアルゴリズムSA-ISを, 以前ふわっと読んだことはあったけれど真面目に読みなおしました. よく出来過ぎだと思う. 細かいところの理解が間違っていたら教えて下さい. ざっくりとした流れしか書きませ…

JAG夏合宿2016参加記

参加記を書き書き(典型)去年に引き続きJAGの夏合宿に参加してきたので感想を書きます(合宿代安くて有り難すぎる)ICPCアジア地区のチーム(catsatmat)のうち自分だけの参加となりました(悲しい)・day1 合宿初日、コンテストは無し。懇親しなかったのでtozangez…

Atcoder Grand Contest No.2

コンテストを寝過ごしたので解いた. Dの一般的なテク感すき. きれい. Bが面白い感あったEはとりあえずグリッド上を動くゲームなことまではわかったけどあんま考えてない. Fの方針が解説と少し違ったので書いておこう.1~Nの1番左のもの(0は無視)がこの順番に…

Codeforces #296 Div1 D. Fuzzy Search

問題: http://codeforces.com/contest/528/problem/D問題概要は省略します.典型なのかもしれないけど, あんまりこういうの解いたことなかったので面白かった解法:流石にまとめてマッチ箇所を求めるのは大変そうなので, 置く場所は全部試すことにする. そこで…

SRM456 Div1 hard FunctionalEquation

rngさんの問題表を適当に解いていたら聞いたことあるのが出てきたので解いた. 自力で解けて嬉しいというか実質初めて解いたhardがこんな重いのになってしまった(平均的難易度を知らないのでなんとも言えない, hardは怖い)関数方程式という問題名, 一体競技プ…

AOJ2636 Distance Sum

問題: Distance Sum | Aizu Online Judgeブログ書くのめんどくさい. 問題文はとても読みやすいので読んでください. 解説:普通に順番に1からNまで追加してシミュレーションします.まず, i番目を追加した時, i-1番目の時和を最小化する頂点(vとする)とのパス上…

AOJ-ICPC-favorite

好みが普通すぎて面白く無いかもしれません 現在の難易度でsortします・5002333 My friends are small My friends are small | Aizu Online Judge・6002439 Hakone Hakone | Aizu Online Judge2336 Spring Tiles Spring Tiles | Aizu Online Judge2256 Divid…

AOJ2453 Presentation

AOJ

問題: Presentation | Aizu Online Judge概要: 二分木をコピペして作る 解法: 面白かったけど構文解析パート必要ない。あと配列サイズ難しい。重要なのは, 切り貼りすると1番深いところの深さが元のやつより増加するので,最終的に1番深いところ(どれでもいい…

AOJ2338 よくわかる二重魔法

AOJ

問題: Intelligible Double Magic | Aizu Online Judge要約すると、N頂点M辺の無向グラフが与えられるので好きに辺を有向にして(u,v)...uからvにいける ような組を多くせよ、という問題(N lowlinkを使って二重辺連結成分分解し重みつき木にしてdpすれば求め…

AOJ2377 ThreeRooks

AOJ

これで1200+以外は1問以上解いた事になった 概要X*YのマスにK匹のうさぎがいる。互いに攻撃できないように3個のルークを置く場合の数をmod 10^9+7で求めよX,Y 解法 3個同じ所に並んでいる場合 2個並んでいて1個はその範囲にはない 3個が直角に並んでいる場合…

AOJ2603 Time Table

AOJ

バスをm本走らせてn人拾う時の待ち時間の和の最小値を求める問題 とりあえずバス停の場所を時間からひくといつ出発するとちょうどかがわかるので、それをsortしてTiとおくまず何も考えずに愚直なdpの式を立てると dp[i][d] = min{0dp[i][d] = i * t[i] - Si …

AOJ2445 MinimumCostPath

AOJ

MinimumCostPath | Aizu Online Judge まあまあ面白かったn * n (nどう見てもスカスカで、殆ど邪魔されずに行けそうだけど左下と右上付近は混雑するかもしれないので、近くだけbfsして後はdp(経路を最初に通る障害物で区別したりするとなんとかなる)

New Year Contest 2015

rng_58さんのコンテスト。まだあんまり解けてないけど面白かった。 とりあえずコンテスト中に通った分だけA : 愚直にやればよい(vectorは比較出来るらしい) #include <bits/stdc++.h> using namespace std; #define pb push_back int n; vector<int> a,b; int main(){ cin>>n; wh</int></bits/stdc++.h>…