Intro 普段は深夜2時からCodeforces, 根津駅の階段でバテる、好きなプログラミング言語はC++, 最近AtCoder黄色を目指している東京大学のパソコンオタクです。 突然ですがこのたび、ジムに通い始めました。 きっかけは友人が腕につけていたfitbitがかっこよか…
ポエムです。 先日院に進学しました。なんか教授たちが、院生は実質プロの研究者（煽りの文脈ではない）なので、 自覚をもって社会に還元すべく研究をしてください、みたいなことを言ってて、もう自分もそういう段階なのかーという気分になりました。これに…
競プロで使える謎高速化テクニックを集めた記事ほしいな— Joe@社会 (@xuzijian629) March 31, 2019 ということで自分で書きます。ここでいう高速化とは真に計算量を落とすようなかっこいいものではなく、定数倍高速化のことを指します。 まあこういうのは無…
前回の投稿から一ヶ月以上空いてしまったので何か書こうかなと思いまして、先日無事書き終えた卒論を振り返ってみようと思います。 TLDR; 卒論を提出しました。 卒論を提出！！！ pic.twitter.com/Y6BW2hjGDl— Joe@卒論発表☆☆☆☆☆ (@xuzijian629) January 31,…
事の発端 ぼくがICPC後に急に競プロにハマり始めて、でも案外（案外でもないか）毎日精進を続けるのは難しかったので学科Slackにそれをサポートする botを配置しようという話になりました。 結論から言うと、1ヶ月ぐらいはうまく機能しましたが、だんだんみ…
この記事はCompetitive Programming (1) Advent Calendar 7日目の記事とISer Advent Calendar 8日目の記事として書かれました。 TL;DR Implicit Treapを実装しました。以下の操作がクエリ毎O(logn)で可能です。 配列のランダムアクセス 配列の任意箇所へのin…
この記事はCompetitive Programming (2) Advent Calendar 2018およびISer Advent Calendar 2018 1日目の記事です。 CodeForcesやTopCoderで海外勢がよくヘッダーに #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> とかをインクルードしていますが、これのことです。日本語の記事が見当</ext/pb_ds/tree_policy.hpp></ext/pb_ds/assoc_container.hpp>…
お友達がたくさんできたのがよかったです。成績はダメでした。来年がんばりたいね。 高校時代/小学校時代の友達と再会できたしめでたしめでたし。 それにしてもEの簡単な解法に気づかず無限にバグらせて3完だったのはかなりありえなかったので来年は20位ぐら…
タイトルにあるようなことを昨日考えてました。 試すとわりとすぐに気がつくのですが、(n, (n-1の約数))が条件を満たします。 例えば10進数では(10, 1), (10, 3), (10, 9)で、16進数だと(16, 1), (16, 3), (16, 5), (16, 15)ですね。 導出の過程を簡単に紹介…
@bknshnと組んで出ました。後半３問を担当しました。 Dが難しかったのでE, Fを先に書きます。 E - Chef and Periodic Sequence https://www.codechef.com/SNCK1A19/problems/PERIODIC もともとこれがFでしたよねー、いつの間にか順番が変わっていました。明…
久しぶりの投稿です（Codeforcesは久しぶりではない） 紫になりました。やったー！ D - Minimum Path 解法は以下のSlackのトークを参考にしてください。 ところでこの問題を解いているときに、以前のHackerRankのUniversity Codesprint 5の問題を思い出しま…
東京大学大学院情報理工学系研究科コンピュータ科学専攻の院試結果の開示が届きました。 自分が受験するときに全然点数情報がわからなかったので、来年度以降調べる人用に自分のものを開示しておきます。 こんな感じです。第一志望の杉山研に受かりました。 …
【重要】面倒なので、区間の始点終点はすべて異なるとします。そうじゃない場合は適切にソートして順序付けとかしてやると大丈夫です。多分。 すでに区間がたくさんあって交差する回数を数えるやつ No.743 Segments on a Polygon - yukicoder 区間を(start, …
競技Swarmerを引退する（Swarm自体は続けます）のでこの機会に競技SwarmのTipsを残していこうと思います。 得点システムとかあんまり調べても出てこないと思うので自分が1年ぐらいやってわかったことなど思い出しながらまとめていきます。 競技Swarmとは iOS…
Day3はLink-Cut木コンテストだったんですが、むずすぎたのでもうちょっと理解してから記事にしようと思います。 Day4はstereometry（空間の幾何？）コンテスト A - Elementary 問題 4点与えられるのでそれらを頂点とする四面体の体積を求めて、という問題 解…
Day1の内容はJAG合宿Day3と全く同じだったようです。なので記事はDay2からにしようと思います。 beta.atcoder.jp A - Alice and Maze 問題 頂点辺の無向グラフが与えられる。各頂点に報酬、各辺にコストが設定されている。 頂点を訪れるたび、その報酬が貰え…
飛行機の移動が暇なので蟻本を読んでまとめることにしました。 今回は組み合わせ問題編です。 分割数 問題 個の互いに区別できない品物を個以下に分割する方法の場合の数をで割ったあまりを求めよ。 たとえば、4つの品物を(1, 1, 2)と分割するのと(1, 2, 1)…
D - Factorization 長さの正整数の配列で、各要素の積が正整数となるようなものが何通りなるか、という問題。 解法 の素因数分解を考え、とします。今の問題は次のように言い換えることができます。 個の箱があり、個のを重複を許して入れます。 それぞれの…
F - The Shortest Statement 問題概要 頂点辺の連結な重み付き無向グラフが与えられる。個のクエリに答えよ。番目のクエリでは頂点間の最短距離を答えよ。 考えたこと 木っぽいグラフが与えられるということなので、とりあえず木に場合について考えてみるこ…
CでWAを引きすぎて飛ばしてしまい、Dから解いたので574位になってしまいました、、、 C - Vasya and Golden Ticket 0を除いて考えても同じなのではじめに0を除去しておきます。除去後の文字列が空列なら、これは"0...0"という入力に対する場合であり、"YES"…
ABCD解いて443位でした。可もなく不可もなくといった感じ。Fの解法がめっちゃ気になっているので別記事にします。 C - Vasya and Multisets 1回だけ現れる要素が偶数種類だったら同じ種類ずつ振り分けて、複数回現れる要素を片方にまとめる。 1回だけ現れる…
ABC早解きで123位でした。DはHack中にミスに気づいて厳しい気持ちになってました Div. 1との同時開催だったので普段より強い（早い？）人が少なくて、A, Bを解き終えた時点でほぼトップだったのでびっくりしてました C - Enlarge GCD まず制限時間1秒を見て…
C - Chokutter かなり古い企業コンの問題です。点数はついていませんが、感覚では500ぐらいかなと思います。 問題概要 頂点のグラフが与えられます。はじめグラフには辺がまったく張られていません。 個のクエリが与えられます。クエリには以下の3種類があり…
JAG Camp 2018 Day 3の問題 J - Prime Routing 問題の本質を抽出すると次のようになります。 問題 連結で単純な無向グラフが与えられる。頂点Sから頂点Tに向かう奇数長の最短路の長さはいくらか（辺の長さはすべて1）。存在しない場合は-1を出力せよ。 こん…
原題はE - Self-containedですが、問題の本質は以下のとおりです。 問題 0以上未満の整数からなる集合が与えられる。この中の相異なる3要素で、となるものはあるか。 知識 今回は要素の大きさに制限がありますが、制限がない場合、のアルゴリズムが限界だと…
595位でした。前日に比べればかなりマシですが、AとCをHackされ、 さらにEよりCを優先したためさほど難しくないEを捨ててしまうという散々な結果でした。 追記）Eやっぱむずかったです。じゃあまあいつも通りの結果という感じですかね C - Array Product 0の…
散々な成績でした。C, 正解者数的にも絶対シンプルなアルゴリズムがあるのに思考を切り替えられなかったです。 codeforces.com C - Coffee Break 1日目には、が最小なものから、差をより大きくして、選べるだけ選びます。選んだものはその都度、setから削除…
問題 以下の相異なる3つの素数の組のうち、が素数になるものはいくつあるか。 No.732 3PrimeCounting - yukicoder 解法 100000以下の素数の個数は10000個ぐらいなので、で間に合う。ただしは以下の素数の個数。この問題の場合、自明な解が10分ぐらい待てば動…
University Codesprint 5で唯一解けなかった問題。ツイッターを見る限りFよりもずいぶん簡単という評価だったのでコンテスト中に解けるようになりたい www.hackerrank.com 番目の店で本の剣を買う費用は円で、それを番目の店ですべて売ると、円の利益がでま…
A - Function Height 入力が大きい整数のときはdoubleの精度が足りなくなるので、整数のまま処理をしましょうという問題 B - Diagonal Walking v.2 まずゴールまで最短で行ってから、(1,1), (-1,-1)のムーブを繰り返すという戦略が最適なのであとはやるだけ …
