olpheの競プロ帖

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

HUPC2023参加記

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 5/2 船のバスセットを予約していたので、同行者と神戸で集合しコメダで暴食した。 バスで電波の弱い兵庫の山奥を移動しながら…

ICPC模擬地区予選2022参加記

模擬地区予選に参加しました。 jag-icpc.org JAG系のオンサイトは久しぶりなので楽しみにしながらレジりました。 コンテスト前 早くから人が集まっているだろうと予想して意気揚々と開場時刻ごろに会場に向かうと参加者が誰も来ていなかったので見知ったスタ…

HUPC2021day2農工大セットのコメント

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); コンテストへのリンクです。 Aizu Online Judge Arena A問題 簡単枠が欲しいねえって言っていたらいつの間にか生えていた。 1…

Weird LIS(AtCoder Grand Contest 055)

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); 問題概要 ある $1$ から $N$ までの順列 $P$ があって、$P$ の $i$ 要素目を取り除いたときのLISの長さを $A_i$ とする。$2\l…

Online MST(THIRD プログラミングコンテスト 2021 (AtCoder Heuristic Contest 007))

MathJax.Hub.Config({ tex2jax: { inlineMath: [['$','$'], ['\\(','\\)']], displayMath: [ ['$$','$$'], ["\\[","\\]"] ] } }); $8$位だったのでやったことを書く。 問題 $N=400$ 頂点 $M=1995$ 辺のグラフがある。辺のコストははじめ不明である。 $ M $ …

ICPC2021国内予選参加記

予選以前 去年まででふぇりんさんが引退してしまったので今年からはなーぶ君が加入して新生nowcowとして生まれ変わった。 なーぶ君には幾何とフロー実装できるようにしといてくれ!と叫んでいたらAOJの幾何の基礎のやつ(?)とか埋めていてえらかった。 でぃ…

civ6マルチ プレイレポ

RaF持ってない人がいたので無しでやる。以前そのような状況でマルチをやった人がいるらしく、その場合はプレイできなかったらしい。 1日目(1~80ぐらい)首都に隣接している6マスのうち5マスは川沿いでラッキー。序盤にベトナムが異常な時代スコアを出している…

ICPC2020アジア地区大会参加記

ICPC2020のアジア地区大会(オンライン)に参加していました。 昨年は予選に落ちてしまったので2年ぶりの参加です。 メンバーは変わらずferin+div+olpheの3人でnowcowを結成していました。 コンテスト以前 国内予選終わってからチーム練は12月までほぼ毎週、2…

Codingame FallChallenge2020

情報少な目のDPをした。 GOLDの上の方だった。全体159位だった。 ルール ポーションを作って金を得る。 金をたくさん持ってたら勝ち 4種類の材料がある。 常に5種類のクエリが存在する。 毎ターン行動を選ぶ。 相手と被った場合は両方が成功する。 こなされ…

第4回アルゴリズム実技検定 感想+解法

序盤の問題の読解や細かい設定がつらい感じで序盤でかなり時間を使ってしまった。反面後半の問題で詰まることはあまりなく、全体としてはスムーズに解けたと思う。(100分41秒) A:vectorにpair持たせてソートした。 B:100倍した。 C:全探索 D:左、右に絶対に…

ICPC国内予選2020

出ました。結果は5完で7位!nocowの5位には及びませんでしたが農工大記録に迫る好成績でした!アジアでも頑張ります。 A:一瞬で通ってた B:一瞬で通ってた C:1/2乗と1/3乗までの約数列挙すれば全探索できることが分かったので、即2分(120秒)探索を書いた。多…

模擬国2020

出ました。 ライブラリは、どうしても自分のを使いたいものだけ印刷して、他は他の人に任せるか!wという気持ちで準備した。他の人どうしてただろう。(は?)(模擬国のあとでふぇりんライブラリを共有することになった) Discordのサーバ(?)立てて各問題用に…

2円の共通接線

中心がにあって、半径がである円1と、中心がにあって、半径がである円2の共通接線を求めたい。 原点を中心に回転させて、回転後において接線が常にx軸と平行になるようにしたい。またその時、接線があるとすれば、である。 更に、円2は接線の上側にある場合…

ACPC2020day1準備

農工大セットを作りました。 やったこと 立命館の人に枠頂戴って言った。くれた。 日程決めるのに会津の人と北大の人と話した。 原案はgoogle スプレッドシートとhackMDで管理して、データセットとか問題文はgithubで管理した。 こういう技術的なやつ何もわ…

Japan Alumni Group Summer Camp 2015 Day 3

Japan Alumni Group Summer Camp 2015 Day 3のバチャをやった。6完57011ペナ B: シフトの仕方は以下の4通り ・右シフトのみ ・左シフトのみ ・右シフトした後左シフト ・左シフトした後右シフト 各位置について自分より右にある1の中で一番左にある1の位置を…

AGC044-C Strange Dance

ある桁は自分より小さい桁に対して影響を及ぼさないので、操作後の下i桁目について、操作前の下i桁の数によってのみ決まる。 サルサが流れると、すべての桁が変わる。(0のときは変わらないが、変わると考えても困らないので変わると考える。) サルサが2回流…

第二回 アルゴリズム実技検定 解説記事

A 今地上にいるかいないか、目的地が地上にあるかないか4通り場合分けします。 B それぞれの文字が何個あるか見ます。 C 下の行から順に見ていき、Xを見つけたら右上、上、左上のそれぞれについて空白でなければXにします。 D 文字列全部列挙してSのすべての…

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…