問題 nxnのマスに1～nまでの数字がn個ずつ割り振られている。同じ数字が割り振られているマスがすべて4-連結しているか判定せよ。入力形式が少しわかりにくくて、各テストケースのi行目が数字iを持つマスのy座標、x座標を連続で表している。テストケースはn-…
問題 グラフ上のノード番号が2つずつ入力される。前者から後者のノードへは有向辺が伸びているものとする。このグラフがひとつの木になっているか判定せよ。なお入力は複数のテストケースからなり、0 0がそのケースの入力の終わりを表し、2つとも負の数が与…
問題 n x mの市松模様が与えられる。右下が白の場合はc = 1、黒の場合はc = 0である。 8 x 8のチェスボードはこの中にいくつあるか返せ。 やりかた チェスボードを模様の中で動かすことを想定すると、チェスボードの左上が動ける範囲は、模様の左上から(n - …
問題 n(1自然数の個数を求めよ。 やりかた 包除原理。 nの素因数p[]を求めておく。するとnと互いに素でないn未満の自然数の数は、をn未満のp[i]の倍数の集合とするとで求めることができる。これは包除原理をもとにすぐ計算できる。(Kはnの素因数の個数)以下…
問題 素因数が2,3,5,7のみであるものをHumble Numberという。n番目のHumble Numberを出力せよ。(1 やりかた setにhumble numberを突っ込んでいって一番小さいものから取り出してそれらに2,3,5,7をかけてもう一度setに突っ込んで、また一番小さいものから取り…
問題 N人にM枚ずつカードが配られる。カードには1〜N*Mまでの数字が書かれており、重複はない。各人は毎ターン一枚のカードを場に出し、一番数字の大きいカードを出した人がそのターンの勝ちになる。あなたに配られたカードがわかっているとき、あなたが最低…
問題 素数が2つ与えられる。素数のいずれかの桁の数字を一つ書き換えて別の素数に変える操作を、与えられるひとつ目の素数から始めて、ふたつ目の素数に到達するまで行う。最短の操作回数を求めよ。ただし与えられる素数はともに4桁の素数で、経由する素数も…
問題 マジシャンが1からnまでの数字が書かれたn枚のカードを次のような手順で場にディールしていく。1回目はカードデッキの一番上の1枚をデッキの一番下に移し、新たに一番上になった一枚をディール。 2回目はカードデッキの一番上の2枚をデッキの一番下に移…
問題 symbol = valueという形で変数が与えられるので、その変数を解に持つ最も簡素な形式の数式を出力せよ。 やりかた 最も簡単な形式はsymbol = valueという式そのもの以外にないのでそのまま出力すればいい。要は標準入力をそのまま標準出力にだせばいいだ…
問題 2以上10000以下の整数nが与えられる。nを連続する素数の和で表したい。何通りの方法があるか求めよ。素数一つで表せる場合も該当する。 やりかた エラトステネスの篩をして10000以下の素数の数列を求めておき、それらの部分数列の和を全列挙して該当す…
問題 4以上の整数は2つの素数の和で表せる、という予想をゴールドバッハ予想という。4以上2^15以下の整数nが与えられるので和がnとなるような素数の組数を返せ。ただし(p1,p2)という組と(p2,p1)という組を別々に数えてないけない。 やりかた エラトステネス…
問題 1x1x1のサイズの立方体の展開図が文字列として与えられる。'#'はそこが1x1のサイズの面であることを表し、'.'は面ではないことを表す。 この展開図は正しい展開図であるとは限らない。そこで文字列が与えられた時、正しい展開図となっているかを返せ。 …
問題 2000年1月1日からの経過日数が与えられる。何年何月何曜日か出力せよ。 やりかた 2000年からはじめて、その年の日数を計上していき与えられた数を超える年が答えとなる年。（コードでは数から日数を引いていき0以下になるとこで止めている） で、与えら…
問題 i i >= 1 の場合、 で定義される数列がある。はxの床関数である。 を返せ。 やりかた 単純なメモ化再帰で通る。ただしすべてメモするとMLEなので100万くらいまでメモっておいてそれ以上大きい場合は、再帰を繰り返して計算するようにすると通る。以下ソ…
問題 連結な有向グラフが与えられる。ある頂点から再びその頂点に戻るような長さxのパスが存在するときxはvacation friendlyであるという。途中で頂点に一度戻るようなパスも可とする。 xを1から無限まで調査し、vacation friendlyなら1、そうでないなら0と…
問題 高さr、幅cの長方形の盤面がある。(1,1)のコマから右隣か上に移動を繰り返してゴールの(r,c)まで行きたい。盤面には特別なコマがいくつかありそれらの位置はfieldrow、fieldcolで与えられる。ゴールに行くまでに特別なコマをx個通る手順数を1000007で割…
問題 #か.で描かれた絵がある。#と#が上下左右で隣り合っているとき、それらは接しているといい、接している#の集合を一つの連結成分ということにする。同じ連結成分に属している2つの#には道のりが定義でき、一方の#からもう一方の#までたどり着くまでに経…
問題 円周上にノードが配置してあり、時計回りに1からNまでの番号が振られている。数字iのノードからはiの各桁の数字の和だけ時計回りに進むことができる。あるノードからスタートして移動中にすでに訪れたノードについたら終わりとする。任意のノードからス…
問題 XY座標上で点が与えられる。全ての点が少なくとも1つ以上の多角形に属するように多角形を配置する。それらの面積の和が最小となるように配置し、その和を返せ。多角形の頂点は常に与えられた点の上にしか置くことはできない。与えられた点は多角形の辺…
問題 1x1のタイル、もしくは1x1の障害物で構成されたサイズが10x10以下の部屋が与えられる。この部屋を1xNの棒で敷き詰めたい（Nは任意の正整数）。棒は部屋の幅もしくは奥行きに対して平行にしか置くことができず、一つのタイルに対して重複して置くことは…
問題 無向グラフが与えられる。各頂点は白か黒の色で塗られており、辺は異なる色の頂点間でのみ張られている。このグラフ上で次の手順でゲームを行う。 白と黒が交互に行い、初手は白である。 白のターンでは各黒の頂点にその頂点と隣接する白の頂点の点数を…
問題 折れ線グラフが以下の形式で1つ以上与えられる。互いに交差している折れ線グラフを1つの集合と数えると、いくつの集合になるか。1つの折れ線は1つ以上の線分からなり、点同士は'-'で区切られ、点は','で区切られる2つの非負整数で表現される。' 'で区切…
問題 やりかた 以下ソース。 class ArithmeticProgressions { public: ll N, m, M; vector<ll> s; ll floor(ll a, ll b){ ll m = a % b; if(m < 0) m += b; return (a - m) / b; } ll ceil(ll a, ll b){ ll m = a % b; if(m < 0) m += b; if(m > 0) m = b - m; r</ll>…
問題 複数の男女がいる。かれらのお互いの友好度がpreferencesとして与えられる。preferences[i][j]が'1'のとき男iと女jは結婚に適しており、'0'のときは適していない。一夫多妻型か多夫一妻型の結婚が認められている（多夫多妻制は不可）ときにすべての男女…
問題 整数Nが与えられる。好きな桁を2つ選んで、それらの数字を1つずつ減らしてそれらを交換するというゲームを行う。このゲームでとりうる最も大きい数字を求めよ。なおLeading Zeroができてはいけない。 やりかた ゲーム中に桁が増えるようなことはなく、…
問題 足場をジャンプして渡り、コインを集めるゲームがある。足場の位置とそこにおいてあるコインの枚数が与えられる。 ゲームでは今いる足場からy座標上で下にある足場にしか移動はできない。足場は点として考えて良い。ジャンプには物理法則があり、ジャン…
問題 3つの自然数a,b,cが与えられる。これらを2進数表記にした際に、最も大きい桁数を持つ数字と桁数が同じになるように残りの2つにleading zeroを足す。これらの数字について2進数上で1と0の順番を好きに入れ替えることで新たな数字a',b',c'を作る。なおlea…
問題 1からNまでの高さを持つ、N棟の建物が一直線上に並んでいる。これらを左端から眺めた時に、i番目の建物が見えるというのは、0〜i-1番目の建物がi番目の建物より低い時である。右端から眺めた時に見える場合はi+1〜N-1番目の建物がi番目の建物より低い時…
問題 何人かが円状に位置しており、一つのボールを互いに当て合うゲームをする。プレイヤーはボールを持っている時、自分以外の人を狙うものとし、i番目のプレイヤーがボールをもっている時に、このプレーヤーが狙った相手に当てることのできる確率はprobabi…
問題 QWERTYキーボードにおいてキーとキーの距離とは隣接するキーをいくつ隔てて到達できるかによる。ただしスペースキーと隣接するキーとの距離は3と数える。（詳細は問題文中の図）"month day"という形式で日付が与えられる。この日付はミスタイプされてい…
