きままにものづくり

日々の気付いたことなんかを書いてます。

2014-12-01から1ヶ月間の記事一覧

SRM608Div1Easy

問題 N個のキャンディが入った箱が与えられる。箱の中のキャンディの合計はC個である。箱の中のキャンディの数は正確には分からず、lowからhighの間という情報だけが与えられる。X個のキャンディを必ずとるのに必要な箱の数の最小値を求めよ。 解法 X個を集…

SRM609Div1Easy

問題 長さNの文字列が与えられる。要素はの2つである。要素を好きなだけ消すことができる。最初のn個が>、次のn個が 解法 長さに付いて全探索をし、その長さを実現できるかを確認する。 計算量 コード

SRM610Div1Easy

問題 サイズNの二次元配列が与えられる。各要素は1か0である。1と0か繰り返す四角形の最大の面積を求めよ。 解法 (x,y)を考え、そこから1と0を繰り返す幅を探索し、この時の面積を今までの最大の面積と比較し更新する。y+1に移動可能なら同様のことを行い、…

SRM611Div1Easy

問題 2つの数列AとBが与えられる。引数に数列をとるLCMという関数を定義する。LCMは与えられた数列の全ての組み合わせにおける最大公倍数の集合を返す。LCM(A)==LCM(B)となるかを確認せよ。 解法 LCMの返り値を計算するととなる。数列内で余分な要素を削除す…

SRM612Div1Easy

問題 目標の数字Sが与えられる。初めは1からスタートし、以下の操作を行い目標の値にする。 現在の値をコピー 以前コピーした値を現在の値に加算 現在の値から1を引く Sとするのに必要となる最小の操作回数を求めよ。 解法1 1を引く操作ができないと仮定する…

SRM613Div1Easy

問題 N個の数列が与えられる。各要素は+Xか-Xだけ移動しなければならない。数列の最小と最大の要素の差の最小値を求めよ。 解法 数列をソートする。 小さい順から適応していくと、+Xをする要素と-Xをする要素の2つに分解できる。+Xをした後に-Xをし、また+X…

SRM617Div1Medium

問題 N人のプログラマーがいる会社にM回行くことを考える。毎回AとBのおもちゃを持って行き、choice1とchoice2のプログラマーにどちらかのおもちゃを渡す。各プログラマーが持っているAとBの差分の総和が小さくなるように、どちらのプログラマーにどちらのお…

SRM618Div1Medium

問題 N個の文字が与えられる。これらの文字を使って以下の性質を満たす文字列の数を求めよ。 同じ文字が連続しない xyxyの形式を持たない。x=yの場合も含み連続している必要はない。 1,2の性質を満たす文字列の中で最長 解法 まず、文字列の長さの最大を求め…

SRM628Div2Medium

問題 長さNの文字列が与えられる。文字列の要素は(,),{,},[,]の6文字かどの文字にもなれる'X'のどれかである。全ての括弧が対応しているかを確認せよ。ある括弧をまたいで対応している場合は、無効とする。(例: ([)]) 解法 ひとつのスタックを用いることで、…

SRM619Div1Medium

問題 N人の社員とK個の仕事と仕事を覚えるのに必要なコストが与えられる。社員の構成はピラミッド状になっており、0番目の社員以外は必ず上司がいる。 直属の部下と上司の固まりを部署とする。各社員は必ず2つの違う仕事を習得している。同じ部署内で全員が…

TLS(SSL)のハンドシェイクの安全性について

今年は色々と問題のあったTLSについてです。 この記事では、TLSがどうのような暗号技術を用いてセキュアな通信を実現しているのかを説明します。 TLSとは TLSとはTransport Layer Securityのことであり、現在は1.2が最新のバージョンで1.3を策定しているとこ…

SRM620Div1Medium

問題 N人のメイドいる。それぞれM個のスキルに対しての能力表scoreが与えられる。スキルに対して安定的なソードを何度か行うことでresultと同じ結果を得られるか調べよ。 解法 ソートの順番を遡ることで答えを導く。 resultの結果が昇順にならんでいた場合は…

SRM621Div1Medium

問題 ノード数Nの2つのツリーが与えられる。各ツリーはN-1のエッジを持っている。類似度S(e1, e2)を定義する。e1はツリー1、e2はツリー2のエッジを示す。ツリー1をe1で分断すると、ふたつのノードの集合ができる。ツリー2も同様である。このノードの集合を比…

SRM622Div1Medium

問題 ノード数Nのツリーが与えられる。ツリー内部のノード同士の距離がDを超えないように、K個のサブツリーを構築する。最小のKを求めよ。 解法 メモ化と再帰を用いて解く。f(x, d)はノードxをルートとした時の最小のサブツリーの数を返す。xはノードの番号…

SRM623Div1Medium

問題 二次元平面を考える。果物の位置が与えられる。果物は1秒経つとy軸のマイナス方向に1移動する。(0, 0)に果物を収穫できる人がいて、一秒ごとにx軸のプラスかマイナスの方向に移動できる。収穫できる果物の最大値を求めよ。ただし、は以下の式で生成され…

SRM614Div1Easy

問題 二次元平面上に、N個の点が与えられる。K個の点を含む正方形の最小面積を求めよ。 解法 xで2つの組み合わせを取り出し、その間にあるyを全て取り出す。取り出したyをソートし全探索をする。 計算量 コード

SRM615Div1Easy

問題 サイズNの数列Xが与えられる。ある数字xからスタートし、Xの要素を0要素目から比較していく。同じ値になった場合は値を2倍にして探索を続ける。この操作を行った後に出力することができない実数の数を答えよ。 解法 Xに入っている要素でシミュレーショ…

SRM624Div1Medium

問題 ノード数N、エッジ数Eの無向グラフが与えられる。それぞれのノードには1~Nまで番号が振られている。各エッジはコストを持っている。コストは0を取ることが可能である。1からNまでの最短となるパスの数を求めよ。無限にある場合は-1とする。 解法1 まず…

SRM625Div1Medium

問題 サイズNの平面を考える。スタート点'b'と穴'H'とゴール'$'と通常のパネル'.'が存在する。'b'は複数存在し、その上には駒が置いてある。駒は上下左右に3マスずつ移動可能である。駒の移動先、もしくは移動する間の2つのマスが'H'ならそのマスへは移動で…

SRM626Div1Medium

問題 ノード数N、エッジ数Eの有向グラフが与えられる。ノードには1~Nまでの番号が振られている。各エッジは正整数コストを持っている。Nancyはノード1からスタートしノードNに最小コストで到達したい。Nancyはcharge回だけエッジのコストをマイナスにするこ…

SRM626Div2Hard

問題 ノード数N、エッジ数Eの有向グラフが与えられる。ノードには1~Nまでの番号が振られている。各エッジは正整数コストを持っている。Nancyはノード1からスタートしノードNに最小コストで到達したい。Nancyはcharge回だけエッジのコストをマイナスにするこ…

SRM627Div1Medium

問題 N個のノードと無方向性のエッジとノードに対応する数字が与えられる。K個以上のノードをつないだ時のノードに対応する数字の列を考える。この数列(要素数がK個以上)の転換数の最小値を求めよ。転換数とは、Sを得られる数列とした時にiS[j]を満たす(i,j)…

SRM638Div1Easy

問題 サイズNの三次元の空間を考える。XY平面、YZ平面、ZX平面での射影が与えられる。XY平面への射影は、Z方向から光を当てた時にできる影のこととする。サイズ1のオブジェクトが6近傍で接続されていてかつ、射影の結果に矛盾がない場合はPossibleを返し、そ…

SRM637Div1Easy

問題 2N枚のカードが渡される。このカードには1~2Nまでのカードが書かれている。自分と相手プレイヤーにそれぞれN枚のカードが渡される。カードを出しあい数字がでかい方が勝者となり1pointもらえる。自分の手札はhand、相手のカードを出す順番はsotheである…

SRM636Div1Easy

問題 高さH、幅Wの二次元配列が与えられる。各要素は0~9までの数字を持っている。この配列を縦と横に2つずつ直線を引いて9つのエリアに分割する。エリアの要素の総和がそのエリアの値となる。エリアの値の最小値が最大となる分割方法を見つけ、その時の値を…

SRM635Div1Easy

問題 サイズNのdate,ratingのふたつの数列が与えられる。その中で、同じ傾きの列を持つ数列が2つ以上存在する集合の中でそれぞれの点の長さの総和が最大値を求めよ。 例) {1,2,4,8,16,32},{1,2,4,8,16,32} 傾きは{1,1,1,1,1}となる。{2,4,8,16,32},{2,4,8,16…

SRM634Div1Easy

問題 M個の品物がありN人の買い物客がいる。一人につきひとつまでしか商品を買えない。K個以上の品物を購入した者を大口顧客と定義する。どの品物がいくつ購入されたかを示す数列が与えられる。この条件を満たす最小の大口顧客を求めよ。 解法 大口顧客の数…