Advent Calendar Contest 2020 の 18 日目として、ecasdqina さん作の問題の tester を担当しました。tester 解は、writer 解と少しアプローチが異なっていたので紹介したいと思います。また、コンテスタントの提出を見て発見した、形式的べき級数を一切使用…
この記事は Competitive Programming (1) Advent Calendar 2020 の 13 日目の記事として書かれました。 以下のツイートから着想を得たネタで書いています。完全にポエムなのでご了承ください。 「純粋培養競技プログラマが就職して１年」みたいなブログがよ…
このツール使ってる人なら既にやってるひと多そうだけど一応 概要 Online Judge Template Generator で普通にテンプレートを出力させると std::endl を利用したものが出力されるが、こどふぉ等で出力 TLE になる可能性があるのでできれば使用を避けたい。 pr…
9/14〜9/16 に HUPC2020 が開催され、9/14 は 北大セット でした。元々は RUPC2020 の北大セットとして出す予定だったので自分もまだ作問に携わっていて、今回で大学合宿の作問は卒業ということになりました。思い返してみれば、RUPC2017 からセット提供する…
この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます 問題概要 原文 (PDF): https://codeforces.com/gym/101982/attachments/download/7897/20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf 整数 が与えられる。 を満たす…
問題概要 原文はこちら atcoder.jp 棒が 本ある。これらのうち異なる 本に輪を投げ入れることを 回行う。投げ入れ方によって以下のように得点が定められる。 回目に 番目の棒に輪を投げ入れたとき、 点を得る。これらの合計を とする。 番目の棒について、全…
問題概要 原文はこちら atcoder.jp 長さ の数列 があり、 ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 回行った後、最終的にできた数列を出力せよ。 整数 が与えられるので、 と を交換する。 整数 が与えられるので、 を…
調べても解説がなかったので 問題概要 原文 → D - 大爆発 日本語なので元の問題文参照 解説 まず自明なケースとして、以下があります。地味に厄介なので最初に弾きましょう。 ブロックがひとつも存在しない (答えは ) 全てのマスにブロックが存在する (答え…
こういうの典型なんですかね？結構面白い気がしたのでブログに残しておく 問題概要 原文 → Problem - G - Codeforces 個の箱が一列に並んでいる。箱の中身は石またはギフトである。石が入っている箱はすべて同じ重さであり、ギフトが入っているどの箱よりも…
はじめに これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。 ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ) https://hcpc-hokudai.github.io/archive/algorithm_divide_and…
この記事は 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 チーム通過している見込みで、ひとまずは安心です。しかしもう少しがんばりたかっ…
