codeforces.com ある長い数字n(最大10万桁)について、すべての桁の合計はk以上であり、幾つかの桁が書き換えられた数字(桁数は同じ)が与えられる。最小で何桁書き換えられたとかんがえられるか？ 与えられた書き換え済みの数字についてまずは桁の合計を計算…

codeforces.com 2人がタイピングゲームをする。キーの送受信のレイテンシ及び一つのキーを押す時間と、課題の文字列の長さが与えられるのでどちらが勝つか判定せよ。 「レイテンシ * 2 + キーを押す時間 * 文字列の長さ」で比較するだけ。

arc038.contest.atcoder.jp 位置iにある石を移動させるゲームを行う。位置iの石は左に1からC[i]の範囲で好きなだけ動かすことができる位置0にある石はそれ以上移動させることができない。先攻と後攻どちらが勝つか。 まずは位置iに石が1個ある時のGrundy数を…

agc017.contest.atcoder.jp ＋字型の図形の情報が幾つか与えられる(正確な定義は問題文参照)。この図形を下辺が地面にピッタリ付くように並べていく。例えば┴みたいなのは延々と並べていける。与えられた図形をすべて用いてそのように並べることは可能か？ …

arc078.contest.atcoder.jp 公開されない整数Nが存在し、システムに整数nを入力とするクエリを出すと、下記の条件の時Yesが帰ってくる。 n≤N かつ str(n)≤str(N)を満たす n>N かつ str(n)>str(N) を満たす この時、最大64回の質問でNを特定せよ。 まず分かる…

arc078.contest.atcoder.jp 木が与えられる。頂点のうち、1点は白、もう1点は黒、残りは色なしの状態である。先手は白に塗られた頂点から隣接する頂点にだけ、後手は同様に黒の頂点だけ色を塗っていくことが可能である。ただし、既に塗られたところには上塗…

agc017.contest.atcoder.jp 木の根を含まない部分木を交互に取り除いていき、操作ができなくなった(根しかない状態になった)ほうが負けとする。最適な行動を取る時先手後手どちらが勝つか？ Green Hackenbushとかいう有名問題とのこと。明らかにGrundy数であ…

agc017.contest.atcoder.jp 数列A[i]が与えられる。この数列は時刻tにX[i]番目がY[i]に変化する。時刻tでの数列に於いて、「k個の数がある時、kの数字を削除する」という操作を繰り返すことで数列を空にしたい。そのためには時刻tでの数列から何個の数字を変…

arc078.contest.atcoder.jp 数列a[i]が与えられる。|(a[1]+...+a[k]) - (a[k+1]+...+a[N])|を最小化せよ。 a[i]の累積和sum[i]を計算しておくと、(a[1]+...+a[k]) 及び (a[k+1]+...+a[N]) はそれぞれO(1)で計算可能。これでkを全探索すればよい。O(N)。

agc017.contest.atcoder.jp 長さNの数列を構成したい。最初と最後の要素がA, Bで与えられる。また、隣り合う要素同士の差はC以上D以下になるようにしたい。このような構成は可能か？ 最初の要素を除くN-1個の要素について、k個が前の要素以上、N-1-k個が前の…

agc017.contest.atcoder.jp 数列A[i]が与えられるので、部分列をとってその和の余りを0または1にしたい。そのような部分列は何通りあるか？ k番目までの数列の部分列をとったときにあまりが0または1になる組み合わせをa[0][k], a[1][k]とおく。A[k + 1]が奇…

arc007.contest.atcoder.jp 最大10の周期でxoxooxoxxという並びが繰り返す。この周期と同じ周期を幾つか用いて、それぞれ任意の数だけずらして重ねたときに少なくとも1個の○が存在するようにしたい。最小でこの周期を何個使えばいいか。 周期の長さを持つ01b…

arc008.contest.atcoder.jp N人の人が(x[i], y[i])にいる。それぞれ最大t[i]の速度でたこ焼きを投げられ、また最大r[i]までの速度で投げられたたこ焼きをキャッチできる。一人目の人が1秒おきにたこ焼きを投げ、その他の人もたこ焼きを受け取ったらそれを更…

arc077.contest.atcoder.jp 整数xを一つ決める。ある数a[i]に対して、a[i] + 1 またはxに遷移する、という操作を行い、a[1]～a[n]までの遷移を実現する。この操作の回数が最小になるようにxを決めた時、その最小回数を求めよ。 素直にやるとO(NM)の問題で当…

arc077.contest.atcoder.jp 1～nの数で構成された、n+1個の数列が与えられる。この数列の中で、1～nはそれぞれ少なくとも1回以上は登場する。この時、長さ1～n+1の部分列で、異なる個数の総和を求めよ。 要はある数が一つだけダブっており、それ以外は全部1…

arc077.contest.atcoder.jp 数列a[i]が与えられる。このa[i]とある空の別の数列b[j]について、bの末尾にa[i]を加え、bをreverseする、という操作をすべてのa[i]について繰り返す。最後にできる数列を求めよ。 毎回Reverseするのではなく、Nが偶数なら最後に…

arc076.contest.atcoder.jp RxC の平面内に (x1[i], y1[i]) (x2[i], y2[i]) の座標のペアが幾つか与えられる。このペア同士で線を引きたいが、それぞれの線が交差してはならない。そのような引き方が可能かどうか判定せよ。 まず、両方の点のいずれかが周囲…

arc076.contest.atcoder.jp 座標(x[i], y[i])に街がある、街間に道路を引くためにはx座標の差またはy座標の差の小さいほうの距離だけコストがかかる。いくつか道路を引いて全部の街を行き来できるようにするための最小コストはいくつか？ 最小全域木を求めれ…

arc076.contest.atcoder.jp 犬がN匹、サルがM匹いる。犬同士、サル同士が互いに隣り合わない並びかたは何通りか？ |N - M| > 1 の場合は0通り。 |N - M| == 1 のときは、xoxoxoxox という並び順しかありえないのでN! * M! 通り。 |N - M| == 0 のときは、oxo…

agc016.contest.atcoder.jp H行W列の整数値のテーブルで、h行w列の部分区画の和はすべて負、かつテーブル全部の要素の和が正であるようなテーブルは存在するか？するなら具体例を示せ。 具体的な構成を色々試すと、右下の角1マスだけ負、それ以外は正である…

agc016.contest.atcoder.jp N匹の猫が色付き防止をかぶっている。それぞれの猫は自分以外の猫の帽子の色がa[i]種類あるといっている。このような組み合わせは存在するか？ ある猫に注目したときにその猫をカウントする・しないで最大1種類しか違わない。よっ…

agc016.contest.atcoder.jp アルファベット小文字からなる文字列がs[i]で与えられる。新しい文字列のi番目の文字をs[i] or s[i + 1] のいずれかを選んで構成する、という作業を行う。この作業を何回か繰り返して全ての文字が単一のアルファベットで構成され…

code.facebook.com Facebook Research Blogに面白いAIの記事が出ていました。自然言語(英語)で交渉をするAIを作ってみたという記事です。シチュエーションとしては、2者がそれぞれ何個かのアイテムを所持しており(公開情報)、それぞれのアイテムに2者それぞ…

arc075.contest.atcoder.jp 数列が与えられる。連続部分列の平均値がK以上であるような部分列は何通りあるか？ まずすぐ分かることはすべての要素からKを引くと、部分列の和が0以上になるような組み合わせをカウントすればよい。これはO(N^2)であれば、累積…

画像認識 (機械学習プロフェッショナルシリーズ) 作者: 原田達也 出版社/メーカー: 講談社 発売日: 2017/05/25 メディア: 単行本（ソフトカバー） この商品を含むブログを見る 比較的新しい画像認識の本。ただ構成が独特で、画像認識の一般論といった基礎を…

arc075.contest.atcoder.jp 魔物の体力s[1]～s[N]が与えられる。一回の魔法攻撃で、特定の一つの魔物の体力をA削り、その他すべての魔物の体力をB削る。ただしA>Bとする。全滅させるには魔法攻撃を最低何回打てばよいか？ C=A-Bとする。魔法攻撃の回数をkと…

codeforces.com 木の2個の頂点にAさん及びBさんがいる。AさんがBさんを追いかけ、BさんはAさんから逃げるという目的で行動を最適化するとき、AさんがBさんに追いつく手数を求めよ。その場にとどまるのもありとし、Bさんが先手とする。 Aさん及びBさんがいる…

No.524 コイン - yukicoder N(0

codeforces.com n階m部屋と両脇に階段(よって全体の幅はm + 2)の建物がある。最初は1階の左はじにいる人が各階の電気をすべて消し、上にのぼる、次の階もすべて消し上にのぼる…を繰り返してすべての部屋の電気を消す。最初に点いている部屋が与えられる時、…

No.520 プロジェクトオイラーへの招待 - yukicoder 三角形の各辺について、a個、b個、c個の内分点が与えられる。頂点及び内分点同士で直線を互いに交わらないように引けるだけ引く。線の引き方は何通りあるか？ 真ん中に三角形ができるパターンと出来ないパ…