問題概要 原文 → Problem - F - Codeforces 以下のクエリを処理せよ。なお、以下で考慮する座標はすべて自然数座標である。 点集合に を追加する 点集合から を削除する 点 が与えられる。その時点の点集合について、原点 と を結んでできる直線に対して線対…

問題概要 原文 → Problem - E - Codeforces 頂点からなる森が与えられる。このグラフに対して辺を追加して木を作りたい。木の直径が最小になるように辺を追加した時の、その直径の値と追加すべき辺を列挙せよ。 解説 森を木に分割して、木同士をマージするこ…

問題概要 原文 (D1) → Problem - D1 - Codeforces 原文 (D2) → Problem - D2 - Codeforces 長さ の数列が与えられる。以下の操作を繰り返し行うことによって、全要素の値を等しくしたい。 D1 で認められる操作 値が同じである隣り合う要素を選び、その両方に…

問題概要 原文 → Problem - C - Codeforces 文字の文字列 があり、あなたは が全体としてどのような文字列であるかは知らない。しかし、長さが から までの全ての prefix と suffix についての情報は持っている (ただし、どれが prefix でどれが suffix かは…

コンテストからだいぶ日が開いてしまいましたが、参加記を書きます。 ACM-ICPC 2018 Asia Yokohama Regional Contest に参加しました。昨年と同様に four-t として参加しました。また、同じ大学からチーム Megido も参加しました。 0 日目 (前日の移動) 本当…

この記事は Competitive Programming (1) Advent Calendar 2018 の 17 日目の記事として書かれました。本来なら日本で執筆する予定だったんですが、飛行機運が悪すぎて機内でスマホを使って記事を書いています。限界すぎる。 先日、2018 年 12 月 17 日現在…

数学的な知見がいっぱいあったので備忘録です。 問題概要 日本語なので原文を参照してください → D: チップ・ストーリー ～黄金編～ - DISCO presents ディスカバリーチャンネル コードコンテスト2019 予選 | AtCoder 解説 この問題を解くには、いくつかの数…

CODE FESTIVAL 2018 に参加しました。予選は 2 年前から参加していましたが、3 度目の正直で今回やっと初めて本戦に参加できました。感想をいろいろつづります。 予選 予選 A で解けるタイプの DP が運良く出たので、通過しました。予選 B が結果的に早解き…

先月末に、めでたく AtCoder 黄色になりました。 1976 -> 2025 (+49)念願の！！！！ 黄色！！！！ です✌️✌️✌️✌️✌️✌️✌️ pic.twitter.com/6S5whNlq8G— tsutaj (@_TTJR_) 2018年9月29日 きのう、ふと「黄色になりました記事書いてないなぁ」と思って雑に呟いた…

会津大学プログラミング合宿 2018 に参加しました。ACPC は実は初参加です。 0 日目 JAG に行っていたので東京にいた。TIke さんと seica さんと ferin さんと olphe さんでボドゲカフェに行ってあそんだ。ワイナリーはワイン農家をやめた者が勝つゲームだっ…

初めて JAG 夏合宿に参加しました。同じ大学からは four-t のチームメイト (rsk0315 君と TAB 君) と waku 君も参加しました。以下、雑に記します。 0 日目 札幌から東京まで移動した。なんか自分が離陸した後に新千歳行きの電車が止まったらしく、わりとあ…

昨日、ACM-ICPC 国際大学対抗プログラミングコンテストの国内予選 が行われました。自分が所属する北海道大学からは 4 チームが参加し、3 チームが 4 完・1 チームが 3 完しました。このうち 2 チームはアジア地区に行けそうで、弊学サークル全体のレベルの…

リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。 自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒…

問題概要 原文 → Google Code Jam 長さ の数列 (この数列の 番目の要素を とする) と、整数 が与えられる。 は より大きく、数列の要素の総和は 未満である。 新たな数列 を作ることを考える (この数列の長さを とし、 番目の要素を とする)。 は長さが 以上…

#RUPC2018 pic.twitter.com/cTQUtSQFcV— tsutaj (@_TTJR_) 2018年3月26日 立命館大学競技プログラミング合宿 2018 (通称 RUPC 2018) に参加しました。去年に引き続き 2 回目の参加です。いやあ濃密な三日間だったなあ・・・ 以下時系列順に振り返るいつもの …

問題概要 日本語なので原文参照 → D - Checker 解説 公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。 考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。こ…

問題概要 原文 → CS Academy 頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。 はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除…

問題概要 原文 → CS Academy の行列 から、 の行列 を作る。 (作り方は原文参照) を作る前に、 について行どうし、または列どうしのスワップを合計 回まで行える (何もしなくても良い) とき、 の最大値を求めよ。 解説 ある要素が、 の要素のうちいくつに関…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ハノイの塔をアレンジしたゲームを考える。 つの棒に、左から 個、 個、 個のディスクが刺さっている (ハノイの塔と同じように、大きさは相異なる)。これらのデ…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので) この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取っ…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。 と の最長共通部分列 (LCS) が と の LCS が と の LCS が 解説 を仮定すると、次の…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。 解説 Div2 では制約が小さいため、以下のように解くことができます。 「先頭 …

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。 点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 括弧列 と が与えられる。 に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか？…

蟻本練習問題の解説をします。今回のトピックは動的計画法です！ 今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。 から まで移動するとき、コスト和の最小値を求めよ。 解説 横方向に移動す…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。 与えられた木から、辺の重…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement digit1 桁の数 と、digit2 桁の数 を、以下の条件のもとで作ることを考える。 leading zero を許す の各桁において、登場する の個数の合計は最大で 個 このよう…

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる無向グラフがある。頂点にはそれぞれ色 が付いている。 同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) …