くるくるドア(模擬国内予選G)の担当者であるnotさんとMi_Sawaさんが揃ってGを解いておられたので， ライブラリをぺたぺたして解いてみた次第． 方針は，外周の候補を列挙後に折り線基準で偏角ソートして， どっちかの多角形に内包(strictly)されているものを…

いつものチラシ裏。 - C : 壊れた暗号生成器 writerでした。国内予選レベルの構文解析の練習にと考えてみた問題。 ?数制限はかなり迷った結果、謎の組織の会議によって3個制限を付けることに。 上位層は置換でサクッと通すだろうと思っていたら、意外と全探…

誰も見てないと思って担当した問題について好き勝手書くコーナー。 ソースコード載せてる以外は解法に触れてないのでご注意？ - E : Putter Testerでした(writerはir5さん)。 サンプルが見た目より強いのでこれ通れば大体ACじゃねと思ってましたが、そうでも…

D. 素数洞穴解法 洞穴のマップを頑張って生成する 各洞穴への到達時の最適解は上の洞穴から順に確定させていける 最適解：pair(通った素数洞穴の数、 最後に通った素数洞穴の番号) の最大値 全ての洞穴について到達時の最適解を確定させ、最も良かったものを…

E. つながれた風船解法 色々やり方はあるけど、ここでは円の問題に落として2分探索する方針 高さhまで風船が上げられるかという問題を考える 高さを決めれば、各ヒモの先端がどの範囲を動けるかは円で表せる その円に共通部分が存在すれば、風船は高さhに上…

C. 階層民主主義解法 第1段階では過半数ギリギリで勝つのが最適 第k段階(k>1)について考えると、 過半数ギリギリの選挙区で勝てば良い 勝つのに必要な票数が少ない方から半数の選挙区でだけ票を取る 負けても良い選挙区では0票としてしまって良い という感じ…

B. ICPCの順位付け解法 シンプルなシミュレーションの問題 基本的には問題文で言われたとおりに実装すれば良い 順位付けはpairとか使って頑張っても良いけど、ここではoperatorを定義。 #include <iostream> #include <vector> #include <algorithm> #include <cstring> using namespace std; class</cstring></algorithm></vector></iostream>…

A. 整長方形解法 A問題だし、男は黙って全探索という感じでやってみた 答えの高さと幅は150を超えないので、あり得る答えを全通り試しても余裕 全列挙→ソート→upperbound もアリ #include <iostream> using namespace std; int main(){ int h, w; while(cin >> h >> w </iostream>…

Writerした3問+何となく解いたGのソースをコッソリ貼ってみます。 初Writerでしたが、色々難しいなと痛感しました。 - C : 双子の読書感想文 2年前くらいに思いついたものの問題設定が考えつかず放置してた問題 ある性質に気づけばあとは国内予選レベルの実…

I. Operatorなんか講評よりオーダーが良かったので晒してみます。 嘘の告発は(ry 一応、二分探索＋ちょっとではありません。解法 基本はJAGの講評に準拠 オペレータの数が小さい方からシミュレーション オペレータは区別しなくて良いので各時間でヒマな人数…

F. Two-Wheel BuggyAOJに投げてみたらコードサイズがだいぶ小さかったので晒してみます。 嘘の告発は大歓迎です。解法 直進か曲がるかの2通りに場合分けして処理する 車の状態は，2個のタイヤの中点pと車の方向dirによって管理 直進(左右の回転数が一緒)はや…

AOJで通ってしまったので、その記録を晒してみます。F. 古い記憶基本的な方針は以下の通りです。 ピースをつなぎ合わせて(深さ優先で)文字列を生成していく 改ざん文書に対し編集距離d以下のものが出来たら答えに追加 さすがにナイーブに書いたら遅すぎたの…

E. 最強の呪文下に書いた話で、 倍くらい調べればループを使って辞書順を小さくする文字列が見つかる ゴール以外で6*(ノード数)くらいでループなしより辞書順で小さくなったら"NO" とか言ってるので，倍くらい調べなくて良い事に気付きました。 "NO"になる判…

G. レーザー光の反射解法 レーザーが当たる鏡の順番を全列挙する 反射回数は高々5で，鏡の枚数も高々5なのでそんなに多くない 各反射順ごとに，レーザーの照射角度を求める 反射順に鏡を選び，照射地点の鏡像を取っていく 最終的に得られる照射地点の像の方…

id:kusano_progさんに先に書かれてしまいましたが…。E. 最強の呪文解法 [現在の呪文の長さ][現在地] を使った拡張ダイクストラ 文字列A, B, Cに対して、一般にmin(A+C, B+C) = min(A, B) + Cは成り立たない が，AとBの長さが同じなら成り立つので文字列長ご…

D. ぐらぐら解法 仕様どおりに実装するだけの簡単なお仕事 以下の実装では、再帰を使った深さ優先探索を行っている isStable:(_y, _x)の位置にあるピースが安定ならtrueを返す Mは関係するピースの座標値(+0.5)の合計 cntは関係するピースの個数 重心のx座標…

C. ポロック予想解法 動的計画法 Nを何個の正四面体数で表せるかは，1〜N-1の答えを使って求められる ansA[i]を「iを表すために必要な最小の正四面体数の数」とする 正四面体数1, 4, 10, 20, …に対し， ansA[N] = min(ansA[N-1], ans[N-4], ans[N-10], …) + …

B. 迷図と命ず解法 入口から幅優先探索 データが綺麗に成形してあるので、文字列のまま持っておくと楽 座標を2倍すると文字列上での現在地に対応する #include <iostream> #include <queue> using namespace std; char dx[] = {1, 0, -1, 0}; char dy[] = {0, 1, 0, -1}; int </queue></iostream>…

こっそり国内予選の問題を解いたので、記録でも書いてみます。 ちなみに、Fは自分の実力では謎。 あと、問題の概要は問題文が日本語なので省略します。A. 角角画伯，かく悩みき解法 問題文通りに各タイルの位置を計算する i番目のタイルの位置(x, y)を配列で…