徳山こうせん(not 高専)の標識まとめ

高専生ならみんな入力したことのある○○光線ですが,実在する○○光線があります. それは徳山光線です.ちゃんと証拠の画像もあります. 暗くて字が読めなかったので,色味の調整をしていますが,それ以外の画像編集は一切していません.ちなみに,Google マッ…

証明を書こう!

この記事はCompetitive Programming (その2) Advent Calendar 2016 - Adventarの記事として書きました. この記事に,技術的に有用なことはありません. 「証明を書こう!」という話です. 何か月か前に,とある方から次のような質問をされました. 競技プ…

ICPC2017国内予選 参加記(引退します)

チーム名はyotei_awanaiです. チームメイトのハンドルを知らないので,N君とK君とします. 結果 どう考えても5完セットでした.6完ワンチャンだったと思います.でも3完74位です. 引退 & JAG入会待ったなし. 結論 コミュニケーション大事 練習大事 平常心…

SRM 690(Div.1 Easyのみ)

ケアレスミスでEasyを落としました.(何やってんだか.) 解いた問題 Easyのみ.120点ぐらいでの提出だった. 問題概要 整数 とが与えられる.() 1 ~ 100 までの整数のうち,個の数 を選び,どのように を選んでも,がにならないようにする. 解法 等差数…

TopCoder部のカレンダーをGoogleカレンダーで(そこそこきれいに)見る

カレンダーを公開しました.AtCoderのイベントはAtCoder社さんのカレンダーをお使いください. githubにあげました. TopCoder部のカレンダーを開くのさえ億劫になってきている今日この頃. コンテストの予定がGoogleカレンダーに表示されるようになれば,コ…

ACM-ICPC 2015 こくないよせん さんかき

ぼくはAもんだいをとおしました.ぼくがAをとおしたあとは,くりんぺっとさんがB,Cをとおして, しゅんかんてきにいちいになりました.そのあと,EやFをおもにかんがえましたが,ほうしんがまとまらず, すわっているだけになりました.きょすくんが「Hがや…

ACM-ICPC 2014 アジア地区予選東京大会 参加記

オリセンで開かれたICPCアジア地区予選に参加してきました.アジア地区予選に出場するのは個人でも学校でも初の経験でした. 結果は4完29位(大学別24位)でした.29位だったのでリクルートさんからNiku Awardをいただきましたありがとうございます. チーム編…

ICPC-JAG Day4 Problem F

解説では,Suffix Array + Range Minimum Queryでの解法が紹介されていましたが,僕はクエリ先読み + Aho-Corasick法で通しました.というか,Suffix Arrayよくわかってない.ある人には,「クエリ先読みするなよ」と言われました. 概要 文字列SとQ個のクエ…

POJ 2441: Arrange the Bulls

概要 牡牛がN頭いて,M個のコートに1頭ずつ割り当てたい. 牡牛はそれぞれ好むコートが決まっている. 割り当て方は何通りあるか. 解法 bitDPやるだけ. ただし,愚直に実装するとMLEを起こすはずなので,配列の再利用をする. int N, M; int P[30]; int B[…

POJ 2886: Who Gets the Most Candies?

POJ100問AC記念. 概要 N人の子供が一枚ずつカードを持っていて,輪になって並んでいる. K番目の子供からスタートする.まず,現在選んでいる子供を輪から除外する.除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ.これを繰り返す…

POJ2155: Matrix

概要 N次正方行列があり,初期状態ではすべての成分が0である. T個のクエリが来て,内容は (x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う. (x1,y1)の成分を答える である. 解法 2次元のBITを用意する.これは,(1,1),(x,y)によって定まる矩形領域の値…

POJ 3109: Inner Vertices

概要 2次元格子上においてある黒い石の情報が与えられる. ある格子点において,x方向,y方向共に黒い石に挟まれているならそこにも黒い石を置く. 最終的に格子上においてある黒い石の個数はいくつか? 解法 扱いやすいように座標圧縮をしておく. 各x座標…

POJ 1990: MooFest

概要 一次元座標x[i]と,値v[i]が与えられる.iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である.コストの総和を求めよ 解法 座標でソートしておく. 各iについて,BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計…

POJ 2674: Linear World

思いがけないところではまったのでメモ. 概要 線分の上を物体がある方向に向かって動く.2つの物体が衝突すると反対に動く. 一番最後に落ちる物体の名前とその時間を求める. 解法 蟻本の蟻と似た考え方.最後に落ちるものを特定するには,左側にどれだけ…

POJ 3185: The Water Bowls

概要 20個のボウルが一列に並んでいて,あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る.(端っこのボウルを選ぶと2個だけひっくり返る) 全てのボウルを正しい向きにするには,何回の選択が必要になるか? 解法 端っこから地道にシミュレ…

POJ 1222: EXTENDED LIGHTS OUT

ほろ酔いコーディング 概要 5行6列のライトのついたボタンがあって,ボタンを押したらそのボタンと4近傍のボタンが反転する. 与えられた状態からライトを全部消す押し方を求める. 解法 蟻本まんま.幅と高さをいじればそのまま通用する...と思う. 僕は…

POJ 2739, POJ 2100

POJ 2566は,そのままだとしゃくとりできないが,累積和にしてソートするとしゃくとりできるようになる.なぜならば,問題が知りたいのは合計の絶対値であるから,累積和の差だけを考えればよいため.カンニング先→POJ-2566 : Bound Found - komiyamの日記 P…

POJ 1759: Garland

概要 N個の提灯が下がった糸を垂らす.片方の端点はAとし,他方をBとする. このとき,糸は重力にしたがって垂れ下がる. i番目の提灯の高さをH_iとすると, H_1 = A, H_N = B, H_i = (H_(i-1) + H_(i+1)) - 1 が成り立つ. あるAが与えられたとき,全ての提…

POJ 3685: Matrix

概要 N次正方行列があって,その(i,j)-成分はi^2+100000*i+j^2-100000*j+i*jで与えられる. M番目に小さい要素の値はいくつか. 解法 解について二分探索.列を固定してしまえば,値は行について単調増加であることが式からわかる. 2次方程式を解けばO(1)で…

POJ 3662: Telephone Lines

概要 N頂点,辺P本のグラフが与えられる.K本の辺は無料で使うことができ,それ以上使うとK本からはみ出た辺の中での最大の長さだけの料金が発生する. 頂点1から頂点Nまでの経路をできるだけ安い料金で実現したい. 解法 料金(辺の長さの最大値)について…

POJ 2991: Crane

何を血迷ったのか,くっそ忙しいときに取り組んだ.そのうえ,勘違いをただすためにかなり時間を食った.今は反省している.問題文・解法は蟻本まんまのため省略. 多分同じ間違いをする人はいないと思うが,もしも同じ勘違いで頭を悩ませる人が出てきたとき…

POJ 3579: Median

概要 N個の配列が与えられる.この中から2つの要素を取り出し,その差を計算し別の数列とする. 新しく作った配列の中央値を探索する.ただし,この問題において偶数長(m)の配列の中央値はm/2番目に小さい値と定義する. 解法 解を仮定して二分探索.入力さ…

POJ 3111: K Best

概要 n個の宝石があって,k個を残して売り払いたい.その時,残したk個の宝石の単位重さあたりの評価値を最大化したい. 解法 蟻本そのままで二分探索.謎WA連発の末,探索終えた後にもう一回答えを計算したほうがいいという結論に至る. 繰り返し回数が結構…

POJ 2976: Dropping Tests

概要 授業でn回のテストを受けた.i番目のテストではb[i]問中a[i]問正解した. 受けたテストのうちk回を取り除き,を最大化したい. 解法 二分探索.蟻本の練習問題まんま. int n, k; int a[1010], b[1010]; double v[1010]; bool C(double x){ for(int i =…

POJ 3045: Cow Acrobats

概要 牛がN匹いる.i番目の牛は重さがw[i]で,強さがs[i]であることがわかっている. この牛でタワーをつくりたい.タワーは牛が別の牛一頭にのることを繰り返してつくられる. この時,牛iの危険度は (牛iの上に乗っている牛の重さの合計) - (牛iの強さ) で…

POJ 3104: Drying

概要 洗濯物がn個あって,自然乾燥だと1分間に洗濯物の水が1だけ減る.暖房機を使えば,1分間にkだけの水を減らすことができるが,これは1分間に1つの洗濯物についてだけしか使えない. 暖房機を最適に使った時,すべての洗濯物を乾かすのに必要な最小の時間…

POJ 3273: Monthly Expense

概要 要素数Nの数列{a_i}が与えられる.この数列をM個の連続した部分に分け,各部分の要素の合計の最大値を最小化したい. 解法 合計の最大値に対して二分探索を行う. 下限の初期化を間違っていたせいか,WA出した.あと,最近気が付いたんだけど,二分探索…

POJ 3258 : River Hopscotch

概要 スタートの石とゴールの石が川の中にあって,その間の距離がLだけ離れている.スタートとゴールの間には,N個の石が一列に並んでいて,i番目の石はスタートからd_iだけ離れた位置にある. スタートとゴールの石をM個以下だけ取り除いて,石(スタートと…

POJ 3641: Psudoprime numbers, POJ 1995 : Raising Modulo Numbers

解法 繰り返し二乗をやるだけ. POJ 3641 bool isPrime(ll x){ for(int i = 2; i * i <= x; ++i){ if(x % i == 0) return false; } return true; } ll p, a; int main(){ for(;;){ scanf("%lld%lld", &p, &a); if(p == 0 && a == 0) return 0; ll q = 1, s =…

POJ 3292 : Semi-prime H-numbers

概要 H={4N+1|Nは0以上の整数}とする.この時,Hの元xが1とxの組以外の積で表現できないものをHの素数と呼ぶことにする.h \in Hが与えられたとき,2つのHの素数の積で表すことができるh以下の数の個数を計算する. 解法 素数の列挙は篩を使っていい. あと…