algoNote

プログラミング関連

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) C. Optimal Polygon Perimeter

問題 http://codeforces.com/contest/1074/problem/C 解法 マンハッタン距離での周囲の長さなので、選んだ多角形を囲むような(面積最小の)長方形の周囲の長さになります。よって、k=4以上のケースは自明で、n点を囲むような長方形の周長です。 問題はk=3のケ…

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) B. Intersecting Subtrees

問題 http://codeforces.com/contest/1074/problem/B 解法 クエリの上限は5回ですが、2回で求まります。 まず、yの中から適当なラベルを選んで、自分の木での位置を質問します。この頂点をSとして、Sとxの頂点との距離が最小になる点をPとします。Pの位置の…

Lyft Level 5 Challenge 2018 - Final Round (Open Div. 1) A. The Tower is Going Home

問題 http://codeforces.com/contest/1074/problem/A 解法 以下y軸平行な境界線を"縦線"、x軸平行な境界線を"横線"と呼びます。 方針としては、左からいくつの縦線を消すかを固定して、その時に横線をいくつ消す必要があるかを考えます。 (縦線については最…

SRM738 easy - FindThePerfectTriangle

System Testで落ちて0ptでした... 問題概要 三角形の周囲の長さ(perimeter)と面積(area)が与えられる。 周囲の長さ、面積が与えられたものに一致し、各頂点の座標が整数となるような三角形が存在するか判定し、存在するなら頂点の座標を返せ。(複数存在する…

ARC103 E - Tr/ee

構築回だったので、得意な人はハッピー回だったみたい。 個人的にはD問題を誤読して部分点すら取れなかったわけですが、時間を掛けて部分点だけで終了となるよりもEを解くべきなので、Dを捨ててEをやったのは正解だったなと思います。 それにしてもみんな強…

CSA精進記録2

引き続き解いていきます。 Jeans and Shirts https://csacademy.com/contest/archive/task/jeans-and-shirts/ 色ごとの個数を配列に入れておいて,例えばジーンズの色を固定する(cとする)と,シャツの方は[1,c-K],[c+K,1000]の範囲から選ぶことが出来るので…

CSA精進記録

最近,CSAの過去問を埋めるのにハマっています。Solved数順に並べて500人以上くらいのところから始めました。(かなりやるだけ率が高いです。400人くらいから始めれば良かったかも) せっかくなので解いた記録を残しておこうと思います。 Array Removal https:…

みんなのプロコン 2018 C - 駆引取引

コンテスト終了間際にACする解法が思いついたのですが、コンテスト中に通すことが出来ませんでした。 無駄の多い解法(考察)ですが、考えたことを順に書いてみようと思います。 問題 C - 駆引取引 考えたこと が18以下と小さいので商品の集合をビットで管理…

2017年の振り返り

もうすぐ2017年が終わりますね。今年もあっという間でした。 ということで、2017年のことを振り返ってブログに書いておこうと思います。

Codeforces Round #448 (Div. 2) C - Square Subsets

コンテスト中にAC出来ませんでしたが、解けたので好きな問題です(オイ) 問題 codeforces.com 個の要素から成る数列 が与えられます。 要素の積が の形で表せるような部分集合の取り出し方は何通り存在しますか。109 + 7で割った余りを求めてください。 制約

Codeforces Round #433 Div.2D / Div.1B . Jury Meeting

問題文 codeforces.com

セグメントツリーを勉強した

セグメントツリーを勉強したのでメモとしてコードを載せておきます。 区間add - 区間sum 区間update - 区間min 区間add - 区間max Codeforces Round #149 Div2 E.XOR on Segment

SRM 718 Div2

※Hardを解いてからアップしようと思って書いてあった記事が下書きにあったので(Hardはまだ解けていませんが)アップしておきます。 SRM718Div2に参加しました。 Hardが解けなかったり、終了間際にmedのミスに気づいてresubmitしたりと満足いく結果ではありま…

SRM 717 Div2

おそらく全完したのは今回が初めてなので嬉しいです。嬉しいのでブログを書きました。 体感難易度としてmedの方がeasyより簡単な気がしました。(逆でしょ) [easy] NiceTable 問題概要 解法 全探索 別解 ソースコード [medium] LexmaxReplace 問題概要 解法 …

Google Code Jam 2017 Round1B A.Steed 2: Cruise Control

A問題のsmallとlargeだけ通して寝落ちしてました。。 A.Steed 2: Cruise Control 問題概要 Dashboard - Round 1B 2017 - Google Code Jam アニーさんは馬に乗って初め地点 にいて、距離 の地点を目指して直線の道を進む。 道には 頭の馬 がいて、それぞれは…

Codeforces Round #380 Div2 C.Road to Chinema

codeforces.com MathJax.Hub.Config({ tex2jax: { inlineMath: [ ['$','$'], ["\\(","\\)"] ], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 問題概要 $n$台の車についてコスト($c_i$)と燃料の容量($v_i$)が与えられる。 $s$kmを$t$分以内に走ること…

ブログに競プロのレーティングを表示するようにした

AtCoder・Codeforces・TopCoderSRMのレーティングを自動で取得して色付きで表示するスクリプト(javascript)を書きました。 ※追記(2018/09/20) Codeforcesのレートのオレンジの境界が5ヶ月前くらいに変わっていたのですが、更新をサボっていました。今更です…

No.437 cwwゲーム

本番では解けずに解説を見て解きました。 初めてbitDPを使う問題に当たりました。 問題 No.437 cwwゲーム - yukicoder

デバッグ用のマクロ(C++)を工夫する

僕は競プロをやるときにいわゆるprintfデバッグをよくするのですが、その時にマクロが大活躍します。 普段使っているdump(x) #define dump(x) cerr<<#x<<"="<

競プロのプレイスタイル(ソースコード的な意味で)

みなさんはプログラミングコンテストに参加するとき、ソースコードを問題ごとに分けますか?それとも1つのファイルに収めますか? 僕は1つのファイルに収める派です。(深い理由はないのですが、問題毎にファイルを切り替えるのが大変そうだからです) この記…

vagrantの共有フォルダ(Synced Folder)を任意のフォルダに設定する

環境 ホストOS Ubuntu16.04 LTS ゲストOS Ubuntu16.04 LTS vagrant 1.8.5 virtualbox 5.0.24 やりたいこと vagrantのSynced Folderを任意のフォルダに設定したい