職場の同僚に誘われて初参加。"Gon the Fox"の一員でした。面白かったので覚えてるうちに自分がやったことの記録や感想を書きなぐっておく次第。 day1 職場のエンジニアメインのチームなので、終業後のオフィスを占領して参加。問題が公開されてとりあえず読…

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

すごく久しぶりに出てみた。 - 250. AliceGame 問題：{1, 3, ..., 2*n-1} の和がx+yになるようなnを選び、その部分和でxが作れるならそのときの要素数の最小値を求める問題。できなかったら-1を返す。 とりあえず Σ(2*i-1) を求めるぜ！って思ってたら n^2 …

rubyのお勉強をしてました。 - A : 高橋くんの研修 終了後に書きなおした版。本番はCライクなコードだった。 print [gets, gets].max_by(&:size) B : 高橋くんの集計 本番で出したコードそのまま。 0を除くのにselectを使ってみたけど、配列の引き算でもいけ…

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

友人の結婚式でワインをたらふく飲んだため、 死にそうになりながらエンジョイ参加しました。 - A : Magical, Marvelous Tour i番目のデバイスが持つコンデンサ数をc[i]とする 要はmax(c[0]+...+c[a-1], c[a]+...+c[b], c[b+1]+...+c[N-1])を最小化する問題 …

巨人-オリックス戦を観戦しに行っていたのですが、 息詰まる投手戦のまま延長に突入したため泣く泣く撤退しての参加でした。 野球の方は12回までやって1-0とかアツい展開だったらしいです。ぐぬぬ…。 - A : Data Packing 最初「1個のディスクにデータは高々2…

この記事を書いてる時に1Bの記事が事故死してしまった…。まぁいいか。 - 250. SixteenBricks 問題：1*1*h[i]の角柱を4×4のグリッドに並べた時の最大表面積を求める問題。 greedyかなぁと思ったけどsample2が倒せなかった。 安全にbitDPとか出来ないかなと思…

先のARCで運を使い果たしたので震えながら参加。 - A : The Repeater アルファベットの登場順を崩すような操作はできない なので与えられた文字列で、アルファベットの登場順が違うのがあったら勝てない 勝てるんだったら文字ごとに適当に個数を揃えてやれば…

奇跡が起きて1位。順位表のスクリーンショットは撮った。 - A : スーパーICT高校生 指定の文字列が部分列として含まれるか調べるだけの簡単なお仕事 A問題だしと思ってムダにO(n^3)で書いた。反省はしていない。 #include <iostream> #include <string> using namespace std; b</string></iostream>…

問題リンク 分岐点全探索で良かったらしい。 村、城、ほこらの各地点からBFSする 経路は 村→分岐点→ほこら→分岐点→城 として表せる 各点Pについて、村→Pのコスト + 2*(ほこら→Pのコスト) + 城→Pのコスト を調べる 倒すモンスターの数をk以下にした時のコスト…

1年半ぶりに参加。 - A : お買い物クライシス 指定の文字を指定の数字に変えるだけの簡単なお仕事 A問題だしと思ってテストせずに投げた。通って良かった。 #include <iostream> #include <string> using namespace std; int main(){ string s; while(cin >> s){ for(int i=0;i</string></iostream>

誰も見てないと思って担当した問題について好き勝手書くコーナー。 ソースコード載せてる以外は解法に触れてないのでご注意？ - 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>…

ヒマでしたが外出エネルギーを使い果たしてたので自宅に引きこもって参加。 - A : 旧総合研究７号館 ウォーミングアップ #include <iostream> #include <string> using namespace std; int main(){ int N, Q; while(cin >> N >> Q){ string res = "kogakubu10gokan"; int minYe</string></iostream>…

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

残念な結果に終わった昨年のリベンジマッチ。 - A : Ticket Swapping 問題文長い…と思って一旦飛ばしたものの、他も難しそうだったので結局Aから。 端から入退場をシミュレーションして、一番新しいチケットで退場すれば良さそう。 そのシミュレーションをど…

お酒の力を借りて本気出した(?) - A : Osmos 制約を何となくしか見てなくて、N≦10^6 と勘違いする。 DPするだけかと思いきやそれは無理そう(と思い込む)。 削除操作を途中に挟んでも無意味そう。 でかくする→マージ出来ないの削除 をシミュレーションして最…

旅行中だったので、11:00-12:30を電車移動にあてて頑張ってみました。 - A : Bullseye 電車に乗ってから30分くらい席が空かなかったのでnexusで問題文だけ見てた。 オーバーフローに気をつけて2分探索すれば良かろう…という印象を受ける。 脳内で組んだ式が…

今さらながら一応書いておくことに。 - 250. FruitTrees 問題：りんごをx間隔、キウイをy間隔、ぶどうをz間隔で植えるとき、異なるフルーツの最小距離の最大値は？ 各パラメータが2000以内 りんごの位置を固定し、キウイの位置とぶどうの位置の全探索を考え…

飲み会開けの酔拳チャレンジ。 - 300. TheLargestString 問題：同じ長さの文字列s, tから同じ位置の文字を抽出したものを繋げてできる辞書順最大の文字列は？ 文字列長を固定すれば、sからは辞書順が最大になるように選ぶのが最善 で、sからとった文字列が同…

時が流れるのは速いなあと(1個前の記事を見て)思いつつ。 - 250. NewArenaPassword 問題：与えられた文字列を、先頭からK文字とった文字列と、後ろからK文字とった文字列が一致するように書き換えたい。最小で何文字変えれば良いか。 文字列長nに対してn-K文…

2ヶ月ぶりくらいに参加してみました。 - 275. KingXNewCurrency 問題：A円とB円の組み合わせで払えるすべての金額を、X円とY円の組み合わせで払えるようにしたい。A, B, Xが与えられるとき、Yのとり方は何通り? ふおお…なんだか数学ゲーっぽいぞ…。 まずは、…

翌朝も仕事だったけど構わず参加した今年最後のSRM。 - 250. Cut 問題：決められた切断回数以内で10cmのうなぎをなるべくたくさん作る 最大で長さ10mのうなぎ…ごくり。 とりあえず、長さが10の倍数のうなぎはお得 (length/10-1)回の切断で、10cmのうなぎがle…

旅路の新幹線の中から更新。たまにはこんな日も良いですよね。 - 250. MagicDiamonds 問題：与えられた自然数nを、最小何個の合成数の和で表せるか求める 合成数なら分解しなくて良いので答えは1 素数だったら、1+(n-1) あたりに分解しておけば2個で表せるの…

B : バクテリアの増殖 この問題を解くための基本アイディアとして n時間後のバクテリア数を x(n) とする ( x(n)^x(n) )%C = ( (x(n)%C)^x(n) )%C である ((x(n)%C)^p)%C = 0 となるpがなければ、x(n)%C のべき乗は値が循環する その循環の長さを y とすると …