2019-09-01から1ヶ月間の記事一覧
お題箱より。 Problem - F - Codeforces セグメント木を使わない解法を…とのリクエストだったので、何通りか解法を紹介します。 問題概要 個の部屋が並んでいて、順に番号 が付けられている。これらの部屋全てにインターネット回線を提供したい。 回線提供に…
Problem - E2 - Codeforces 問題概要 正整数 に対して、 を十進表記で書いたものをこの順に連結した文字列を とする。例えば "1234567891011" である。 そして、 をこの順に連結した無限の長さの文字列を考える。与えられる 個の整数 に対して、この文字列の…
B - Sorting a Segment 公式解説と少し違う方法で解いたので記録。 解法 ある長さ の区間を昇順に並び替えた時に、値が変更される最左のインデックスを 、最右のインデックスを とします。この時操作の結果は、閉区間 内の要素を昇順に並び替えたものとなり…
E - Who Says a Pun? 解説で別解として紹介されている二分探索+ローリングハッシュで通したので書いておきます。 解法 条件を満たす長さで二分探索 「文字列 の連続部分文字列として位置が重ならずに2回以上出現する、長さ の文字列が存在する」ということ…
E - Sequence Growing Hard 公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。 解法 要素を挿入して、辞書順でより大きくなる条件は 長さ の数列に1つ要素を挿入して、辞書順でより大きい長さ の数列を作る方法…
概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力デ…
てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。 はじまり アルメリアさんへTTPCチーム組みませんかてんぷら— てんぷら (@tempura_cpp) August 1, 2019 ご指名いただきました…
お題箱より。 Problem - 1201B - Codeforces 問題概要 個の正整数 が与えられる。これに 異なる2つの要素を選び、それぞれの要素を1減らす。 という操作を繰り返すことで全ての要素を0にできるかどうか判定せよ。 制約 解法 この判定は競技プログラミングで…