足跡-sokuseki-

りかの日進月歩の記録

herokuのDB(無料)を使って競技プログラミングのアプリケーション開発

自分の用意したDBにコンテスト情報を入れて、情報の閲覧&追加ができるアプリケーションを作った。 →https://hackerrank-jp.herokuapp.com DB周り まずherokuにappを登録する(名前を入力するだけでOK) コマンドラインで$ brew tap heroku/brew && brew inst…

オイラーツアーとセグ木を使ってLCA、パスのクエリに答える

本記事では以下の問題を解きます。 N 頂点の重み付きの無向木が与えられる。 Q 回、ある辺の重みを変更するクエリと、ある2つの頂点の間の距離を求めるクエリが与えられる。 これを、1≤N≤100000, 1≤Q≤100000 で解け。 オイラーツアーは木をDFSしたときの順番…

ブロッコリーのチヂミ

美味しかったけど、前回のチーズリゾットには負けるなあ2種類の野菜チヂミをカフェっぽくしてみた✌️#そすうさ自炊飯#おうちで優勝 pic.twitter.com/O79Xvllfk4— そすうさᕱᕱ(新社会人のすがた) (@wk1080id) 2020年5月10日 右のやつです。 材料(直径6cmのチ…

ブロッコリーとコーンのミルクチーズリゾット

適当に創作したらおいしかったのでメモ。 ブロッコリーの茎を使う最強レシピだと思います。うますぎ。 材料(1人分) 炊いたごはん 約200g 玉ねぎ(みじん切り) 1/4個 ブロッコリーの茎(5mm角) 1房分 コーン 適量 チーズ 適量 オリーブオイル 小さじ1 塩胡…

数学が苦手な人のための期待値DP AtCoder 第一回PAST O - 持久戦

期待値が苦手すぎるので解説を自分が理解できる粒度まで噛み砕いて書きました。 問題文 https://atcoder.jp/contests/past201912-open/tasks/past201912_o 解法 dp[i] := 直前にiを出したときの残りの回数の期待値とすると dp[max_number]は1であり、dp[0](…

topcoder SRM775 参加記

SRMそんなに出ないしすぐ忘れるのでコンテスト参加記を残そうかなあと思ったので(すぐ飽きそう)前回、初回にして爆死はこちら→wk1080id.hatenablog.com まともにACして早く灰色から脱出したいところ。 直前にtopcoderでのコードの書き方を前回の記事を見な…

C++のcomplexで円と線分の交差判定

ある円Cと線分Sの交差判定をします。 定義 円と線分(ここでは直線として管理します)の定義は↓ typedef complex<double> P; struct L : public vector<P> { L(const P &a, const P &b) { push_back(a); push_back(b); } L(){;} }; struct C { P c;double r; C(const P </p></double>…

ICPC2019 アジア地区横浜大会 参加記

11/16~18に行われたICPC2019アジア地区横浜大会に参加しました。 ICPC 2019 Asia Yokohama Regional 〜前日 国内予選が終わってから特に何もしてなくて、何もしないまま当日を迎えるのは怖かったので、チーム練は今年のJAG夏合宿の問題で3セットやりました。…

topcoder SRMに初参加してみた

topcoder登録 難しいと聞いていたんですが、そこまで難しくなかったです topcoderのトップページ右上のcommunityをクリックし、competitive programingの「take me to the coders!」をクリックする ページ中部のLaunch Arena(beta)を選ぶ ログイン画面になる…

ACPC2019(会津大学競技プログラミング合宿2019)参加記

会津大学競技プログラミング合宿2019 : ATND に参加しました。 day0 6時間かけて関西から会津に移動#acpc2019 前泊行くぜ!(ガタッ pic.twitter.com/y2HAEgu5DP— そすうさ (@wk1080id) September 17, 2019 きた!#acpc2019 pic.twitter.com/7bmIBkZj5T— そすう…

ゆるふわ競プロオンサイト #2 参加記

9/14にゆるふわ競技プログラミングオンサイト at FORCIA #2 ゴリラの挑戦状のオンサイトに参加してきました。 コンテスト前 新幹線に乗りながらオンサイト準備slackにも入ったしHackerRankのアカウントも作った これで完璧— そすうさ(素数うさぎ) (@wk1080…

HUPC2019 参加記

北海道大学プログラミング合宿 2019 : ATND に参加しました。参加記FAを目指します。(追記:FAできませんでした) 経緯 ○○大学競技プログラミング合宿といえば、RUPCとACPCがあります。その2つの合宿は、近年は立命館大・会津大・北海道大がコンテストの問…

ICPC2019 国内予選 参加記

noy先輩とHao君と一緒に「UnRated」というチームで出場しました。 3完54位でした。 〜前日 チーム練は3回くらいしたと思います。 HCPC 2019 Virtual Vol.20 - 足跡-sokuseki- ICPC2019模擬国内予選 - 足跡-sokuseki- four-t practice 2019 Vol.12 - 足跡-sok…

four-t practice 2019 Vol.12

https://onlinejudge.u-aizu.ac.jp/beta/room.html#fourt_2019_12/info チームでときましたABCを自分とnoy先輩、D以降をHao君が読むことにする。 Aを読む。やるだけなので実装する。AC。 Bを書いてもらう。入力形式がアでつらそう。その間Cを読む。なんだか…

ICPC2019模擬国内予選

問題文: http://icpc2019.jag-icpc.org/icpc2019/contest/problems_guest_ja.php 順位表: 2019/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni GroupチームUnRatedで出てABC3完75位(有資格者46位)でした。 BCあたり時系列ちょっと怪しいですが…

HCPC 2019 Virtual Vol.20

チームで解きました。 onlinejudge.u-aizu.ac.jpAを自分が、Bをnoy先輩が、CをHao君が担当することになったので、まずAを読む。 やるだけなので書く。ACしたのでBを書いてもらう。その間Dを読む。 Bが通ったのでCを書いてもらう。Dは拡張ダイクストラをすれ…

AOJ2333 僕の友達は小さい

AOJ-ICPC 500 自力AC!!!!My friends are small | Aizu Online Judge 問題概要 人の友達がいて、 番目の友達の重さは である。 この友達を好きな順で選択し、選択した友達の重さの総和が を超えないようにしたとき、選択した友達の組み合わせは何通りある…

AOJ 2642 Dinner

Dinner | Aizu Online Judge AOJ-ICPC 550点…? 問題概要 日間の夕食を食堂か自炊のどちらかで済ませる。 日目に食堂で夕食をとると幸福度が 得られる。 各日に自炊をすると得られる幸福度は、 (自炊をした時点での自炊パワー) である。 自炊パワーは、初期…

GitHubで過去のcommit logのメールアドレスを変更する

GitHubのメールアドレス変更が終わった後の話 基本はこれ:https://help.github.com/en/articles/changing-author-info#変更したい repository の名前を repo とするローカルのその repository の外で git clone --bare https://github.com/user/repo.git cd…

AOJ0310 枠

枠 | Aizu Online Judgeこの高速化テクは典型らしいです。 問題 のグリッドがあり、各マスに数が書かれている。 このグリッドに太さ1マス分の長方形の枠をのせ、枠が覆っているマスの数の総和を最大化する。 ただし、枠は や や のように、中央に穴が空いて…

競プロ合宿の開き方

はじめに 競プロ合宿といえば RUPC (立命館大学競技プログラミング合宿)や ACPC (会津大学競技プログラミング合宿)が有名だと思います。*1 最近、競プロ合宿の需要が増えている気がしていて、たとえば RUPC の参加登録はページ公開後1時間もしないうちに…

競プロで Σi*f(i) を求める問題

競プロで Σi*f(i) ( Σi/f(i) でもよい)を求める問題で、f(i)のとる値が少ない場合、「f(i)の値ごとにiの総和を求めてからf(i)をかけて、それらをすべて足す」というテクを使えばよいという知見を得た。最近解いた問題でいうと、yukicoder No.737 PopCount…

RUPC2019(立命合宿)参加記

3/5(火)から3/7(木)に行われたRUPC2019(立命館大学競技プログラミング合宿2019 : ATND)に参加しました。 Day0 今年は前泊をしていたので、同じく前泊していた北大の人とまぜそばを食べました。北大勢とRUPC前夜祭!! pic.twitter.com/0IhQux5xXf— そすう…

Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

Problem - F1 - Codeforces 問題概要 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成で…

技術室奥プログラミングコンテスト #3 E - デフレゲーム

E - デフレゲーム 問題概要 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。 前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。 解法 期待値の線型性より (サイコロを 回振ったときの目の総和) ( 回目で初めて目が…

競技プログラミング2018総括

2017の総括を書き忘れていたことに最近気付いたので2018の総括を書きます。 今年あったこと 1月 RUPC2018のATNDを公開したら1日くらいで枠がいっぱいになって競プロ人口の増加を感じた 2月 競プロサークルの部長になってしまった… 3月 学内の理系ゼミサーク…

Suffix ArrayのO(NlogN)構築(とおまけでSA-IS)

この記事はCompetitive Programming (1) Advent Calendar 2018 - Adventar の25日目の記事です。 はじめに 競技プログラミングの問題でSuffix Arrayを使う場合、蟻本で紹介されている の構築で間に合う問題がほとんどです。しかし、では定数倍高速化をしない…

ICPC2018 アジア地区横浜大会 参加記

12/8~10に行われたICPC2018アジア地区横浜大会にpriMe.caTというチームで参加しました。 Asia Yokohama Regional Contest 2018 | ACM-ICPC 2018 Asia Yokohama Regional国内予選の様子→ACM-ICPC 2018 国内予選 参加記 - 足跡-sokuseki-ぼくは初めてのアジア…

AOJ2321 Butterfly

Butterfly | Aizu Online Judge 問題概要 個の用事があり、 個目の用事は時間が 区間拘束され、 個目の区間は 時から 時である。また 個目の用事をすると満足度が 得られる。 時間がかぶらないように行う用事を決めるとき、得られる満足度の最大値を求めよ。…

AOJ1336 The Last Ant

The Last Ant | Aizu Online Judge 問題概要 長さ cmのトンネルに蟻が 匹いる。最初、蟻 はトンネルの左端から cmの場所に向き の状態でいる。トンネルは広い場所と狭い場所があり、狭い場所はトンネルの端から1cmおきのところにある。トンネルのある場所で…