問題 mp3プレイヤーにn曲の曲が入っており、i曲目の名前は "i.mp3" である このプレイヤーは曲名を数字の昇順ではなく文字列の昇順にソートする このプレイヤーの表示順に、 1) n 2) そうでないときは最初の50曲の曲名 を書け1 解法 2桁以下は全部試す 3桁以…

問題 無限に広いグリッド上にロボットがいる 長さnのプログラムが組み込まれており、i番目は「正面にa[i]マス進んでからa[i]*90度右に回れ」という内容 このプログラムをt回実行した後に辿り着くマスと最初にいたマスのマンハッタン距離を求めよ1 1 1 解法 …

ちょっと面白かった 問題 長さmのビット列がn個ある これらのうち2個を選んで機械に入れると、各ビットごとにそれらのor / and / xor和のどれかを計算して出してくれる この機械の各ビットがor / and / xor和のどれを出しているのか特定したい 今あるn個のビ…

問題 n個の箱があり、i番目の箱には赤緑青のボールがそれぞれr,g,b[i]個入っている ある箱からある色のボールを取り出し違う箱に入れるにはコストが1かかる それぞれの箱に入っているボールの色の種類を1以下にするためにかかるコストの最小値を求めよ1 1 解…

問題 整数n,mが与えられる a,bがn,m以下かつ (√a + √b)^2が整数になるような正整数のペア(a,b)の個数を求めよ1 解法 (√a + √b)^2 = a+b + 2√ab だからabが平方数ならokaを全部試す aを平方数で割れるだけ割った結果をa'とする するとこのaとペアにできるbの…

問題 n頂点m辺の無向グラフが与えられる グラフがどんな形になっていても絶対に辺同士が交差しないように辺を削除するとき、最終的なグラフとしてあり得るものは何通りあるか2 1 解法 最終的なグラフは 1) 辺が1本もない 2) 辺が1本だけある 3) 辺が2本以上…

問題 マナオは一人で旅に出た 道中で出会うモンスターはn匹いて、i番目に出会うモンスターの怖さはd[i]で、仲間にするにはp[i]円かかる モンスターに出会ったとき、金を払って仲間にするという選択肢が常にある またはマナオのチームの怖さの合計がそのモン…

チェスサークルの力を発揮 問題 h*wのチェス盤がある 好きなマスにナイトを置いて好きなだけ動かすとき、ナイトが通れるマスの最大値を求めよ1 解法 h h=1: 一度も動けないから答えはスタート地点の1マスのみ h=2: ジグザグに動けばceil(w/2)マス通れる h=3…

問題 長さn(:偶数)の文字列sが与えられる sを2つの文字列x,yに分け、yがxのアナグラムになっているようにしたい xとしてあり得る文字列のうち辞書順最小のものを求めよ2 xとしてあり得る文字列が少なくとも1つは存在することが保証される 解法 1文字ずつ決め…