メンバー紹介 ferin:基本的にはBとDを担当する。 div9851:基本的にはAとCを担当する。(←予選通過の立役者！！) olphe:基本的にはEとFを担当する。幾何が出たらferinさんと1問交換、構文解析が出たらdivさんと1問交換 模擬国内前 僕が入学してすぐにチームが…

ルール 最初正気度を250持っていて、毎ターン4~6正気度を失う。ただし、2マス以内(壁を挟んでもよい)に他の冒険者がいると1~3で済む。 敵はトンベリみたいな見た目のものと死神みたいな見た目のものがいる。 前者は毎ターン1番近い人を追いかける。冒険者と…

今年も出ました！ 迷路君とkenさんとチームを組んで参戦。 とりあえず迷路君が1問目を、僕が2問目を、kenさんが3問目を見ようかな見たいな話になったのでBを見る。 文字列の長さが15で32文字までに収めてね！って言われたので明らかに2個+アスタリスクが2個…

和がNで数列の全要素のGCDが1となる数列の数を求めたい。 a(n) = sum_{d|n} mu(n/d)*2^(d-1) この式で表せるらしいが全然意味が分からなかったのでメモしておく。 d | n……dはnの約数という意味。 sum_{ }……{ }内のすべての要素について何か処理をする。 mu()…

1日目King's Graphはどうでもいいので、2S*2S四方のフィールドに元のグラフの頂点を乗せていくことにする。(King's Graphへの変換後に辺が伸びているかはチェビシェフ距離が1か否かで判定できる)とりあえず愚直貪欲を書いてみようと思って、頂点0をフィール…

前泊ダメだよとのことだったので朝5時ぐらいにお家を出て新幹線で東京に向かうことに。ほぼ始発だったのでめちゃくちゃ混んでて怖いね。 品川でりかちゃんとうしさんと合流して大森海岸へ、 4号車マンやが — olphe (@_olphe) 2017年11月2日 僕も4号車です — …

画像が与えられるので、指定された数の半透明な円を描いていって元の画像に近づけようという問題。 作成途中の画像の状態だけが重要で配置の順番はどうでもいいと思ったのでビームサーチ案を捨て、貪欲に円を配置していくことを考えた。 貪欲パートは、ラン…

ABDの3完で239位 A問題 数字の数と作りたいMEX,N個の数が与えられる。数字を出現させたり消したりしてMEXを指定の数にしたい。 配列を用意して舐めてあげればよいです。 http://codeforces.com/contest/862/submission/30502250 B問題 木が与えられる。二部…

3完99位 Unratedめ… A問題 文字列が与えられる。その中に2種類以上の子音が3個並んでいたら切る問題。 切る回数を最小にしたい。 前から貪欲に調べていって条件を満たし次第切ればよい。 貪欲なのでO(N) http://codeforces.com/contest/860/submission/30422…

5完122位でした！すごい！Round2も頑張るぞ！ A問題 本選に25人参加できるコンテストがあり、それらの参加者のうち何人かの予選での順位が与えられる。本選参加を辞退した人は最小で何人かな？ http://codeforces.com/contest/859/submission/30389464 B問題…

EasyとMedが通って33位 1573->1565(悲しいね) Easy 文字列sとtが与えられるので{0,o},{1,l},{m,n}の入れ替えだけでs->tにできるか判定する。 Med 数列が与えられるので、任意の3数の和が9の倍数にならない最大の組み合わせを求める。bitDPをしたがうしさんに…

4完104位、悲しいね A 舐めて求める数を数えます B 何個数字使うかを全探索してうまくいくときに出力する。 C v[i]はnum[i][0]~num[i][W-1]のLCM、u[i]はnum[0][i]~num[H-1][i]のLCM 条件を満たしていたら出力 D 数がNの時は、N/2と(N+1)/2の結果から導き出…

A 現在の時刻よりも早く出発すべきだった便のうち遅延コストのでかいものから飛ばしていく。自明。 1958->1910 こどふぉ、レート上げるの難しすぎるなあ

マスがあってチェスのナイトを置く。 あるマスを攻撃できるナイトの数がマスに書かれた数字に近づくようにしたい。 舐めつつ焼きなました。 https://github.com/olphe/MM/blob/master/MM_KnightsAttacks~Randomized.cpp なんかシステスと競技中のジャッジの…

MM94お疲れさまでした。 まず全体的な方針として左上から詰めていく(順列を表すvector(以下ansとする)に前から順番に要素を追加していく)ことにした。 理由としては以下の2点 ①どこに一番得点が高い組み合わせを置いても同じだと思ったから。 ②左上にそろえ…

N両の電車とM量の電車が与えられる。それぞれはI列車とO列車のみで構成される。 順にどちらかの先頭の車両を取っていき、IOIOIOIOIのようにIとOか交互に並び、且つIが端にあるように並べたとき、最長の長さを求める問題。 なお、電車はあまらせてもよいし、…

N個の町、M本の道、K個のショッピングモールがある。 ショッピングモールは町の中にある。 町及び道の中で一番近いショッピングモールまでの距離が最大の値を求める問題。 まず、dijkstraで町までの距離を求め、各辺について辺上で一番遠い点を求める。 計算…

H＊Wの看板にN個のテープが貼ってある。色を塗らなければならないスペースが何個あるかを求める問題。 座標圧縮をして、queueで何個あるか探す。 計算量は(N^3)だが定数が小さい。 難易度は7程度に感じられた。 http://judge.u-aizu.ac.jp/onlinejudge/revie…

N行に石があり、それぞれの行にある石の数と、位置と滑りやすさが決まっている。 向こう岸まで跳んで行った時の最小の危険度を求める問題。 なお、一行飛びジャンプはM回までできる。 dp[i行目までで][j回までの一行飛びジャンプを使い][i行目のk個目の石]に…

N個の棒があり、そのそれぞれにひもがつながっている。一番上の棒をつるしているひもを除いては、ひもの下には棒かおもりがある。 角棒について、自分をつるしているひもより左の長さ、右の長さ、左につるしている棒の番号、右につるしている棒の番号(おもり…

N個の町、K本の道がある。各町にはタクシー会社が存在し、それぞれ決められた数までの道を移動できる。また、料金も決まっている。 １～Nに移動するために必要なコストの最小値を求める問題。 基本的にはdijkstraでよいが、各頂点を訪れるごとに移動できる場…

N種類の魚がいて、それぞれの生息範囲が直方体で与えられる。 同時にK種類の魚が存在しうる領域の体積を求めよという問題。 まず、座標の範囲が0~1000000と非常に大きいにもかかわらず、魚の種類は最大でも50なので無駄っぽい。なのでそれぞれについてソート…

N*Nのビンゴに1~Mまでの数字を入れる。和をSにしないといけないという条件の下で、何通りのカードが作れるかな？という問題。 dp[i個の数字で][jを作る]通り数のDPを組む。大きいものから見ることで1次減らせる。 計算量はO(NMS) 難易度は7程度に感じられた。…

Nチームがリーグ戦を行った。M個の勝敗の情報が与えられたとき、順位表のうちの一つを出力せよ。という問題。 なお、引き分けの試合はなく、同順位のチームもなく、順位が上のチームが下のチームに負けなかったことが保証されている。 勝ったチームから負け…

N個の屋台をT時間の間に遊びたい。また、時刻Sの時に花火もみたい。 一つの屋台で遊ぶ時の楽しさと時間が与えられるので、楽しさを最大化しようという問題。なお、屋台は番号の若い順にしか回れず、一つの屋台では一度しか遊べない。 N個目までの屋台につい…

N個の店があり、それぞれJかOかIが決まっている。3店を選んでJOIを作る。 なお、3店は番号の小さい順に選ぶ必要がある。 ここで、任意の場所に任意の文字の店を一つ追加して、JOIを作る通り数を最大化したいという問題。 まず、最初の段階でJOIの通り数を数…

N個のオレンジがあり、それぞれ大きさが決まっている。一個の箱には最大でM個オレンジを詰められ、箱に詰める際のコストはK+num*(MAX-MIN)で求められる。 (numは箱に詰めたオレンジの数。MAX,MINは箱に詰めたオレンジの大きさの最大値、最小値) コストを最小…

N個に切られたホールケーキがあり、それぞれの大きさが与えられる。 先攻はまず好きなピースを取り、それ以降後攻は空間が隣にあるケーキの内で大きいほうのケーキを、先攻はそのようなケーキの内好きなほうを取る。 先攻の大きさを最大化しようという問題。…

N個の饅頭があり、それぞれ価格が決まっている。 M個の箱があり、それぞれ何個饅頭を入れられるか、購入の際のコストが決まっている。 利益を最大化しようという問題。 まず、饅頭をi個売る時は、高いもの時からi個売るのがいいので、ソートして累積和を求め…

N個の電球が並んでいて、それらは点いているか消えている。 一回だけ、連続する電球の点灯状態を反転させて、交互に並べたい。 最大で何個できるかな？という問題。 まず、連続して同じ状態の電球が並んでいるところをリストアップしておき、それらの中で隣…