ferinの競プロ帳

競プロについてのメモ

2018-10-29から1日間の記事一覧

AOJ2401 Equation

問題ページ 解法 変数は高々10種類なので'T'と'F'の割り当ては2^10通りしかない。=で分割しておけばequationを用意する必要はない。構文解析はO(|S|)でできるので割り当てを全通り試して等しくならないものがあれば'NO'、そうでなければ'YES'を出力する。以…

AOJ2613 Unordered Operators

問題ページ 解法 まず演算子の優先順序が*>+>-となっている場合のBNFを書いてみる。左再帰と演算子の優先順序に気をつけつつ書くと以下のようになる。 <expr1> = <expr2> ['-' <expr2>]* <expr2> = <expr3> ['+' <expr3>]* <expr3> = <factor> ['*' <factor>]* <factor> = '(' <expr1> ')' | <number> 他の優先順序の場合についても同様にBNFを書ける。</number></expr1></factor></factor></factor></expr3></expr3></expr3></expr2></expr2></expr2></expr1>…

Tenka1 Programmer Contest E - Equilateral

問題ページ 考えたこと 45度回転 これ以降チェビジェフ距離で考える 距離が等しい点はある正方形上の点になる 2点を固定してその2点のどちらとも距離が等しい点を探す 各点を中心として2点間の距離*2を1辺の長さとする正方形を書く 2点どちらとも距離が等し…

Tenka1 Programmer Contest D - Crossing

問題ページ 考えたこと とりあえず実験 部分集合の大きさを4に固定してみる 1つ目の集合に異なる要素が3個は入っていないと、積集合の大きさが1となる条件を満たせない 1つ目と2つ目、1つ目と3つ目、1つ目と4つ目については以下のように取れば条件を満たす 1…

Tenka1 Programmer Contest C - Align

問題ページ 思考過程 ジグザグにするのがよさそう 一番小さい、大きいのを端に置くと損してる ジグザグな山みたいなのをつくるのがよさそう 一番小さいのを中央に置くか、一番大きいのを中央に置くかで2種類あるのに気をつけながら書くと通った #include <bits/stdc++.h> us</bits/stdc++.h>…