問題概要 長さL( 考えたこと ある暗号文と対応する平文を全通り試せば鍵の候補は全部出せる。 ん？何だこれ。実装するだけにしか見えない。 書く。サンプル合わない。問題文の解釈間違いに気付いて微修正。通った。 同じ鍵が複数有ったときに重複して数える…

問題概要 整数n( 考えたこと とりあえずLCMが必要なことは分かる。 LCMが分かれば後はnがprefixになるような数字の上限と下限の間にLCMの倍数があるか判定すれば良い。 sup/LCM > inf/LCMならばその間にLCMの倍数が存在するので、それを真面目に実装する。 …

問題概要 横断歩道がある。横断歩道の幅はRで、車の幅はCである。人がN( 考えたこと 幾何とかシミュレーションでよくある特徴点全列挙かな？ 時刻を固定したら通過できるかどうかはO(N*log N)で判定できる。 後は特徴点がいくつくらいあるか見積もってみよう…

問題概要 H*W(H,W 考えたこと 二分探索っぽいけどこれくらいなら全探索で通る。 フォントのサイズを固定したときの判定部分を書くだけだし、特に難しい所もなさそう。でも場合分けが出てきてしまう。 ちょっと考えたけど場合分けが回避できない。 書けたけど…

SuperCon 2011の本選課題作題委員をやっていました。課題(なくろん)決定までの流れを話せる範囲で記録しておこうと思います。あと、結果についても簡単に触れておきます。 何で自分が課題作成委員なのか スーパーコン実行委員長であるサイバーメディアセンタ…

問題概要 10桁以下の整数が与えられる。各桁の数字を1増やすか減らすのに1単位のコストがかかる。コストの総和が一定量以下となるようにして11の倍数をたくさん作りたい。このとき、Σ(初期コスト-必要なコスト)を求める問題。 考えたこと 10進数で11の倍数か…

問題概要 自チームと相手チームには互いにN( 考えたこと 最大重み2部マッチング？それって解き方あったっけ？ (2-勝点)をコストとして最小重み2部マッチングで解けるか。 ライブラリコピペするだけなのもあれなので、他の解法も考えてみよう。 しばらく考え…

問題概要 W*H(W,H nmlkji oxwvuh pqrstg abcdef ぐるぐるまわって最奥までいくとき、終点の座標を求める問題。 考えたこと シミュレーションすれば計算量O(W*H)でギリギリ間に合う。でもメモリが足りない。vectorでboolだと足りるような気もするけど、邪道だ…

問題概要 [0,distance(区間を考える。この区間内に人がN( 考えたこと 一目二分探索。 最初に人の座標をソートしておけば、左端から順に考えられるのでよさげ。 dp[p] = ([0,p]をカバーするのに必要な最小コスト)とすればいけそう。 書く、合わない。これじゃ…

問題概要 箱にボールがいくつか入っている。色はN( 考えたこと 高校数学みたいな問題だ。やるだけに見える。 一応オーバーフローとか誤差とかちょっと怖いので対数で計算しよう。 通った。

問題概要 数字の書かれていない目盛12個の時計がある。どれかの目盛を起点にした長針の角度と短針の角度がそれぞれ与えられる。そのようになる時刻を求める問題。ただし複数ある場合は最も早い時刻を答え、無い場合はその旨出力する。 考えたこと うん？これ…

問題概要 一列にデータが並んでいて、互いに素な区間がN(区間の長さや初期位置は10^9以下である。この区間全てをいくつかの小区間でカバーする。ひとつの小区間にかかるコストは区間の長さ+overhead(区間のコストはmaxPacketSizeを越えてはいけない。必要な…

問題概要 50桁以下の数字が与えられる。最小でいくつ加えたらある数字Kが出てくるか求める問題。 考えたこと 1の位見るだけじゃないか。 当然繰り上がりとか考慮してないから落ちる。 多倍長の計算とかしたくないのでJavaで書く。通った。

問題概要 線分からなる図形がいくつか与えられる。重なっているものをマージしていったとき、要素がいくつ残るか求める問題。 考えたこと また入力が面倒な…。 線分の個数とか大したことないし、やるだけ問題に思える。 書いた。サンプル通らない。 入力のパ…

問題概要 ２次元のボード(W*H(W,H 考えたこと 何これただのBFS？これだから昔のSRMは…。 当然落ちる。そうかこれってDAGの最長パスか。 DAGかどうかの判定して、DAGでないなら即座に-1を返してそうでないなら普通にメモ化再帰で行ける。 DAGかどうかの判定っ…

問題概要 ある数列の初項A[0]、第二項A[1]が与えられる。数列はA[n] = abs(A[n-1]-A[n-2])を満たす。第k項を求めよ、というクエリをN( 考えたこと 入力がまたstringで与えられて非常に鬱陶しい。この辺は今でもたまに感じる(グラフがvectorで与えられたり)。…

問題概要 H*W(H,W 考えたこと 10以下という制約があるのでビットDPの可能性が高いことは分かる。 これは珍しく__builtin_parityが使える問題だということも分かる。 でも具体的な解法が分からない。本番は早めに切り上げてサンプルの弱い250の撃墜ケース作成…

問題概要 原点を含まない円がN( 考えたこと 幾何は問題じゃなく、極座標で考えると区間の被覆する区間を最大化する問題に落ちることが分かる。 フローのF？でもノード数多いしそもそもフローだとしたらdoubleな時点で自分には解けない。 残るは貪欲かDPか。…

問題概要 AとBの文字をつなげてできるだけ長い文字を作りたい。ただしA,Bの使用回数は上限countA, countB(maxA, maxB( 考えたこと サンプル弱すぎて不安だ。 ABAB...ABみたいな感じに並べて、後から追加できるだけ追加すれば良さそう。 Aから始まる場合とBか…

問題概要 数列A(長さN( 考えたこと 非常によくあるDPっぽい。 でもeasyでDPって珍しい気もするし、何か他の解法もあるのかな？ ちょっと考えたけど、DPで簡単にかけるからもういいや。 今回は配るDPが一番しっくりくる。 書いた。最後のサンプル合わない。 …

問題概要 ギターがN( 演奏できる曲の多さ ギターの少なさ ギターの名前の辞書順で若い方 考えたこと N=10って…。一瞬マッチング系の問題化と思ったがこれはどう見ても全探索。 素朴な実装で計算量がO(2^N * N*(M+log N))位に見える。 500にしては簡単な気も…

問題概要 n-jumpとは今いる座標から(±n, ±1), (±1, ±n)だけ移動することをいう。nとして使える値が配列として渡されるので(x,y)に到達できるか判定する問題。 考えたこと 数論系の問題？GCDとかでてきそう。 1が曲者過ぎる。全然分からん。 とりあえず3-jump…

問題概要 原点中心半径r( 考えたこと 何か公式が与えられてるけどそれ使った解法がよく分からない。 とりあえず数列辞典に投げてみよう。 あった。色々調べたら、rの素因数で、4で割って1余るものの指数をa[i]とすると4*Π(1+2*a[i])が答えになるらしい。 後…

問題概要 長さM( 考えたこと practiceのA問題なのに敷居高すぎじゃないか？初参加の人がA問題見て、「難しそうだし参加見送ろうかな」とかならないことを祈る。 一番素朴な方法を考えよう。長さをM..0と降順に調べる。先頭の文字列から得られる部分文字列は…

京都大学プログラミング研究会にオンサイトで参加した。個人戦でのオンサイトは初めての経験だったけど、適度に緊張感あってよかった。結果は11位で、まあ順位だけ見れば実力以上のものが出せたような気がするけど、Eが通らなかったのは猛省せざるを得ない。…

問題概要 正整数Nで、N = Π p[i]^e[i], p[i]:素数, p[i] = e[i+1]を満たすようなものをFox Numberという。A( 考えたこと とりあえず、A-Bが負になったり1がFox Numberでないとかには気をつけとこう。 一目、区間篩っぽいのが見えるけど。 とりあえず因数分解…

問題概要 行列(W,Hスワップ、列のスワップを行うことにより、行列がある制限を満たすようにできるかどうか判定する問題。制限は、最大要素から離れるほど値が小さくなっていること。 考えたこと 行と列が独立していることはすぐに気づく。嘘です本当は5分く…

問題概要 長さN( 考えたこと いきなり難しくなった。 でもDだし実は簡単なんじゃないの？重なってる部分の多い所から、とかで案外行けるのかなあ？ うーん、反例が頑張ったら作れそうな気がする。 総和がN/2になるようなビットだと、部分和の期待値は4/Nだか…

問題概要 しりとりで、相手がミスしたら指摘するリアクティブな問題。使える文字集合は小文字のアルファベット。こちらは先手で1~10文字の単語が使える。相手は1~2語の単語しか使えない。50ターン(先手 -> 後手で1ターン)以内に相手のミスを指摘しなければな…

問題概要 W*H(W,H 考えたこと 典型的DP、というか最近見たことあるなあ。 あった。http://community.appliplanet.co.jp/docs/DOC-1134 DPの方が楽(自然)に書けるような気がしたけど、そこを敢えてメモ化で書いた。 あれっ？通らない。というか答えが負って明…