2011-01-01から1ヶ月間の記事一覧
2724 Purifying Machine 2^N個のチーズを持っている人がいて、チーズにウイルスが感染したのを取り除く機械がある。この機械では、1つのチーズもしくは、チーズの番号の2進数表記において異なる桁が1つしかないような2つのチーズをきれいにできる。今、機械…
3842 An Industrial Spy 与えられた数の桁を使って作れる素数は何種類あるか求めよ。エラトステネス＋全探査やるだけ 3844 Divisible Subsequences 与えられた数列の部分列で、和がDで割り切れるものの数を求めよ。先頭からの和を(modDで)取ってやるだけ 365…
1946 Cow Cycling 牛がサイクリング競争をしてる。牛はグループで参加している。x[周/分]の速度(xは整数)で走るとき、リーダー以外の牛は1分間にxのエネルギーを消費するが、リーダーはx^2のエネルギーを消費する。途中で牛が離脱してもよく、最後に1頭以上…
ぶっとんだ配点。 275 1からNまでの整数の書かれたカードがあり、色は素数なら赤、そうでなければ青になっている。今、色だけがわかっている。カードの数を特定できるだけ特定せよ。全探査でやったら計算量実は危なかったかもしれないけど通った 500 N個の箱…
3537 Crosses and Crosses 1*Nのマス目があって、先手と後手が交互に×を書いていく。×が3つ並んだら並べた人の勝ち。どっちが必勝か求めよ。×が3つ並んだら勝ちとは、すなわち×が置かれたらその１つか２つ隣に×を置くと負けるということになる。これを考えて…
3691 DNA repair 悪いDNA列のリストが与えられる。もう一つ与えられるDNA列を編集して、悪いDNAを含まないようにしたい。最低何箇所編集する必要があるか。Aho-Corasickで有限オートマトンを構築した後DP 3697 USTC campus network コンピュータがたくさんあ…
2224 Missing Piece 2001 15パズルみたいなやつを解くだけの問題。手数の上限が与えられていて、その手数以内で解けるか判定する。反復深化やるだけ 2353 Ministry あなたはある文書に大臣の署名を書いて欲しい。大臣のお役所の承認を得るなら、署名してもら…
けっこうひさしぶりのするめ 250 黒と白でグリッドを塗りたい。塗るのには正方形のブラシを使う。白のところに塗ってはいけない。どれだけ大きな正方形を使えるか？やるだけ。グリッドは正方形じゃないので落ちた 500 ある直線上で、木の高さはある範囲の整…
2775 The Number of the Same BST ある配列について、先頭の要素から順番に読み込んで二分探索木を構築する。二分探索木に要素を付け足すときには、すでにある構造を壊さない。左の子のキーは自分のキー以下で、右の子のキーは自分のキーより大きい。この条…
2348 Euclid's Game StanとOllieが2つの自然数で遊んでいる。プレイヤーは自分のターンのときに大きいほうの自然数から小さいほうの自然数を何回か引くことができる。それを繰り返して、0を作ったら勝ちである。Stanが先手である。どちらが必勝か。状態遷移…
3767 I Wanna Go Home いくつかの都市とそれらを結ぶ双方向の道がある。道にはそれぞれ所要時間が決まっている。また、都市は支持するリーダーによって2つに分かれている。異なるリーダーを支持する都市同士をまたぐのは、1回までに抑えたい。都市1から都市2…
2186 Popular Cows N頭の牛がいて、「牛Aが牛Bを人気があると思う」というリストがある。AがBを人気があると思い、BがCを人気があると思うのなら、AがCを人気があると思うことになる。他のすべての牛に人気があると思われている牛の数を求めよ。強連結成分分…
1 1以上9以下の整数の組(a,b,c,d)であって、0 2 2011以下の正の整数のうち、mod3で1になるものの総和-2になるものの総和を求めよ。(1-2)+(4-5)+…+(2008-2009)+2011。1341 3 相異なる7以下の自然数a,b,c,d,e,f,gを用いてa*b*c*d+e*f*gと表せる素数をすべて求…
1313 Booklet Printing 冊子を印刷するとき、各紙に印刷すべきページ番号を出力せよ。やるだけ 1583 Choose Your Words Carefully 与えられた文章において一番多く出てくる語を頼むTrie書くだけ 3510 A Tale from the Dark Side of the Moon 規則に従って入…
2586 Y2K Accounting Bug ある会社はある年の各月において、利益が出たならその額はsで、損失が出たならその額はdであった。その会社は、その年の任意の連続する5ヶ月において、損得を合計すると赤字になったらしい。その年の利益として考えられる最大値を答…
1984 Navigation Nightmare 農場がいくつかあって、それらを結ぶ道の情報が与えられるから、各クエリに対して、2つの農場の間のマンハッタン距離を答えよ。道の情報を全部処理すると木構造になるし、道同士は交差しない。全部の農場で木構造をなすので、全部…
2313 Sequence 数列A(1),A(2),…,A(N)が与えられるから、 V = (|A(1) – B(1)| + |A(2) – B(2)| + ... + |A(N) – B(N)|) + (|B(1) – B(2)| + |B(2) – B(3)| + ... +|B(N-1) – B(N)|) を最小化するB(1),…,B(N)について、Vを求めよ。 10000 どうやらgreedyのよう…
2011 Primary X-Subfactor Series 問題概要は2011 Primary X-Subfactor Series - PKU Wiki*を参照。 使う桁でビットDPやるだけ
