最近，500が解けてないぞ．．．

問題 N都市ある。各都市間を繋ぐ道が隣接行列として与えられる。各道には優先度があり、AB間の道は「A 考え方 優先度が高い全域木を見つけ、それがM本以下ならば、残りの道の優先度の高いものから全域木に追加する。もしM本のグラフができたらそれの次数の配…

前にやってたけど、解きなおした。 問題 整数Nが与えられる。各桁の積がNとなる最小の正の整数Xの桁数を返す。もし存在しなければ-1を返す。 考え方 各桁は2から9までしかありえないので、Nを素因数分解して、それ以上の数値が含まれていれば存在しない。 9-…

問題 ある呪文が与えられる。これは暗号化されている。しかし、この暗号は簡単で、呪文のAとZだけを取り出した文字列を逆に並び替えて、順番にもとのAかZの場所に入れなおすことで復号化できる。復号化した文字列を返す。 考え方 やるだけ。 元の文字列のAか…

問題 5x5のボードに5個以下のピースが置いてある．このピースを上下左右に動かして，すべてのピースがくっついて1つの塊になるようにしたい．最小で何回動かせば1つの塊にすることができるか． 考え方 メモ化bfsで，ピースの位置を変えながら探索． 一つの塊…

問題 壊れたロボットがある．このロボットはnステップランダムに進む．東西南北それぞれに進む確率が与えられるとき，ロボットが直線的(すでに通った場所を通らないの意味)に進む確率を求める． 考え方 dfsで通った場所をメモしながらそれぞれの方向に動いた…

問題 aがnのproper factorとは，nがaの倍数で，aは1かnではないものである．あるnの全てのproper factorの配列が与えられるので，当てはまるnを返す． 考え方 1とn以外の全てのproper factorが与えられるので，1,{proper factor},nはnの約数となる． 約数の…

問題 機械がカードの束のシャッフルする。このシャッフルは1〜maxShuffles回行われた後で各プレイヤーに配られる。あるチートプレイヤーがこのシャッフルの仕方が毎回同じだと突き止めた。そして、彼は最初のカードの並びを自由に変えられる。カードの中でK…

問題 N人でトーナメントを行う。それぞれ番号1から並んでいて隣の人と戦う。もし奇数の時は一番最後の人が不戦勝で次のラウンドに進む。あなたの番号とライバルの番号が与えられた時、どちらも勝ち続けたとして第何ラウンドで戦うことになるかを求める。 考…

問題 ある惑星の宇宙人がカレンダーを作る。一日がdayLengthの長さで、一年はyearLengthの長さである。この長さはそれぞれ、その惑星が一回りする長さ、太陽を一周する長さである。しかし、通常、dayLengthの整数倍が一年とはならない。これを閏年を用いて調…

問題 女の子が好きな男の子のうち一人と付き合いたい。そこで、愛の確率を計算してその確率が高い男の子と付き合うことにした。愛の確率は、 L,O,V,Eをそれぞれ、2人の名前に含まれるL,O,V,Eの数とする 愛の確率は( (L+O)*(L+V)*(L+E)*(O+V)*(O+E)*(V+E) )%1…

問題 aがn個とzがm個により構成される文字列が辞書順に並んでいる．k番目(1-based)にくる文字を返す．もし，kが文字列の個数を超える場合は空文字列を返す． n,m 考え方 いくつかパターンを書いてみると気付く．k番目の文字列の先頭にくる文字は，kが{n+m-1}…

問題 ある文字列が与えられる．その文字列の文字を入れ替えることができるとき，2回以上連続して同じ文字がならばないような文字列の個数はいくつ作れるかを返す． 考え方 その文字列で使われている文字の個数を文字ごとにカウントしていって，dfsで作れるか…

問題 ある文字列が与えられる．その文字列にいくつか文字を後ろに追加して回文となる最小の文字列のサイズを返す． 考え方 ポインタ的にやると間違いやすいので，文字列の最後に部分文字列substr(0,i)をreverseしたものを追加して，それが回文になっているか…

問題 複数レーンのある高速道路の車の出る順番を考える．それぞれの車は次のルールを守る． 1.前に車がいる時はその車は出られない 2.低い番号のレーンの車が出ようとしている時はその車は出られない 3.レーンの先頭にきたら，正確に1回は高い番号のレーンの…

問題 width*lengthのブロック部屋で構成される宮殿がある．その長方形の左下から右に向かって進みだす．もし，端やもう通ったブロックにぶつかったら左に向きを変えて進む．最後のブロックの座標を返す． 考え方 シミュレーションするだけ．

問題 いろんな色のビー玉が箱に入っている．それぞれの色ごとのビー玉の個数が与えられるとき，n個連続で同じ色のビー玉を取り出す確率を求める． 考え方 サンプルにある通りに，それぞれの色について，その色のビー玉の個数aがn個以上ある場合，すべてのビ…

問題 N点を平面におくことができる．(点を結んだ線分が軸に平行な)異なる正方形は最大いくつつくれるか． 考え方 どのように点を配置していった場合，正方形が多く作れるかを考える． 点の数が4,9,16,25,...の時はそれぞれ2*2,3*3,4*4,5*5,...の(その中を点…

問題 ある半径rの円上の整数点(x,y)がいくつあるか． x^2+y^2=nのとき，その個数は4*( d_1(n)-d_3(n) )になる．d_i(n)はnの約数を4で割ったもののうちで余りがiであるものの個数． 考え方 r*rの約数を計算しないといけない．でもr=2,000,000,000もあるので，…

問題 paintballというゲームをする．チーム戦になっていて，それぞれ誰がどのチームに所属しているかと誰が誰にボールを当てたかの情報が与えられる．敵チームに当てたら当てた人に+1，当てられた人に-1ポイントが変化する．同じチームに当てたら，当てた人…

問題 n人(nは偶数)が円になって手を交差させないで握手をする場合，何通り方法があるか． 考え方 メモ付き再帰した． 0番目の人と他の人が手をつないだ場合，交差させてはだめなので，繋ぐ時は偶数人ずつにわかれるように手をつながないといけない．なので2…

問題 黒と白の帽子をかぶっている人がいる．全ての人が黒の帽子をかぶっている人の人数を数える．その数字の配列が与えられるとき，黒の帽子をかぶっている人の人数を返す．あり得ない場合は-1を返す． 考え方 配列は2つ以下の数字からなっていなければいけ…

問題 数字の2次元配列が与えられる．その配列から各行と列がかぶらないように数字を選ぶ．そのとき，すべての組み合わせに対し，その選んだ数字の和がすべて等しいときCORRECT，違う場合INCORRECTを返す． 考え方 列iと列j，行kと行lを考える．(i,k)と(j,l)…

問題 いくつかボタンが壊れているリモコンでテレビのチャンネルを変えたい．最初は100になっている．番号ボタンか+/-ボタンを押して目的のチャンネルに合わせたいとき，最小で何回ボタンを押さなければならないか． 考え方 目的のチャンネルから，前後の方向…

問題 コンサートをしている．1曲ごとにボリューム変化させる量が決まっている．ただし，その値分だけ増やしても減らしてもいい．最後の曲の時に最大音量になるように変化させた場合，その最大音量の値を返す．もし途中で0からMAXVOLUMEから 考え方 メモ付きd…

問題が鬼畜すぎる．．．

問題 文字が敷き詰められた長方形のtableが与えられる．そのtableのコピーを4つ取り，2x2の形に拡張したものを作る．その拡張した長方形のすべての部分長方形を列挙する． 例えば，「OK」というtableの場合，拡張した長方形は OKOK OKOKとなる．各アルファベ…

問題 「AAAA」と「BB」のポリオミノが無数にある．「.」と「X」で構成されたregionが与えられる．このXの部分をポリオミノで埋める．「.」に重なってはいけない．複数の入れ方が存在する場合は辞書順で小さいものを返す． 考え方 やるだけ． 連続したXの個数…

問題 正の整数x,kが与えられる．「x+y=x|y」(|はビット演算のOR)を満たすyのうち，k番目に小さいyを返す． 考え方 例えば，x=5とすると2進数で101なので，和とORが等しくなるためには，1桁目は1なので0しかダメ．2桁目は0なので，0か1であればいい．3桁目は1…

問題 各授業を履修する人数の配列が与えられる．しかし，各授業はminSize以上maxSize以下でなければならなかった．それを満たすように履修者を別な授業へと割り振り直す時，最低何人を動かさなければならないか．もし，このルールが満たせないならば-1を返す…