Area1のif(memo[i][j])スマートフォン用の表示で見るArea1のif(memo[i][j])解いた問題のソースコードと解説など。3点を指定すると残り1点が定まり、その残りの点が与えられた中にあるかを調べる、というやりかただとTLEしてしまう。2点を指定するとその2点の中点が定まる。数列にある負の数の個数が偶数個の場合は操作によってすべて正(もしくは0)にできる。奇数個だとどうしても一つ残ってしまうが、操作をうまく行うと、符号がマイナスになる位置を好きに選ぶことができる。n個の荷物とその荷物を目的に運ぶための車が2台ある。荷物の重量はそれぞれw[i]であり、車が一回で運ぶことのできる重量はそれぞれc1,c2までである。2台の車は常に同時に動かすとする。荷物をすべて動かすのに2台の車を最低何回動かせばよいか答えよ。0と1からなるnxmのマスが与えられる。この中に含まれる1のみからなるx軸とy軸に平行な長方形で最大の長方形の面積を求めよ。ヒストグラム内の最大長方形の面積を求めるアルゴリズムを応用する。N個の文字があり、各文字の文字数が数値として与えられる。文字は与えられた順に(間にスペースを一つ入れて)連結して出力することができ、一行あたり最大でM文字出力する事ができる。文字の途中で改行してはいけない。牛がN匹いて、それぞれの牛の牛乳の生産量は異なっている。2匹の牛の牛乳の生産量の大小を表すクエリがM個与えられる。生産量の順番を確定するために必要になる追加のクエリ数を求めよ。mと互いに素なK番目の自然数を返せ。調べると当然間に合わない。ここは二分探索+包除原理。二次元座標上に点がN個与えられる。この座標上から一点を指定し、N個の点との距離の総和を最小化せよ。NxNのグリッドがあり、各マスに0以上の整数が書かれている。グリッドの左上のマスからスタートして右か下に一つずつ移動して右下のマスまでたどり着きたい。通ったマスの数字は得点となり、一度通ったらそのマスの数字は0になる。与えられた自然数を、それ以下の自然数の数列の和で表現する。これを自然数の分割と呼ぶ。Partitionという。Partitionsという。グリッド上に連結した池がある。これをぐるっと回って戻ってくるための最短経路を求めよ。8連結方向に移動できる。池の周りを4連結で囲むように印をつける。木の直径を求める問題。グラフ上の適当な点からはじめて最も遠い点を見つける。続いてその点から最も遠い点を探すとその間が直径になる。メモリ量、制限時間ともにシビア。グリッド上の格子点を直径1.6mの円形のロボットがスタート地点からゴール地点まで移動する。グリッドの一部に障害物があり、ロボットを障害物にぶつけてはいけない。アイテムがN個あり、それぞれの重さが与えられる。これらのアイテムをビンに詰めたいとする。一つのビンにたいして最大で2個までのアイテムを詰められる。このとき必要な最小のビンの数を求めよ。エレベータがm台あり、各エレベータには昇降用のボタンが2つだけついている。エレベータiの上昇ボタンを押すとu[i]階上がり、下降ボタンを押すとd[i]階下がる。階数は無限にあるが、0階より下の階はない。N人のうちから何人かパーティに招待したい。N人には上司部下の関係が存在し、これらは一つの木構造をなしている。n匹のネズミの位置と、m匹のネズミ穴の位置が与えられる。タカがネズミを狙っており、s秒たった時点で穴に隠れていないネズミは捕食される。すべてのネズミは速度vで動くことができ、一つの穴には一匹のネズミだけが隠れることができる。1からNの数字が書かれたビーズがある。2つビーズについての重さの関係の情報がM個ある。N個のビーズのうち重さが中央値になりえないものの個数を求めよ。一種のトポロジカルソート。両端にそれぞれ色が塗られている棒が複数与えられ、色が同じ棒の端同士を連結して一本の棒にすることができる。与えられた棒をすべて連結することはできるか答えよ。やっていることはしりとりと同じ。無向グラフの情報が与えられる。始点から終点まで辺のコストをかけ合わせたものがパスのコストになる。辺のコストにlogをかければコストの積を和に変換できる。数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。長さLの鉄線をn度で熱すると長さがL*(1+n*C)に変化する。この鉄線を向かい合わせの壁に取り付けて熱すると膨張して弧を描くようにしなる。熱したときの鉄線の中心部の縦方向への変位を求めよ。要素数mの数列をk個の連続する数列に分割する。分割したそれぞれの数列の要素の和を計算し、そのうち最大となる値を最小化するように数列を分割したい。この条件をみたすように数列を分割して出力せよ。無向木の情報が与えられる。同じ辺を2度辿らないように頂点間を移動する時、もっとも距離の遠い2点間の距離を求めよ。無向木の直径を求める問題に他ならない。直径の求め方は、てきとうな頂点から深さ優先探索を始めて最遠の頂点uを求める。文字列が一行ずつ与えられる。一行ごとに以下の処理を行って出力せよ。頂点と辺の情報が与えられる。最小で何色で頂点を塗ることができるか答えよ。四色定理から必ず4以下になる。色を数値で管理して、深さ優先探索でグラフを探索する。nxnの行列Aが与えられる。S=A+A^2+A^3+...+A^kを計算し、各要素をmで割ったあまりを求めよ。行列の累乗は繰り返し二乗でできるとしても単純にやったら確実にTLEする。うまく分割統治しつつメモ化しておくことで通すことができる。いう漸化式の数列がある。与えられるのでを求めよ。考えるとmonotonicalじゃないような。StanとOllieが掛け算ゲームをして遊ぶ。数字を1から始めて毎ターン2から9までの好きな数字をかけていく。数字が与えられた数n以上になった時、そのときのプレーヤが勝ちとする。Stanからプレーを始めて交互に行う。自分のコード(主に「ライブラリ」タグ)はパブリックドメインにします。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。