olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

AtCoderで灰色になりすますまでにやったこと

AtCoderで灰色になりすました!!!!!!!!!!!!!!! 沢山コンテストに参加してようやく灰色になりすませたのでとてもうれしいです! これから競技プログラミングを頑張っていきたいです! 参考にしたツイート AtCoder青になるまでにやったこと・Chr…

チーム練(2016バンコク)

寝坊した。完 Lが自明っぽいらしいので聞くと、自明っぽい。ちょっと細かい条件とかいろいろあってやだなあって言いながら書くと通る。(0:14) Bも自明っぽいらしいので聞くと、TLEしないか心配になるが、満点が同じものをまとめてやると良さそうなので書く。…

CivilizationV紹介

この記事は プログラマーのオススメのゲームの話をする Advent Calendar 2019 - Adventar の5日目の記事です。 昨日の記事は "お手軽オートバトル" ハースストーン バトルグラウンドの話 & 「激闘!ドラゴン大決戦」まで1週間 - fal_rnd_log 明日の記事は is…

チーム練(2018ソウル)

最初は英語が読めないおるふぇがテンプレを書くことにする。(本番だと多分テンプレ5行だけど(ア)(インフラっぽいこと(?)も出来たいね)) Dがやるだけなので書く。(0:11) ふぇりんがLがフローっぽいと言っていたので聞いてみたら貪欲でできることが分かるので…

チーム練(2018ジャカルタ)

でぃぶが一瞬でIを通す。 ふぇりんがからAの概要を聞いた僕が一瞬って言う。WA でぃぶが一瞬でLを通す。 このへんで、僕が1問読む間にチームメイトは2~3問読んでいることに気が付く。 ふぇりんが昨日K解いたって言ってたので任せる。無限時間かかってたけど…

ICPC 2019 Asia Yokohama Regional 不参加記

国内予選(95位)落ちたので参加していませんでした。 学内1位だとしても落ちてるの、弱すぎない?(俺は橙コーダーやぞ)(当時は黄コーダー(俺は黄コーダーやぞ)) ふぇりんとオープンに出ます。 -------------コンテスト開始----------------- ・0:04 ふぇりん…

ACPC参加記(2019)

ACPC1日目 会津合宿鈍行部員なのでこれで来る。 pic.twitter.com/TTHbIbce8Y — olphe (@_olphe) August 10, 2019 南栗橋以降は人が少なく、席が広いのでかなり快適なんですが、電子マネーが使えない場合があるので、切符を買っておくとかなり無難であるよう…

Codeforces Round #581 (Div. 2)D-Kirk and a Binary String

問題概要 長さNの01からなる文字列がs与えられる。次の条件を満たすの文字列tを見つけたい。 長さがN 任意のについて、のLISとのLISの長さが同じ tに含まれる0の数が上二つの条件を満たす中で最大 メモ1 まず、先頭と末尾以外の文字について、文字を変更でき…

Codeforces Round #576 (Div. 1)C-Matching vs Independent Set

問題概要 3N頂点M辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。 ・互いに辺で結ばれていないサイズNの頂点集合 ・互いに頂点を共有していないサイズNの辺集合 解法 全ての辺を好きな順番で見ていき、これまでに辺集合に追加し…

全国統一プログラミング王決定戦本戦-F Flights

問題概要 N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、を満たすときにij間に距離の辺が貼られる。 スタートからゴールまでの距離の最小値を求めたい。距離はで表す。 メモ まずスタートとゴール…

全国統一プログラミング王決定戦本戦-E Erasure

問題概要 N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は通りある。全てのブロックを選択できる区間の使い方は何通りか。 メモ 素直なDPをする方法と包除原理を用いる方法がある。 素直なDP seicaさんから掲…

AGC008-E Next or Nextnext

問題概要 サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、 p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。 メモ 途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかった…

AtCoderで橙になるまでにやったこと

橙になった記事が少ないので橙記事を書きます。 前回のみんなのプロコンで橙になりました。 olpheさんの「みんなのプロコン 2019」での成績:77位パフォーマンス:2660相当レーティング:2374→2406 (+32) :)Highestを更新し、三段になりました!#AtCoder htt…

ICPC国内予選2018

メンバー紹介 ferin:基本的にはBとDを担当する。 div9851:基本的にはAとCを担当する。(←予選通過の立役者!!) olphe:基本的にはEとFを担当する。幾何が出たらferinさんと1問交換、構文解析が出たらdivさんと1問交換 模擬国内前 僕が入学してすぐにチームが…

codingame (Code of Cutulu)

ルール 最初正気度を250持っていて、毎ターン4~6正気度を失う。ただし、2マス以内(壁を挟んでもよい)に他の冒険者がいると1~3で済む。 敵はトンベリみたいな見た目のものと死神みたいな見た目のものがいる。 前者は毎ターン1番近い人を追いかける。冒険者と…

Xmas Contest 2017

今年も出ました! 迷路君とkenさんとチームを組んで参戦。 とりあえず迷路君が1問目を、僕が2問目を、kenさんが3問目を見ようかな見たいな話になったのでBを見る。 文字列の長さが15で32文字までに収めてね!って言われたので明らかに2個+アスタリスクが2個…

Codeforces Round #450 (Div. 2) D問題

和がNで数列の全要素のGCDが1となる数列の数を求めたい。 a(n) = sum_{d|n} mu(n/d)*2^(d-1) この式で表せるらしいが全然意味が分からなかったのでメモしておく。 d | n……dはnの約数という意味。 sum_{ }……{ }内のすべての要素について何か処理をする。 mu()…

北大&日立MMその1

1日目King's Graphはどうでもいいので、2S*2S四方のフィールドに元のグラフの頂点を乗せていくことにする。(King's Graphへの変換後に辺が伸びているかはチェビシェフ距離が1か否かで判定できる)とりあえず愚直貪欲を書いてみようと思って、頂点0をフィール…

DDCC2017参加記

前泊ダメだよとのことだったので朝5時ぐらいにお家を出て新幹線で東京に向かうことに。ほぼ始発だったのでめちゃくちゃ混んでて怖いね。 品川でりかちゃんとうしさんと合流して大森海岸へ、 4号車マンやが — olphe (@_olphe) 2017年11月2日 僕も4号車です — …

Marathon Match 95

画像が与えられるので、指定された数の半透明な円を描いていって元の画像に近づけようという問題。 作成途中の画像の状態だけが重要で配置の順番はどうでもいいと思ったのでビームサーチ案を捨て、貪欲に円を配置していくことを考えた。 貪欲パートは、ラン…

Codeforces Round #435 (Div. 2)

ABDの3完で239位 A問題 数字の数と作りたいMEX,N個の数が与えられる。数字を出現させたり消したりしてMEXを指定の数にしたい。 配列を用意して舐めてあげればよいです。 http://codeforces.com/contest/862/submission/30502250 B問題 木が与えられる。二部…

  Codeforces Round #434 (Div. 1, based on Technocup 2018 Elimination Round 1)

3完99位 Unratedめ… A問題 文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。 切る回数を最小にしたい。 前から貪欲に調べていって条件を満たし次第切ればよい。 貪欲なのでO(N) http://codeforces.com/contest/860/submission/30422…

Codeforces(MemSQL Start[c]UP 3.0 - Round 1)

5完122位でした!すごい!Round2も頑張るぞ! A問題 本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな? http://codeforces.com/contest/859/submission/30389464 B問題…

TCO17 Pittsburgh Event / Fun SRM

EasyとMedが通って33位 1573->1565(悲しいね) Easy 文字列sとtが与えられるので{0,o},{1,l},{m,n}の入れ替えだけでs->tにできるか判定する。 Med 数列が与えられるので、任意の3数の和が9の倍数にならない最大の組み合わせを求める。bitDPをしたがうしさんに…

CSAcademy#47

4完104位、悲しいね A 舐めて求める数を数えます B 何個数字使うかを全探索してうまくいくときに出力する。 C v[i]はnum[i][0]~num[i][W-1]のLCM、u[i]はnum[0][i]~num[H-1][i]のLCM 条件を満たしていたら出力 D 数がNの時は、N/2と(N+1)/2の結果から導き出…

CodeForces433(div1)

A 現在の時刻よりも早く出発すべきだった便のうち遅延コストのでかいものから飛ばしていく。自明。 1958->1910 こどふぉ、レート上げるの難しすぎるなあ

Poland Lighting Round(TC MM)

マスがあってチェスのナイトを置く。 あるマスを攻撃できるナイトの数がマスに書かれた数字に近づくようにしたい。 舐めつつ焼きなました。 https://github.com/olphe/MM/blob/master/MM_KnightsAttacks~Randomized.cpp なんかシステスと競技中のジャッジの…

MarathonMatch94

MM94お疲れさまでした。 まず全体的な方針として左上から詰めていく(順列を表すvector(以下ansとする)に前から順番に要素を追加していく)ことにした。 理由としては以下の2点 ①どこに一番得点が高い組み合わせを置いても同じだと思ったから。 ②左上にそろえ…

セグメントツリー

https://github.com/olphe/temp/blob/master/segment_tree.cpp 宣言時に要素数と、min,maxのどっちを求めるかを決める。 v:各要素 l:各要素がもつ範囲の一番左 r:各要素がもつ範囲の一番右 is_min:最小値を求めるか否かの判別をする。 Update,TopDown:一気に…

IOI列車で行こう(13本選2)

N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。 順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。 なお、電車はあまらせてもよいし、…