yukicoderで出題していただいた問題の解説です。 問題 No.346 チワワ数え上げ問題 - yukicoder 与えられる文字列 の部分列(連続でなくともかまわない)のうち、"cww" となるものの総数を求めてください。 制約 解説 計算量を落とす過程に沿って説明していきま…

yukicoderで初めて作問させていただいたので、その問題の解説です。 解説にはC++, Pythonのサンプルコードをつけてあります。 質問等あればコメント欄か @yurahuna まで。 問題 No.345 最小チワワ問題 - yukicoder 与えられる文字列の連続した部分文字列のう…

他のブログを見て「なんで交差判定"2回"してるの？？」と思った人用の記事。 問題 abc016.contest.atcoder.jp 多角形と、線分が与えられる。線分により、多角形はいくつの領域に分断されるか。 解法 公式の解答を見ると、(求める数) = (線分と交差する辺の数…

解くのに3時間かかりました(弱い) 問題 abc025.contest.atcoder.jp 3*3マスの盤に、先手と後手が順に○と×を埋めていく。盤面が埋まったら次のように得点を配分する。横に隣り合うマス、縦に隣り合うマスの計12組のペアにそれぞれ得点が設定されている。各ペ…

想定解と違うっぽかったので書いておきます。（ダイクストラで解いた） 問題 abc022.contest.atcoder.jp グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

「やられた！」と思った問題。こんなんがCODE FESTIVALの決勝でも出るんだなあ…。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-festival-2014-final-open.contest.atcoder.jp 与えられる整数Aがパスカルの三角形に含まれるなら、その段数・行…

さてB問題。これが一番時間かかった。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-thanks-festival-2014-a-open.contest.atcoder.jp 石像が南北方向にR行, 東西方向にC列並んでいる。最初はすべて南を向いている。左上を(1, 1)とする。 儀式…

2月14日――世間では「バレンタインデー」と呼ばれ、恋に焦がれる者たちがチョコを渡しあう今日この日――私は22歳の誕生日を迎えながら実家で一人卒論を書いていました。 バレンタインらしいことも誕生日らしいことも特になく、しかも誕生日翌日が卒論提出日と…

「なるほど！」と思った問題。わかってしまえば簡単かも。 問題 arc009.contest.atcoder.jp 0～9の数字の、新しい大小関係が与えられる。この大小関係に沿って、与えられるN個の数を昇順にソートせよ。 解法 初めてこの問題を見たときは「比較関数を作って、…

バレンタインということで（？） 問題 arc025.contest.atcoder.jp 縦Hマス、横Wマスのチョコレートがある。各マスはブラックチョコかホワイトチョコであり、これらは市松模様に並んでいる。 各マスについて、チョコの濃度が与えられている。このチョコレート…

この記事は「競プロのための正規表現」と題し、競プロに頻出の文字列の問題を正規表現でさくっと解けるようになろう！という目的のために書かれた記事、を、いつか書くためのメモです。 実際のコードも載せているので、「正規表現ってなんですか＞＜」「競プ…

蟻本2-6章を読んで素数・約数系のライブラリ的なものができたのでまとめておきます。説明は全部蟻本にあるぞい。 【なかみ】 gcd(a, b): aとbの最大公約数 lcm(a, b): aとbの最小公倍数 extgcd(a, b, &x, &y): ax + by = gcd(a,b) の解(x,y)を得る(拡張ユー…

蟻本 2-5章 のまとめです。各グラフアルゴリズムの概要と例題について。例題は一応ソースコードもつけておきます。 アルゴリズム 最短路問題 ベルマンフォード法 単一始点から他の各点への最短路を求める。負の長さの辺があってもOK。負閉路を持たない場合は…

結果 A問題 無限に落ちて 悲しいな (575) 3完が目標だったので残念。というか今回A問題が一番難しかった！(手をつけた問題の中では) Bも無駄にimos法使ってpretest通ったと思いきやsystem testで落とされたのでご愁傷さま。 レーティングは1469 -> 1431(-38)…

問題 C: 列 - AtCoder Beginner Contest 032 | AtCoder 長さ N の非負整数列 S=s1,s2,…,sN と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないと…

ダイクストラ法とその例題についてまとめておきます。 例題はワーシャルフロイドのやつ使いまわしです（ダイクストラ向きのは二分探索とか絡んで難しいので……） ダイクストラ法とは？ ダイクストラ法(Dijkstra's algorithm)は、グラフのある点から各点までの…

ワーシャルフロイド法のアルゴリズムと例題についてまとめておきます。師匠へのレポートもかねて。 ワーシャルフロイド法とは？ ワーシャルフロイド法(Warshall–Floyd Algorithm)とは、グラフの全点間の最短距離を求めるアルゴリズムです。簡単な3重ループを…

Union-Find木を勉強するために使ったサイトと例題をまとめておきます。 「Union-Find木って何？」「とりあえずUnion-Find木を使えるようになりたい！」という人向けです。 Union-Find木とは？ Union-Find木はグループ分けを管理するデータ構造です。各グルー…

過去問再挑戦キャンペーン実施中。 問題 1からnまでの番号がつけられた点とm個の辺からなるグラフがある。重複辺・自己辺はない。 このグラフのいくつかの辺に色を塗ることでハリネズミを作る。ハリネズミは「尾」と「背骨」からなる。これらは以下のように…

これはね……数学の問題。 問題 n体のサメが丸い机の周りに座っている。i番目のサメと(i+1)%N番目のサメは隣りあっているものとする。 サメiは数s_iを閉区間[l_i, r_i]に含まれる整数から等確率で選ぶ。任意の隣りあうサメi, jに対し、s_i * s_jがpで割り切れ…

問題 1000*1000の正方形のチェス盤がある。この上にn個のビショップを置く。 ある2つのビショップについて、それらが同じ対角線上にあるとき、ビショップは「互いを攻撃している」と言う(AとBの間に他のビショップCがあっても、AとBが同じ対角線上にあれば「…