問題 Editorial 問題 A004201は、任意の(等差, 長さ)の等差数列を含む(飛び飛びでも含んでいるとする)。 与えられた(等差delta, 長さn)に対して、最初に現れるその等差数列の初項を求めよ 2 1 解答 EditorialとPractice Roomのrng_58さんの解答を参考にした…

問題 Editorial 問題 マップでスタート地点からゴール地点まで行きたい。 マップには空白・壁、回転ドアがあり、回転ドアは 1 2 | -O- → 5O6 3 4 | の図のように、1,3の位置から5の位置まで、2,4の位置から6の位置まで行く事によって回転できる。 縦になった…

https://twitter.com/anta_prg/status/281025745768288256 問題 今位置0に居て、ある位置[K,K+M-1](K,M≦10^10)の範囲に止まる必要がある。 カードがN(≦40)枚、それぞれに数値とコスト(≦10^9)が書かれていて{捨てる・数値だけ進む}ことができる。 コストを最…

問題 Editorial 問題 ゲームをする。プレイヤーがN人いて、常に一列に並んでいる。 kingと呼ばれるプレイヤーが各ターンに一人いる。 kingは次のプレイヤーとテニスの対戦をしていき、kingが勝ったなら、対戦相手は列の一番後ろに移動し、次のプレイヤーとま…

問題 Editorial 問題 xとyからなる文字列に対して、いつでも 含まれる"yyyyyy"を削除する 含まれる"xxxxxxxx"を削除する 含まれる"xy"を"yyyyyx"に置換する という操作ができる。 文字列Aに操作を0回以上繰り返してBにできることを(A ⇒* B)と書くとき、関係~…

問題 Editorial 問題 サイズNの順列がある。「ある位置とある位置のswap」という操作をして[0..N-1]からその順列にしたい。 ただし、操作をする時にswapする2つの要素に対応したコストweightsがかかる(2つの要素のそれぞれのコストの和がかかる)。 コストの…

問題 Editorial 問題 今ここに、Nつのそれぞれentrees[i]円の料理がある。 また、M人の人がいてそれぞれの人に対して、好きな料理(0 1 1 解答 分割統治法。 半分にわけて、まず片方を全列挙する。そして人々の状態にたいしての最小コストをメモっとく。 次に…

問題 Editorial 問題 フォーラムによると、 この問題は非常に誤読しやすいように書かれているらしい。実際自分も誤読していた 解答 まだ理解できていない。 フォーラムを読んだ。 漸化式になるようだが、どうしてそうなるかわかってない。 コンビネーション…

問題 Editorial 問題 今位置0に荷物がNつある。 この荷物たちをそれぞれ指定された位置boxesに移動したい。 移動するのに2つの方法がある。 一つ目がテレポート。これは複数の荷物をまとめて、任意の位置へ移動できる。ただし1回に1つの位置にしか移動できな…

問題 Editorial 問題 二人でゲームを行う。このゲームにはNつの山があって、それらは非負整数を記憶する。初期状態がpilesで与えられる。 プレイヤーは各ターン、次の動きを行う。 「(0 ただしそのとき、i番目の山は1以上でなくてはならない。 また、j = kで…

問題 Editorial 問題 平面上に一本の道がある。これは終点が次の始点となる有向線分(roadX,roadY)をつなげた形で、交差・接触はしない。 この道の始点から終点までを最小時間で移動したい。 道にそって走る時は単位距離に対して単位時間かかる。ただし道の向…

http://arc010.contest.atcoder.jp/assignments ARCは今の自分にとってちょうどいい難易度(うまくいったら全完程度)で楽しいです Coding A シミュる B やる。 振替休日はカウンタを持っておくといい C (何番目か * 一つ前の色 * 2^mで出た色)でDP。 メモリが…

問題 Editorial 問題 略 解答 他の人の解答を読んだ。 嘘枝狩りしたら普通にやっていけるようだ コメント 最初問題読めてなかった。 EditorialにはTrieとか書いてある。 嘘枝狩りとかも柔軟に使えるようになりたいねえ コード #include <string> #include <vector> #include <algorithm></algorithm></vector></string>…

問題 Editorial 問題 簡単な言語のプログラムが与えられる。そのプログラムの関数・変数の型を決定しろ 解答 まずがんばって構文解析する。 型の決定はUnion-findでやった。 コメント 構文解析苦手だなあ。無理に全部を1-passでやろうとして変なふうにしてた…

問題 Editorial 問題 円弧の4分の1の動きで、与えられたマップgridのブロックに当たらないように進むことが出来る。 ただし点のみで当たっている場合はOK。 最小の移動数を求めよ 1 解答 まず、円弧がどこを通るかは、x^2+y^2=r^2を変形してlower_boundとupp…

問題 Editorial 問題 ヒルベルト曲線を順番通りに書け 解答 WikipediaのRepresentation as Lindenmayer systemを参考にして書いた コメント 32*32までだし、埋め込みとかもありだ コード #include <string> #include <vector> using namespace std; typedef vector<string> vs; struc</string></vector></string>…

問題 Editorial 問題 略 解答 二分探索する コメント 簡単なのにバグらせて無駄に時間かかってしまった コード #include <string> #include <vector> #include <sstream> #include <cstring> #include <limits> #include <complex> #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define reu(i,l,u) for(i</complex></limits></cstring></sstream></vector></string>…

https://github.com/anta-/kawigi-tekito-

問題 Editorial 問題 □□ □という形のブロックが無限にある。ブロックは自由に(90度単位で)回転できる。 length*widthの長方形にぴったり詰め込みたい(空白の部分があってはいけない)。 その「場合の数」を答えよ。ただし、対称の形でも別に数える 1 1 返り値…

問題 Editorial 問題 H*Wのマップlevelがある。マップの各セルには数字が書いてある。 左上(0, 0)から右下(W-1, H-1)へ、右か下のセルを辿っていく動きができる。このとき、たどったセルの数字がスコアに加算される。 3回上記の動きをするとき、得られるスコ…

問題 Editorial 問題 上下左右に無限に広がったチェス盤がある。 今、ナイトは(0, 0)にいて、標準のナイトの動きをすることができる。 点が複数(pieces)与えられた時、全ての点に行く動きの最小数を求めよ 1 -1000000 解答 まず巡回セールスマン部分は全探索…

問題 Editorial 問題 HexMapがあって、座標が2つ与えられる。 その点と点を結ぶ線分と交差する6角形の数を答えよ。 ただしエッジの上にオーバーラップする場合や、角の1点だけで触れる場合はカウントしない 10000 解答 Editorialを読んだ。 まず、座標を斜め…

Coding Easy (250) 場合分けした。簡単に証明できたし Medium (500) 場合分けしてSum計算ーとかやってたら全然出来なかった DPかー…しかし難しいなあ… なるほど、何番目かを持って、k番目のときに判定してさらに最後までやる感じか！ なるほどー。この形は思…

問題 Editorial 問題 数列segmentsが与えられる。何個かを組み合わせて、和を特定の数desiredLengthにしたい。 組み合わせる数を最小にせよ。 1 1 1 解答 Exact-Knapsack。半分全列挙する。 2^(N/2)*N/2でできる。 このやり方は最初は意味不明だったが、しっ…

問題 Editorial 問題 数列countriesと数値kが与えられる。 [0,|countries|)の中から重複なしでkつ選んだものの数を最大化せよ。 ただし、iはcountries[i]個までしか使えない。 2 k 1 解答 Editorialを読んだ。 単純に作る数を二分探索すればよい。 判定は(Su…

問題 Editorial 問題 長方形Aが一つ与えられる。 別の長方形Bが与えられ、それを幾つか置いて先の長方形Aを被覆したい。 ただし、置くのに、与えられた角度だけ回転させて置かなければならない。 置く長方形の数を最小化せよ。 -100 0 角度が0と90以外なら、…

問題 Editorial 問題 数列xs(1 このとき、(\ys xs-> sum. zipWith (*) ys xs)が0より大きく、かつ最小となるような数列を求めたい。 これを辞書順最小で返せ。ただし、要素の大きさは、絶対値が小さい方が小さく、絶対値が同じなら正の数のほうが小さいとす…

問題 Editorial 問題 ある性質をもって走る犬がいる。 木にぶつかるまでの間、点(0, 0)を中心とした円周上を時計回りに走る 木にぶつかった場合、上記の動きができるようになる位置まで、木にそって反時計回りに走る 犬が点(startx, starty)から走り始める時…

問題 Editorial 問題 クラスが複数個ある( 「クラス複数個中からxつ以上のクラスを取る必要がある」という要求が複数( 全ての要求を満たしたい。 ただし、クラスは一つの要求にしか使うことができない。 また、既にとっているクラスが複数個与えられて、それ…

SRM、DIV1のEasy,Mediumを(抜けはあるが)200番まで見終わった (見た問題の表)。 SRM200番台のMediumの難易度と今のEasyの難易度同じくらいじゃね？というほどに、今のSRMは昔と比べて難しくなっている気がする。 これからは200番台から昇順に、Hardを解いて…