2019 年 2 月 23 日 (土) に 2017 Beijing Regional を vjudge で解いたのでその時の立ち回りのメモです メモ 開始。前回の反省を踏まえて、自分は後ろの問題から目を通していき、rsk0315 が前から目を通していき、TAB が A に目を通すことにした。A 問題が…

2019 年 2 月 10 日 (日) に 2016 Dalian Regional を vjudge で解いたのでその時の立ち回りのメモです メモ 開始。TAB が A を見て、rsk0315 が B を見て、自分が C を見る。B は正規表現ぽいらしい。自分も見てみてひと目で Shift-or っぽいと思ったがなぜ…

問題概要 原文 → Problem - F - Codeforces の倍数 と、整数 が与えられるので、以下を全て満たす正の整数集合を構築できるかどうか判定せよ。 要素数は で、値は全て 以下で相異なる の各元 について、要素を で割ったあまりが になるような、集合内の要素…

問題概要 原文 → Problem - E - Codeforces '.' または 'z' のマスのみからなる の盤面が与えられる。この盤面内に存在する「Z 型」の正方形領域がいくつ存在するか求めよ。 Z 型の正方形領域の定義 最も上と最も下の行は全て 'z' 反対角成分は全て 'z' それ…

tsutaj です。今回は競技プログラミングの解説記事ではなく、競技プログラミングに関するアプリケーションのリリースノートを書きます。 Competitive Programming Team Maker ユーザーのレーティングと所属を元に、以下の条件をできるだけ満たしつつチーム分…

問題概要 原文 → 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 な括弧列になるパターンは何通りあるか？…