ひどい問題だった。参加記のようなものも書いたけど3日目でほぼ最適解の出せる解法が出たので先に解法を書いておく。 最終日に確実に最適解が出るようにしたのでそれも追加した。

keyword 2部マッチング C++ 概要 ただの2部マッチング。ソース略。これで400問に達した。

keyword 集合 構文解析 C 概要 和と差と積の入った集合演算をする問題。 集合の個数が26個以下なのでビットで扱う。構文解析の部分は、よくあるBNFで定義してから実装した。

keyword アナグラム C 概要 2つの文字列が与えられる。最低何文字削れば2つの文字列がアナグラムになるか求める問題。 出てくる文字をカウントして違っている分だけ削れば良い。

keyword C 概要 _とアルファベットで構成された文字列が与えられる。その文字列のいくつかをつくって別の文字列がつくれるかどうか判定する問題。_はワイルドカードとして使える。 _以外の文字を使えるだけ使って処理しきれなかった文字の数と_の数を比較す…

keyword 動的計画法 回文 C 概要 長さ5000以下の文字列が与えられる。このとき文字を最低いくつ削れば回文になるか求める問題。 今考えてる文字列の両端が等しい場合は両端を取り除いた文字列を考えれば良く、そうでないときは両方取り除いた場合やいずれか…

keyword 構文解析 C 概要 pはvalid。sがvalidなとき、Nsはvalid。s,tがvalidなとき、Cstはvalid。このルールの元で、与えられた文字列がvalidかどうかを判定する問題。 素直に実装する。あと多分メモ化は意味ないはず。

keyword ゲーム C 概要 アリ本を参考にして解いた。ソース略。

keyword C 概要 D( 実装するだけ。

keyword 約数 C++ 概要 10000以下の整数が10個与えられる。その積の約数の個数をmod 10で求める問題。 それぞれの整数を素因数分解するだけ。

keyword カレンダー Java 概要 y年m月d日が何曜日か求める問題。 JavaのCalendarを使う。Calendar.MAY = 4などとなっていることに注意。

keyword 動的計画法 C++ 概要 N( dp[iターンまで終了][残っている数列の左はどこか]でDPする。最後の処理に引っかかった。

keyword n進数 任意精度浮動小数 Java 概要 8進数の小数が与えられるので10進数の小数に変換して出力する問題。 JavaのBigDecimalを活用する。入力文字列を8進数として解釈するコンストラクタはBigDecimalに無いのでいったんBigIntegerに変換してから元に戻…

keyword C++ 概要 a,b,...,z,ab,...,az,bc,...,yz,abc,...とアルファベットが並んでいる。文字列(10文字以下)が与えられるのでそれが何番目のものか求める問題。 シミュレーションだと間に合わないので適当に2項係数などをつかってスキップする。

keyword C++ 概要 多項式の係数が与えられるのでそれを多項式の形にして出力する問題。 形式が面倒だけど基本的にはやるだけ。

keyword 中央値 C++ 概要 数列の中央値を求める問題。 ソートするだけ。partial sortしたらもしかしたら速くなるかもしれない。

keyword 整数 10進数 C++ 概要 2282:The Counting Problemの文字0のみに関する問題。

keyword 構文解析 論理式 BruteForce C++ 概要 真偽値をもつ元が5つと、それぞれの組み合わせからなる論理式がある。論理式の値が真偽値の任意の組み合わせに対して1となるかどうかを判定する問題。 まずは式を構文解析する。あとは真偽の組み合わせ2^5全通…

keyword 行列 BruteForce C++ 概要 n*n(n サイズが小さいので全探索する。それなりに高速化する必要があるが、対称性から1列目は固定する、実際に回転はしない、和の計算を全てのパターンに対してn^2でしない、などすればよい。

keyword 整数 10進数 C++ 概要 mからn(0

keyword シミュレーション C++ 概要 数直線上に石が置かれていて、人が原点にいる。人は原点に近い石を拾いにいく。ある時間内に石をいくつ拾えるか求める問題。 人の動き方は完全に決まっているので、シミュレーションするだけ。

keyword C++ 概要 でかいチェスボードの中に8*8のチェスボードを置く方法は何通りあるか求める問題。 偶奇に気をつけてやるだけ。

keyword 構文解析 C++ 概要 各行列のサイズが与えられる。このとき、(AB)Cなどの文字列が与えられるので、行列の積が計算できるときは要素の積の計算回数を出力する問題。 パースできれば答えを出すのは簡単。トークンがぴったり1文字分なので処理が簡単。

keyword 整数 多倍長 Java 概要 a,b,t(0

keyword 探索 C++ 概要 N*N (N 探索するだけ。

keyword C++ 概要 kn!を満たす最大のnを求める問題。積の計算に時間がかかるため、Javaで多倍長使ってもTLEする。なので対数で処理する。精度とかあんまり気にしなくても通った。

keyword 動的計画法 Java 概要 数字列が与えられる。それを(a_0-a_1-...-a_n)_dの様に表す方法は何通りあるか求める問題。a_i

keyword Union-Find C++ 概要 学生がN( union-findするだけ。

keyword シミュレーション C++ 概要 ウェブブラウザの戻るや進むや新しいウェブページに移動などのコマンド列が与えられる。その度に今表示しているウェブページのアドレスを出力する問題。 実装ゲー。queueを使うもよし。配列で処理するもよし。

keyword C++ 概要 数字を指定された大きさのアスキーアートで表現する問題。 実装ゲー。