AtCoder
問題 H - Doki Doki Programming Clubs! 問題概要 個の数列が与えられる。 番目の数列の長さはである。 クエリとは以下の通り： 数列について、をで割った余りを答える 上記のクエリが個与えられるので、各クエリについて答えよ。 アイデア まず、クエリにつ…
問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 問題概要 個の駅があり、駅に対してからまでの番号が振られている。列車は駅から駅ごとに停車する。また、種類の名産品があり、番目の名産品は駅から駅の区間で売られており、その駅に停まると…
問題 F: Rotated Palindromes - AtCoder Regular Contest 064 | AtCoder 問題概要 長さの数列としてあり得るものを全て用意する。ただし、は は回文(つまりとの逆順に並べたものは一致) という条件を満たす。このようにして得られたに対して、「先頭の要素を…
問題 E: Cookies - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 はじめ、1秒に1枚のクッキーを焼くことが出来る。そして、クッキーを全て食べつくすという行動を取ることが出来る。枚数に関わらず、これには秒かかる(食べている間はクッキーを…
問題 G: Zigzag MST - CODE FESTIVAL 2016 Final (Parallel) | AtCoder 問題概要 頂点が個のグラフがあり、からまで番号が順に付けられている。初期状態で辺は無く、以下のような辺追加クエリが個来る。 頂点番号とと重みが与えられて、 とに重みの辺を張る…
問題 D: ~K Perm Counting - AtCoder Grand Contest 005 | AtCoder 問題概要 長さの順列がある。について、を満たすような順列は何通りあるか、答えを (素数)で割った余りを求めよ。 アイデア 答えを直接求めに行くのではなく、余事象を求めることにする。つ…
問題 D: Anticube - AtCoder Grand Contest 003 | AtCoder 問題概要 要素数の重複を許す整数の集合が与えられる。この集合の部分集合の中で、その部分集合のどの2つの要素の積も立方数にならない部分集合の最大のサイズを求めよ。 アイデア まず、2数をかけ…
問題 E: 高橋君とホテル / Tak and Hotels - AtCoder Regular Contest 060 | AtCoder 問題概要 件のホテルが一直線上に並び、座標はで与えられる。一日に移動可能な距離の上限がである。次のようなクエリが個与えられるので、各クエリに答えよ： 一日ごとに…
問題 F: バイナリハック / Unhappy Hacking - AtCoder Regular Contest 059 | AtCoder 問題概要 キーボードには0,1,Bの3種類のキーがある。Bは空文字列でなければ末尾の一文字を削除する。このキーボードのキーを回押して文字列を入力したい時、入力方法は何…
問題 C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder 問題概要 からまでの整数を並び替えたものをサイズの順列として，サイズの順列とに対して，その2つで順序が入れ替わっている数字の組の個数をとの転倒距離とするときに，ともとも転倒距離の等しい…
問題 C: だれじゃ - AtCoder Regular Contest 024 | AtCoder 問題概要 長さの文字列がある．この中から長さの連続する部分文字列を2つ取り出して，アナグラムになっている位置があるかどうか判定せよ． アイデア 文字列内の文字はアルファベット小文字のみな…
問題 C: 最後の森 - AtCoder Regular Contest 019 | AtCoder 問題概要 の広さのグリッド上を村からスタートしほこらを通ってから城に向かいたいが，特定のマスには強敵がいて，そのマスに止まると戦闘が起こる．強敵との戦闘は回以内に抑えたい(戦闘が終わっ…
問題 E: 和風いろはちゃん / Iroha and Haiku - AtCoder Regular Contest 058 | AtCoder 問題概要 長さの数列を考える．数列の各要素について，値は1以上10以下である．数列がXYZを含むものは何通り有るか答えよ． ただし，XYZを含むとは： を満たすが存在す…
問題 C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder アイデア 方針はすぐに思いついたけど、実装でバグらせまくって時間かかったのでメモ。 まず、各頂点どうしの最短経路を求めておいた方がよさそうだな、と思いワーシャルフロイドだとかかって…
問題 B: ゲーム - Typical DP Contest | AtCoder 簡潔なのでまとめなくていいかと。 アイデア ゲームが進行し、Aの山の一番上がa[x]、Bの山の一番上がb[y]になっている状況を考える。 dp[x][y] := (上記のような状況での先手が取れる価値合計の最大値)として…
・概要 E: 常ならずグラフ - CODE FESTIVAL 2014 決勝 | AtCoder数列が与えられるので、大小がジグザグになるように数列の要素をいくつか削る。その削って条件をみたすようになったグラフのうちで要素が最も多いものの要素の個数を求める。・アイデア 数列の…
・問題 D: へんてこ辞書 - AtCoder Beginner Contest 030 | AtCoder・アイデア まず、色々例とかを紙に起こしてみて有向グラフみたいイメージで考えられるんじゃないかって思った。 そして、かならず１つはループが生じるということもわかった。なぜなら木に…
・問題分 D: 1 - AtCoder Beginner Contest 029 | AtCoder・アイデア 各桁ごとに数字の現れ方に規則性があるから桁ごとに注目して数え上げればいいじゃんってのには気づいたけどそれをうまく実装できなかった。解説スライド(http://www.slideshare.net/choku…
・問題 B: 難易度 - AtCoder Regular Contest 043 | AtCoder・感想 これはDPだなーとコンテスト中に問題見て思った。しかも私でもすぐ気づく感じなので、割と典型な感じの。ただ、DPを実装するにあたって、私はメモ化再起でしか書けなくて、dpの配列をforル…
