E - Symmetric Grid 問題概要 それぞれのマスにアルファベットの小文字が入った，H×W (H, Wは12以下) のマス目が与えられる． 行の交換と列の交換を繰り返し，このマス目を点対称にできるか判定する． 解法概要 行の交換と列の交換の操作の順番は変えても問…
City Merger | Aizu Online Judge 問題概要 長さ20文字以下の都市の名前が最大14個与えられる．これらのすべてを部分文字列として含むような文字列の長さを求める． 解法概要 与えられた都市の名前の個数をnとする．また，都市の名前の長さの最大値をlとする…
Flipping Parentheses | Aizu Online Judge セグ木の練習がしたい + 括弧列の問題がすきということで難しい問題にチャレンジ． 問題概要 長さNのバランスの取れた括弧列が与えられる．これに対し，Q個のクエリが与えられる．クエリは以下の内容である． 括弧…
B - Neutralize 問題概要 N個の整数値からなる数列$ b = \{ b_1, b_2, \cdots b_n \} $について，連続するK個の要素を全て0にするという操作を好きなだけ繰り返して良いとき，数列に含まれる値の和を最大化する． ($ 1 \leq K \leq N \leq 10^5$) 解法概要 …
昨日7/6 (金)，チーム KatsuT0shiのメンバーとしてICPCの国内予選に出場しました．参加者の皆さん，関係者の皆さん，お疲れ様でした． KatsuT0shiは情報系のM1 3人で構成されるチームです．3人のうち私を含む2人は95年生まれでこのチームで出られるICPCは最…
Discrete Speed | Aizu Online Judge 問題概要 N$ ( N\leq 30)$ノードMエッジの多重辺のない無向グラフ上を移動してスタートノードSからゴールノードGを目指す．SからGに行くまでの最短時間を求めたい． エッジにはそれぞれ制限速度c$ ( c\leq 30)$と距離d$ …
Carrot Tour | Aizu Online Judge 問題概要 合計移動距離がr以下(0 < r < $ 10^4$)になるように20個以下の都市を回る． 都市を訪れる回数を最大化せよ． ただし，進む向きを一度に$ \theta$度より大きく変えることはできない． 解法概要 都市が20個以下とい…
問題概要 通路が"."，壁が"#"で表される最大50×50の迷路がある．スタート地点$ (r_1, c_1) $からゴール地点$ (r_2, c_2) $に行くまでの所要時間を求める． ただし，"."のある地点から4近傍の"."に移動するのに1秒かかる．また，今いる"."と同じ行または同じ…
問題文原文 問題概要 ミサイル保有国がn国ある．それぞれの国はm個のミサイルを保有している．各ミサイルはcapability cをもつ． 各国のミサイルのcapabilityの和の差をd以下に保ったまま，全てのミサイルを廃棄できるかを答えよ． ただし，各国はミサイルを…
クックパッドさんの 1day インターンシップに参加しました． 「技巧を駆使した実用性のないプログラムを作成する『超絶技巧プログラミング』を習得する」という，インターンシップらしからぬテーマ (偏見) に惹かれて参加を決めました． はじめに軽く自己紹…
E - Meaningful Mean 問題概要 長さNの整数列$ a=\{a_1, a_2, \cdots, a_N \} $の空でない連続する部分列について，算術平均がK以上のものの数を求める． 解法概要 「算術平均がK以上の部分列」が満たす条件を変形してみる． $$ \begin{align} \frac{1}{r-l+…
E - Range Minimum Queries 問題概要 長さNの数列Aに対して，長さKの連続する部分を選びK個の要素の中で最小のものを削除する操作をQ回繰り返す． 削除される値の最大値と最小値の差を最小化する． 解法概要 Nはたかだか2000なので，最小値を決めうちしても…
E - Sorted and Sorted 問題概要 1からNまでの数字が書かれた，黒・白のボールがある． この2N個のボールを，それぞれの色について数字が昇順になるように並べ替える． 隣同士のボールの交換を繰り返して並べ替えを行うとき，最小の交換回数を求める． 解法…
A - アナログ時計 問題概要 $ h $時$ m $分$ s $秒からスタートして，分針と秒針，時針と分針が重なった回数がそれぞれ$ C_1 $回，$ C_2 $回であるときの最小・最大の経過秒数を求める． 解法概要 $ C_1 \leq 10000 $なので，愚直に針の動きをシミュレートし…
codeforces.com 問題概要 二次元座標上に直線 解法概要 点と点が1回遭遇するたびに2つの点の経験値が1ずつ増えるので，全体の経験値の和は2増える．すなわち，求めるべき全ての経験値の和は点同士の遭遇回数の2倍の値である．また，全ての点は等速直線運動し…
問題概要 ちょっとまとめるのが面倒なので，問題文原文を見てください (手抜き) 解法概要 長方形の領域になっている部分を貪欲に取り除いていく．取り除かれた長方形の領域は，次の長方形を探す際に長方形の領域として使って良い (使わなくても良い)． 長方…
問題概要 駅$ 1 $から駅$ N $までの$ N $個の駅に対し，$ M $個の路線が存在する． $ i $番目の路線は駅$ p_i $と駅$ q_i $を相互に結び，会社$ c_i $によって運営されている． 駅$ 1 $を出発地，駅$ N $を目的地とするとき，異なる会社の路線への最小の乗り…
問題概要 $ n $要素からなる数列$ a = \{ a_1, a_2, \cdots, a_n \} $が与えられる．$ a_i $は，テレビシリーズのシーズン$ i $のエピソードが第$ a_i $エピソードまで存在することを表す． シーズン$ i $のエピソード$ j $とシーズン$ j $のエピソード$ i $…
ブログ記事に書くと定着度が高まることがわかったので，これからは解いた問題を積極的に記事にしていこうと思う． 問題概要 $ N $要素からなる数列$ a = \{ a_1, a_2, \cdots, a_n \} $，$ b = \{ b_1, b_2, \cdots, b_n \} $に対し，以下の操作を行う． あ…
問題概要 $ N $頂点からなる木があり，$ i $番目の頂点には最初$ A_i $個の石が置かれている． 相異なる2つの葉を選び，その2頂点間のパス上にある頂点から石を1個ずつ取り除く．ただし，パス上の頂点で石が1個も置かれていない頂点がある場合，この操作はで…
問題概要 高橋くんと青木くんが Nim (石取りゲーム) をする．ただし先攻は高橋くんで，それぞれの山から1回に取れる石の数に以下のような制約がある． $ N $個の山があり，$ i $番目の山は最初$ A_i $個の石がある． ある地点で$ i $番目の山にある石の数を$…
codeforces.com 問題概要 学び 解法として「和をkで割ったあまりがvをkで割った余りと等しくなるようなタンクの部分集合」がほしいと考えていたが，トレース？付きのDPがなかなか書けなかった． 以下のソースコードでは2次元配列used[i][j]を使って，「1から…
問題概要 整数 長さは 上記2条件を満たす文字列中で，同じ文字のみからなる部分文字列のうち最長のものの長さが最も短い． 上記3条件を満たす文字列中で辞書順最小である． 解法概要 "同じ文字が続いても良い数" ABB…B(Bがk個) ABB…B ABB…B…のprefix AA…A(A…
あけましておめでとうございます． Twitterで繋がっている皆さんが振り返り記事を投稿しているのを見て，私もやってみたくなりました． が，新年に余裕で間に合いませんでした． この記事を書き始めた地点では2017年だったので，あまり気にせず書き進めるこ…
問題概要 与えられる文字列sと'yahoo'の0回以上の繰り返しの文字列との編集距離を求める． 解法 普通の編集距離DPを元にいくつかアレンジを加える． 編集先文字列はインデックスjについてj%5が0,1,2,3,4番目の文字がそれぞれy,a,h,o,oの文字列と考える 'yaho…
問題概要 N個の文字列が与えられる． 解法 まず， 次に， " (こうして書き出してみると割と"やるだけ"……) ソースコード #include<iostream> #include<string> #include<vector> #include<set> #define rep(n) for(int i=0;i</set></vector></string></iostream>
この記事は情報系を勉強する女子大生 Advent Calender 2017の16日目の記事です． qiita.com 16日目担当のNoiminです． 情報系学科の学部4年で，自然言語処理の研究室に所属しています(自然言語処理は本アドベントカレンダーでもasai0304さんが取り上げてくだ…
↓のAdvent Calenderに参加登録したことをきっかけに，以前から始めようか迷っていた技術ブログ(?)を始めることにしました． qiita.com 競技プログラミングの精進記録やコンテスト参加記，NLP関連のTips等をメインにしていけたらいいなぁと思っています． 自…
