hogecoder

tsutaj 競技プログラミングの記録

月報 (2021 年 9 月)

あれ、月変わってるじゃん月報ナチュラルに忘れました (明日書こう・・・)— homu (@homuhomucomp) 2021年9月30日 気づいたら 10 月になってたので月報を完全に忘れてました。日付感覚がほしい。

月報 (2021 年 8 月)

今月分の月報です。家で晩酌しすぎ問題は禁酒したらマシになりました。みんなも禁酒やろう。

FaceBook Hacker Cup 2021 Qualification Round C: Gold Mine

問題概要 問題原文 → Problem C2: Gold Mine - Chapter 2 | Facebook Hacker Cup - 2021 - Qualification Round 頂点の木があり、それぞれの頂点 には重み がついている。木から高々 個の辺素パスを取るとき、パスに含まれる重みの和の最大値を求めよ (ただ…

月報 (2021 年 7 月)

今月分の月報です。眠れない問題は梅雨明けとともに勝手に治りました。その代わり、日々の晩酌をやめられないことが最近の悩みになりました。

月報 (2021 年 6 月)

今月分の月報です。梅雨時期は眠れなくなりがちなのか、最近あんまり寝れてないです。大学までは梅雨と無縁の生活だったので、なんとなく生活リズムが以前とは違いますね。

月報 (2021 年 5 月)

今月から月報を書いてみることにしました。今月の自分が何を為したのか、何を為さなかったのかを把握したりなど、1 ヶ月の振り返りができればいいかなと思っています。

リモートワークのために揃えて便利だったもの一覧 (エンジニア向け)

リモートワークのために揃えてよかったもの一覧みたいなブログを書こうかなと思ってやめるのを無限にやってる (新卒勢が 3 月に色々揃えがちなので、書くなら 2 月中がいいのかなあ)— tsutaj (@tsutaj) 2021年2月24日 ちゃんと記事書いてえらい。 この記事は…

Advent Calendar Contest 2020 18 日目: 塗るめた

Advent Calendar Contest 2020 の 18 日目として、ecasdqina さん作の問題の tester を担当しました。tester 解は、writer 解と少しアプローチが異なっていたので紹介したいと思います。また、コンテスタントの提出を見て発見した、形式的べき級数を一切使用…

純粋培養競技プログラマが社会に出てみた感想

この記事は Competitive Programming (1) Advent Calendar 2020 の 13 日目の記事として書かれました。 以下のツイートから着想を得たネタで書いています。完全にポエムなのでご了承ください。 「純粋培養競技プログラマが就職して1年」みたいなブログがよ…

Online Judge Template Generator で std::endl を使わないようにする

このツール使ってる人なら既にやってるひと多そうだけど一応 概要 Online Judge Template Generator で普通にテンプレートを出力させると std::endl を利用したものが出力されるが、こどふぉ等で出力 TLE になる可能性があるのでできれば使用を避けたい。 pr…

大学合宿の作問を卒業した & HUPC2020 Day1 の講評とか

9/14〜9/16 に HUPC2020 が開催され、9/14 は 北大セット でした。元々は RUPC2020 の北大セットとして出す予定だったので自分もまだ作問に携わっていて、今回で大学合宿の作問は卒業ということになりました。思い返してみれば、RUPC2017 からセット提供する…

2018-2019 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) B: Coprime Integers

この辺の (海外の ICPC 問題の) 記事書く人いなさそうなので書きます 問題概要 原文 (PDF): https://codeforces.com/gym/101982/attachments/download/7897/20182019-acmicpc-pacific-northwest-regional-contest-div-1-en.pdf 整数 が与えられる。 を満たす…

第三回アルゴリズム実技検定 O 問題: 輪投げ

問題概要 原文はこちら atcoder.jp 棒が 本ある。これらのうち異なる 本に輪を投げ入れることを 回行う。投げ入れ方によって以下のように得点が定められる。 回目に 番目の棒に輪を投げ入れたとき、 点を得る。これらの合計を とする。 番目の棒について、全…

第三回アルゴリズム実技検定 N 問題: 入れ替えと並び替え

問題概要 原文はこちら atcoder.jp 長さ の数列 があり、 ははじめ昇順にソートされている。この数列に対して以下で説明される操作を合計 回行った後、最終的にできた数列を出力せよ。 整数 が与えられるので、 と を交換する。 整数 が与えられるので、 を…

天下一プログラマーコンテスト 2012 予選 B D: 大爆発

調べても解説がなかったので 問題概要 原文 → D - 大爆発 日本語なので元の問題文参照 解説 まず自明なケースとして、以下があります。地味に厄介なので最初に弾きましょう。 ブロックがひとつも存在しない (答えは ) 全てのマスにブロックが存在する (答え…

Educational Codeforces Round 87 G: Find a Gift

こういうの典型なんですかね?結構面白い気がしたのでブログに残しておく 問題概要 原文 → Problem - G - Codeforces 個の箱が一列に並んでいる。箱の中身は石またはギフトである。石が入っている箱はすべて同じ重さであり、ギフトが入っているどの箱よりも…

分割統治法メモ

はじめに これは自分の備忘録的に書いているだけであり、体系的に書いているわけではありません。ご了承ください。 ちなみに蟻本 +α くらいの情報をまとめている資料が以下にあります (ダイマ) https://hcpc-hokudai.github.io/archive/algorithm_divide_and…

HCPC のホームページを移行した話

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

ICPC の現役を引退した

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

ACM-ICPC 国際大学対抗プログラミングコンテスト アジア横浜大会 参加記

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

PCK 2017 本選 5: 朝昼晩ごはん

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

ACPC 2019 参加記

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

JAG 夏合宿 2019 参加記

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

TTPC 2019 参加記

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

AtCoder Grand Contest 030 F: Permutation and Minimum

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

Codeforces Round #581 Div. 2 D: Kirk and a Binary String

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

LeetCode Weekly Contest 149: Swap For Longest Repeated Character Substring

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

LeetCode Weekly Contest 149: Online Majority Element In Subarray

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

TopCoder SRM 764: RectangleHunt

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

LeetCode Biweekly Contest 6: String Transforms Into Another String

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