裏紙

ほぼ競プロ、たまに日記

AtCoder

ARC 068 E - Snuke Line

問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 問題概要 個の駅があり、駅に対してからまでの番号が振られている。列車は駅から駅ごとに停車する。また、種類の名産品があり、番目の名産品は駅から駅の区間で売られており、その駅に停まると…

ARC 064 F - Rotated Palindromes

問題 F: Rotated Palindromes - AtCoder Regular Contest 064 | AtCoder 問題概要 長さの数列としてあり得るものを全て用意する。ただし、は は回文(つまりとの逆順に並べたものは一致) という条件を満たす。このようにして得られたに対して、「先頭の要素を…

CODE FESTIVAL 2016 Final E - Cookies

問題 E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを…

CODE FESTIVAL 2016 Final G - Zigzag MST

問題 G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 頂点が個のグラフがあり、からまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリが個来る。 頂点番号とと重みが与えられて、 とに重みの辺を張る…

AGC 005 D - ~K Perm Counting

問題 D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder 問題概要 長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。 アイデア 答えを直接求めに行くのではなく、余事象を求めることにする。つ…

AGC 003 D - Anticube

問題 D: Anticube - AtCoder Grand Contest 003 | AtCoder 問題概要 要素数の重複を許す整数の集合が与えられる。この集合の部分集合の中で、その部分集合のどの2つの要素の積も立方数にならない部分集合の最大のサイズを求めよ。 アイデア まず、2数をかけ…

ARC 060 E - 高橋君とホテル / Tak and Hotels

問題 E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder 問題概要 件のホテルが一直線上に並び、座標はで与えられる。一日に移動可能な距離の上限がである。次のようなクエリが個与えられるので、各クエリに答えよ: 一日ごとに…

ARC 059 F - バイナリハック / Unhappy Hacking

問題 F: バイナリハック / Unhappy Hacking - AtCoder Regular Contest 059 | AtCoder 問題概要 キーボードには0,1,Bの3種類のキーがある。Bは空文字列でなければ末尾の一文字を削除する。このキーボードのキーを回押して文字列を入力したい時、入力方法は何…

ARC 043 C - 転倒距離

問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder 問題概要 からまでの整数を並び替えたものをサイズの順列として,サイズの順列とに対して,その2つで順序が入れ替わっている数字の組の個数をとの転倒距離とするときに,ともとも転倒距離の等しい…

ARC 024 C - だれじゃ

問題 C: だれじゃ - AtCoder Regular Contest 024 | AtCoder 問題概要 長さの文字列がある.この中から長さの連続する部分文字列を2つ取り出して,アナグラムになっている位置があるかどうか判定せよ. アイデア 文字列内の文字はアルファベット小文字のみな…

ARC 019 C - 最後の森

問題 C: 最後の森 - AtCoder Regular Contest 019 | AtCoder 問題概要 の広さのグリッド上を村からスタートしほこらを通ってから城に向かいたいが,特定のマスには強敵がいて,そのマスに止まると戦闘が起こる.強敵との戦闘は回以内に抑えたい(戦闘が終わっ…

ARC 058 E - 和風いろはちゃん / Iroha and Haiku

問題 E: 和風いろはちゃん / Iroha and Haiku - AtCoder Regular Contest 058 | AtCoder 問題概要 長さの数列を考える.数列の各要素について,値は1以上10以下である.数列がXYZを含むものは何通り有るか答えよ. ただし,XYZを含むとは: を満たすが存在す…

ARC 025 C - ウサギとカメ

問題 C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder アイデア 方針はすぐに思いついたけど、実装でバグらせまくって時間かかったのでメモ。 まず、各頂点どうしの最短経路を求めておいた方がよさそうだな、と思いワーシャルフロイドだとかかって…

Typical DP B - ゲーム

問題 B: ゲーム - Typical DP Contest | AtCoder 簡潔なのでまとめなくていいかと。 アイデア ゲームが進行し、Aの山の一番上がa[x]、Bの山の一番上がb[y]になっている状況を考える。 dp[x][y] := (上記のような状況での先手が取れる価値合計の最大値)として…

CODE FESTIVAL 2014 決勝 - E : 常ならずグラフ

・概要 E: 常ならずグラフ - CODE FESTIVAL 2014 決勝 | AtCoder数列が与えられるので、大小がジグザグになるように数列の要素をいくつか削る。その削って条件をみたすようになったグラフのうちで要素が最も多いものの要素の個数を求める。・アイデア 数列の…

ABC 030 - D: へんてこ辞書

・問題 D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder・アイデア まず、色々例とかを紙に起こしてみて有向グラフみたいイメージで考えられるんじゃないかって思った。 そして、かならず1つはループが生じるということもわかった。なぜなら木に…

ABC 029 - D: 1

・問題分 D: 1 - AtCoder Beginner Contest 029 | AtCoder・アイデア 各桁ごとに数字の現れ方に規則性があるから桁ごとに注目して数え上げればいいじゃんってのには気づいたけどそれをうまく実装できなかった。解説スライド(http://www.slideshare.net/choku…

ARC 043 - B: 難易度

・問題 B: 難易度 - AtCoder Regular Contest 043 | AtCoder・感想 これはDPだなーとコンテスト中に問題見て思った。しかも私でもすぐ気づく感じなので、割と典型な感じの。ただ、DPを実装するにあたって、私はメモ化再起でしか書けなくて、dpの配列をforル…