■12/19のSRM491 Div2。夜遅くて眠かった。 250 OneDigitDifference 解けた。 やるだけぽい。 500 FoxMakingDiceEasy 提出しなかった。 全通り試すのはギリギリ怪しそう。(間に合う) 組み合わせの数でやると、、重複どのぐらいでるかわかんない。 うまく枝刈…

問題 FerrersDiagramという、n=a1+a2+...+akとなるリストa1,a2,...,akでa1>a2>...>akとなるものを考える。さらにFIELD diagramというものを、nボックスが □□...□□ ←fieldOrder個 □□...□ ... □□ □ と並んでいて、k行目の個数がak 整数fieldOrderが与えられる…

問題 (x1,y1)と(x2,y2)の2つの点が与えられる．これらを端点とする線分をひいた時に，その線分上の点でx,yどちらも整数座標となる座標がいくつあるか答えよ．ただし，端点は含まない． 考え方 線分のどちらかの端点が原点になるように移動し，線対称にしても…

問題 ある電光掲示板があり、それはメッセージを繰り返し表示し続けている。そこで、そのメッセージの長さを調べたい。このメッセージを書きとめた文字列配列runningが与えられる。たとえば"abcabcabcab"であれば、"bca"や"abcabc"というメッセージがありえ…

久しぶりの参加。

問題 ある連続した正の整数の並びを1つだけのぞいてバラバラにした数列が与えられる．除かれた可能性のある数字を返す．もしありえないような場合は空の配列を返す． 考え方 ソートして連続した数列のなかで抜けているものを探す． もし，1個の時はその数値…

問題 いくつかの文字列が与えられる．それぞれの文字を省略したい．他の文字列の区別がつくように文字列を前からいくつか選んで省略する場合，それぞれの省略後の文字列を返す． 考え方 各文字列についてi文字目まで比較して同じのがなかったらそれを返すよ…

問題 数字の5は，以下のように6種類の数字の和で表現できる． 4 + 1 3 + 2 3 + 1 + 1 2 + 2 + 1 2 + 1 + 1 + 1 1 + 1 + 1 + 1 + 1 同様にして，数字の100は，2つ以上の和で表現すると何種類あるか． 考え方 上の分解を見てわかる通り，各和は，i番目の数字が…

問題 ある数列permutationが与えられる．これは1からnまでの数字がn個ランダムに並んでおり，これを昇順に並べたい．そこで，ipermutation[j]であるような(i,j)の組のswapを考える．各状態でswapは等確率で選ばれるとき，与えられた数列を昇順に並べるのに必…

問題 ideal文字列とは，(1-basedなインデックスで)各アルファベットが最初に現れる位置のインデックスの個数出てくるような文字列をいう．ある整数lengthが与えられるので，辞書順で最小となるideal文字列を返す．もしあり得ないときは空文字を返す． 考え方…

問題 4と7はラッキーdigitである。この2つの数字だけからなる数字はラッキーナンバーである。 aとbが与えられる時、aとbの間にあるラッキーナンバーの数を返す。 考え方 4と7だけから構成されるので、ラッキーナンバーの数はそんなに多くないことがわかる。 …

問題 4と7はラッキーdigitである。この2つの数字だけからなる数字はラッキーナンバーである。 nが与えられるとき、n以下の最大のラッキーナンバーを返す。 考え方 n以下のすべての数字に対してその数字が4か7だけからなる数字かをチェックして最初のラッキー…

問題 74932 1325 457 92 1 のような数字の三角形が与えられる。各数字は上の数字と右上の数字の和の最後の桁を表す。 各段の数字がいくつか「?」なっている三角形が与えられる。上記のルールを満たすように「?」に数字を当てはめた三角形を返す。 考え方 下…

問題 本は3つ部分("introduction","story","edification")からなる。ある人はいろんな順序で本を読んでいく。ただし、同じ本の同じ部分を2度読み直すことは許されない。さらに、一度別な本を読んでしまったら前の本を読むことはできない。読んだ部分readPart…

問題 あるファイルシステムで現在のいるディレクトリと目的のファイルの絶対パスが与えられる。相対パスを返す。 考え方 目的パスとカレントディレクトリを「/」で分解しておく。 ルートからどこまであっているかを調べて、カレントディレクトリからそこまで…

問題 nのk下降乗というのを「n*(n-1)*...*(n-k+1)」と定義し、n^^kと書く。それぞれの定義が与えられるとき、これを計算する。 考え方 やるだけ。

問題 配列divisorsにある各数字の倍数で、配列multiplesにある各数字の約数であるような正の整数を返す。 考え方 divisorsのすべての数字の倍数でなければならないので、この配列の中で最大の数字以上でなければいけない。また、multiplesのすべての数字の約…

問題 長方形のグリッドが与えられる。各セルには、占領済み「X」か空「.」が書かれている。1-happyなセルとはそのセルが空で8近傍すべてが占領されているセル、2-happyなセルとはそのセルが空で直交セル(上下左右)が占領されていて斜めのセルの1つ以上が空に…

問題 4と7だけからなる数字はラッキーナンバーである． ある整数nが与えられるとき，ラッキーナンバーの和でnとなる組み合わせを返す．複数の解があり得る場合は要素数が少ないもので，辞書順で早く来るものを返す．ここで辞書順とは2つの配列a1,a2があった…

問題 直線状にnセルつながった通路がある。セル0からセルn-1まで移動する。ただし、セルiに入るためにはcellPrice[i]コストがかかる(-1には入れない)。移動方法は、両隣に1マス動くか、テレポートできる。テレポートはenterCellからexitCellに飛ぶことができ…

問題 その会社の給料体系は「部下の給料の合計値がその人の給料」となる。ただし、部下がいない場合は給料は1。上司かどうかが隣接行列で与えられるとき、すべての人の給料の合計値を返す。 考え方 トポロジカルソートして、順番に自分の上司に自分の給料の…

問題 グリッド平面をスパイラル状に動く。動いたところに書いてある数字の合計値を計算する。 ただし、左上から右に動き始め、それ以上直進できなくなった(進行方向セルがすでに行った事のある場合)ら、向きを右に変えて動き続ける。向きを変えた場合はその…

問題 友達のシドと赤玉redCount個と青玉blueCount個が入ったバッグから取り出すゲームをする。玉の個数の合計は奇数。 自分のターンではランダムに玉を1つ取り出す。シドのターンでは必ず青玉を取り出す。自分が勝つためにはバックに入っている最後の玉を取…

問題 毎日夜にろうそくに火をつけて、朝に消す。一晩で1インチ短くなる。n日目にはn本火をつけなければならない。複数のばらばらな高さのろうそくが与えられる時、最大で何日間火をつけることが可能か。 考え方 greedy。 各日について、ろうそくを高さが高い…

問題 scoreをconversionFactorsで割ったものが点数となる。ただし、小数点以下は四捨五入。 合計点を求めよ。 考え方 やるだけ。

問題 文字列配列wordsの超文字列Xとは、 wordsの各要素がXの部分文字列 x_1素数)。x_kはwords[k]がXに出現する場所。 たとえば、"abca"は{"abc","ca"}の超文字列。x_1=0,x_2=2とすることができる。 文字列配列が与えられる時、最短の超文字列の長さを返す。 …

問題 64cmのスティックを持っている。これを半分に割っていく。これを繰り返し、目標の長さを作るとき、最終的にスティックは何本に分割されているか。 考え方 2進数に直して1の数を数えるだけ。

問題 あるメモリシステムはキャッシュ機能を持っていて、以下のアルゴリズムで動作する。 baseアドレスから連続したk個分をキャッシュとして持つことができる。もし、この範囲に要求されたアドレスが含まれない場合は、新たに取るキャッシュが最小になるよう…

問題 暗号化した文字列をやり取りする。有効な文字列validWordsが与えられ、文字列にはそれぞれが0回以上現れる。そして、文字列中の文字をそれぞれ入れ替える時、元と違う個数だけコストがかかる。たとえば、"abc"が有効な文字列ならば"acb"はコストが2、"b…

問題 非負の整数は2つの非負の整数の2乗の和にすることができる。たとえば、13=2*2+3*3。 その整数のスコアを「2つの整数の和の異なる表し方の合計数」と定める。lowerBoundからupperBoundまでの整数の中で最大のスコアを持つ整数を返す。 考え方 やるだけ。