この記事は Competitive Programming (1) Advent Calendar 2019 の 12 日目の記事として書かれました。 2019 年 11 月に、北海道大学競技プログラミングサークルのホームページを FC2 から GitHub Pages へと移行しました。移行していろいろと便利になりまし…

今年の ICPC アジアの大会参加記 にも書いたとおり、今回をもって ICPC の現役を引退しました。それと同時に、北海道大学競技プログラミングサークルの運営 (部長的立場なんですが、役職という概念が存在しないため適切な用語がない) も退くことになりました…

2019/11/16 〜 18 に行われた ICPC アジア横浜大会 に参加しました。 Day 0 鳥取の学会に行っていたので、鳥取から横浜まで夜行バスで移動しました。所要時間は 11 時間 (つらい)。あまり寝られなかったので AOJ-ICPC の問題を考察してました。 Day 1 午前 7…

この難易度帯にしては難しいなあと思ったら、自分の解法が想定と違った。 問題概要 日本語なので原文参照 → Aizu Online Judge 解説 人 と人 の食事の時間を同時に満たせるかどうかを考える。この判定は if 文で容易に行える。 さて、元の問題は「 に含まれ…

会津大学競技プログラミング合宿 2019 に参加しました。昨年に引き続き、2 年連続 2 回目の参加でした。 Day0 JAG 夏合宿 (参加記へのリンク) の後だし、休むか・・・と思っていたはずなんですが、昼からひたすらボドゲカフェでボードゲームをし、やよい軒で…

JAG 夏合宿 2019 に参加しました。昨年に続いて二回目で、今年も four-t としてチーム全員で参加しました。今回は作問もすることになったので昨年とは少し違う面持ちで参加した気がします。 Day 1 割と時間ギリギリでオリセンに向かっていると、知ってる顔の…

2019/8/31 に開催された 東京工業大学プログラミングコンテスト に参加しました。 前日まで 某社に行ったり五等分の花嫁展に行ったり中本を食べたりした。 かわいいを摂取 (@ 池袋サンシャインシティ 展示ホールA in 豊島区, 東京都) https://t.co/jl2h6XfzG…

問題概要 日本語があるので原文参照 → F - Permutation and Minimum 解説 と の順序は答えにあまり関係ないので、数列を 2 個のブロックに区切って考えていき、ブロックの中は (左の値) < (右の値) という関係が常に成り立つものとする。ブロックの状態とし…

問題概要 原文 → Problem - D2 - Codeforces 0 と 1 のみからなる長さ の文字列 が与えられる。 の文字を、以下の条件が満たされた上で変更することを考える。 全ての に対して、 の 文字目から 文字目までのみからできる最長単調非減少列の大きさが元の文字…

本番に書いたコードの実装が悪すぎたので書き直し 問題概要 原文 → Loading... 文字列 が与えられる。この文字列に対して、あるふたつの文字を選んで swap することが一度だけできる。同じアルファベットを最大で何連続させられるか答えよ。 解説 まずランレ…

問題概要 はじめに、長さ の数列 が与えられるので、以下のクエリにオンラインで答えよ。 の 番目から 番目の間に 回以上出現するものを答えよ。なお は区間の長さの半分を真に超えるため該当する場合は 1 つしか該当しない。そのような要素がなければ -1 と…

問題概要 原文 → TopCoder Statistics - Problem Statement 個の点が与えられる。 与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。 …

問題概要 原文 → Loading... 文字列 と が与えられる。 以下の操作を 0 回以上行うことによって、 を と一致させることができるか判定せよ。 アルファベットをふたつ選び、それを とする。 に含まれる全ての を同時に へ変更する。 解説 操作をグラフとして…

個人的に面白かったので書きます。 問題概要 原文 → Contest Page | CodeChef 整数集合 (multiset ではない set) があり、はじめは空集合である。この集合に対して以下で示すクエリを 回処理する。 整数 が与えられるので以下を処理 に を insert する の元 …

本番は嘘解法で通してしまったのでちゃんと書きます。 問題概要 原文 → Problem - D - Codeforces のグリッド状のマスが与えられ、それぞれは白または黒に塗られている。 このマスの任意の 長方形領域に対して、その領域内にあるマスを全て白にするという操…

問題概要 原文 → Problem - D - Codeforces 長さ の整数列 と、パラメータ が与えられる。 数列内の連続する閉区間 について、そのコストは で表される。なお、空の区間に対するコストは である。 あり得る全ての区間を考慮した時のコストの最大値を求めよ。…

問題概要 原文 → Problem - E - Codeforces 色のボールがあり、 番目の色で塗られたボールは 個ある。 これらのボールを以下の条件を全て満たすように箱に入れる。 それぞれの箱について、箱の中にあるボールの色は 種類のみ 空箱が存在しない 箱に入ってい…

問題概要 原文 → TopCoder Statistics - Problem Statement 種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。 それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムであ…

HUPC 開催の経緯 これまで自分が RUPC や ACPC などの他大学の競技プログラミング合宿に参加してきて、自分も合宿を主催して他大学の (特に北海道の) 競技プログラマと楽しみたいという思いがあって、開催することにしました。やると決めたからにはたくさん…

ICPC の国内予選に参加しました。今年も four-t として rsk0315, TAB, tsutaj のチームで出ました。 弊学からは 7 チーム出て、全チーム 3 完でした。昨年に引き続き今年も 2 チーム通過している見込みで、ひとまずは安心です。しかしもう少しがんばりたかっ…

JAG の模擬国内予選 に参加しました。チーム結成 3 年目にしてようやく、初の全員揃っての参戦でした。 模擬予選の様子 自分は A の担当になっているので開始直後から読む。いけそう。一応オーバーフローとか入出力ミスとかそのへんに気をつけながら実装して…

2019 年 6 月 2 日 (日) に AOJ でチーム練習をしたのでその時の立ち回りのメモです メモ 開始。A はすぐわかるので書いて通す。B は微妙に計算量落とさなかったみたいで 1 ペナあったけど通ってた (問題見てない)。C, D もいつの間にか rsk0315 と TAB が通…

同じ方針でやっている人があまりいなさそうなので一応書きます。 問題概要 日本語なので原文を参照してください → Card | Aizu Online Judge 解説 整数を組み合わせて最終的に という数を作ったとします。与えられるそれぞれの整数について、その整数の 1 の…

2019 年 5 月 19 日 (日) に 会津合宿 2013 Day1 を AOJ で解いたのでその時の立ち回りのメモです メモ 開始。A がパッと見面倒そうだけどよくみたら制約が優しい。落ち着いて書いて AC。 B は TAB と rsk0315 が頑張っていたので任せて、自分は C を見る。…

2019 年 5 月 13 日 (日) に 会津合宿 2014 Day3 を AOJ で解いたのでその時の立ち回りのメモです メモ 今回は北大の別のチーム (チーム名未定) も参加してました。 開始。前回と同じ戦略で進めていった。まず A を読んで実装したが若干読み間違えていてサン…

2019 年 4 月 21 日 (日) に 2017 Tehran Regional を vjudge で解いたのでその時の立ち回りのメモです メモ 今回は京大勢や ragan (北大の別のチーム) も参加してました。 開始。今回は rsk0315 が環境構築、自分が序盤の問題を読み、後半を TAB に読んでも…

2019 年 4 月 14 日 (日) に 2015 Shanghai Regional を vjudge で解いたのでその時の立ち回りのメモです メモ 開始。前回に引き続き rsk0315 に環境構築をやってもらう。問題を 3 つに分けて読み進めていくも、簡単な問題を取りこぼすとまずいので順位表も…

tsutaj です。もうすぐ新年度になるので、弊学の競技プログラミングサークルを紹介します。特に春から北大に入学・進学する方々の参考になれば幸いです。 競技プログラミングとは？ まず、この記事を読んでくださった方で「競技プログラミングって何？」と疑…

立命館大学プログラミング合宿 2019 (RUPC 2019) に参加しました。RUPC への参加は 3 年連続 3 回目です。 Day 0 飛行機で関西国際空港に到着、その後電車で立命館大学まで移動。空港に 14 時半 くらいに着いたし、集合時間の 18 時にはまあ間に合うでしょう…

問題概要 原文 → Problem - F1 - Codeforces 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。 木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これ…