ferinの競プロ帳

競プロについてのメモ

AtCoder

CODE FESTIVAL 2014 予選A D - 壊れた電卓

問題ページ D: 壊れた電卓 - CODE FESTIVAL 2014 予選A | AtCoder 考えたこと 桁DPコンテストの問題として見たので桁DPを考える 使った数をbitで持ってi桁目までで差がもっとも小さい数を持つDPを考える dp[i桁目まで見た][使った数の集合]としてDPをする i…

ABC076 D - AtCoder Express

問題ページ D: AtCoder Express - AtCoder Beginner Contest 076 | AtCoder 考えたこと 各区間で場合分けして見ていくのを考える。サンプルを見ていると無限に場合分けがありそうで確実にバグらせるのでやめる。 現在の速度を持っておいて1秒ごとにシミュレ…

ABC076 C - Dubious Document 2

問題ページ C: Dubious Document 2 - AtCoder Beginner Contest 076 | AtCoder 解法 O(|S||T|)で愚直に探索していく。文字列S内に文字列Tが内包されることがありうるかをこの時点で判定し存在しなければ終了。文字列Tを当てはめるために変換する?以外は全部a…

AGC005 C - Tree Restoring

問題ページ C: Tree Restoring - AtCoder Grand Contest 005 | AtCoder 解法 まず、max(a[i]) = Xの距離のグラフをつくることを考える。このグラフをつくるのに * Xが偶数のとき 距離がX/2の頂点が1個、X/2+1~Xまでの頂点が2個ずつ必要 * Xが奇数のとき 距…

ARC069 E - Frequency

問題ページ E: Frequency - AtCoder Regular Contest 069 | AtCoder 解法 辞書順最小なのでその時点で追加できる最小のものを追加していくようにする。 0 1 2 3 4 5 6 7 8 9 1 2 1 3 2 4 2 5 8 1 -> 8が3(=(8-5)*(8以上の数の個数))回追加 (最大の石の数は8)…

Tenka1 Programmer Contest C - 4/N

問題ページ C - 4/N 考えたこと 何かうまい構成方法でO(1)?と思ったがよくよく考えると全探索できる。誤差死とオーバーフローに気をつけつつ算数をすると通った。 時間かけすぎで反省。 解法 hとnを決めるとwは一意に決まるのでO(35002)の探索をする #inclu…

Tenka1 Programmer Contest D - IntegerotS

問題ページ D - IntegerotS 考えたこと ナップザック問題っぽさを感じる。Kをそのまま配列に持つのは無理なのでbitが立ってる本数を配列に持つのかなあと考えるがうまくいきそうにない。 いろいろ実験してるとKのある桁を1から0にしたとき、それ以下の桁は全…

Tenka1 Programmer Contest E - CARtesian Coodinate

問題ページ E - CARtesian Coodinate 解法 解説を見た。 https://img.atcoder.jp/tenka1-2017/editorial.pdf www.youtube.com まず、N点からのマンハッタン距離の和が最小になる点について考える。マンハッタン距離はx座標、y座標それぞれ独立に足すことがで…

ARC039 C - 幼稚園児高橋君

問題ページ C: 幼稚園児高橋君 - AtCoder Regular Contest 039 | AtCoder 考えたこと 解説を見た。 4方向の近傍だけ持ってればよくて通ったところとその近傍しか情報いらないからmapでうまく持てばO(KlogK)で解ける。linked listを思い出しつつバグらせない…

chokudai contest 001

問題ページ Tasks - Chokudai Contest 001 | AtCoder 唐突にマラソンがやりたくなったのでジャッジが公開されているマラソンのchokudai contest 001を試しにやってみることにした。 6:46 問題を読む グリッドゲーで操作にかかる手数をできるだけ小さくしたい…

ABC074 D Restoring Road Network

問題ページ D - Restoring Road Network 考えたこと 問題を読むとワーシャルフロイドの逆をやるらしい。それぞれの頂点間にA[i][j]の長さの辺があるのを初期状態として、どの辺を減らせるかといった方針で考える。i->k->jと移動した時、A[i][j]と同じコスト…

ARC 081 E - Don't Be a Subsequence

問題ページ arc081.contest.atcoder.jp 解法 まず、dp[i] = (区間[i, s.size())の部分文字列に含まれない最短の文字列の長さ)としたDPを考える。文字cがi番目以降ではじめて現れる位置をnext(i, c)と表記することにすると、このDPはdp[i] = min{dp[next(i, …

TDPD I イウィ

tdpc.contest.atcoder.jp区間DPの問題。AOJ 1161ダルマ落としと似てる。dp[l][r] = {lからrまでの区間で操作をできる回数}としてDPする。 区間lからrで間の区間(l+1からr-2orl+2からr-1)が全て削除でき、削除したあとに残る文字列がiwiならばその区間は全て…