裏紙

ほぼ競プロ、たまに日記

CF 677 D - Vanya and Treasure

問題 Problem - D - Codeforces 問題概要 のグリッドとして表される宮殿の中にいる.それぞれの部屋の中には引き出しがあり,上から行左から列の位置には番の引き出しがある.番の引き出しには,番の引き出しを開けるためのカギが入っており,番の引き出しは…

CF 653 D - Delivery Bears

問題 Problem - D - Codeforces 問題概要 街で熊を雇って運び屋業をすることにした.街は頂点が個,辺が本ある有向グラフとして表される.各辺には耐えられる重量が決まっている.1回の配達を,1頭の熊が頂点から頂点へ運搬する際のパスとして表現する. 今…

2016/7 Solved(2)

7/17 AGC 001 C - Shorten Diameter 木の中心を使って全探索する問題.中心という概念を初めて知った. ARC 047 B - 同一円周上 解説を見ながら.まずX=x-y,Y=x+yの座標変換を行うことによって,マンハッタン距離上等しい点が軸に平行な正方形のようになるよ…

ARC 019 C - 最後の森

問題 C: 最後の森 - AtCoder Regular Contest 019 | AtCoder 問題概要 の広さのグリッド上を村からスタートしほこらを通ってから城に向かいたいが,特定のマスには強敵がいて,そのマスに止まると戦闘が起こる.強敵との戦闘は回以内に抑えたい(戦闘が終わっ…

ARC 058 E - 和風いろはちゃん / Iroha and Haiku

問題 E: 和風いろはちゃん / Iroha and Haiku - AtCoder Regular Contest 058 | AtCoder 問題概要 長さの数列を考える.数列の各要素について,値は1以上10以下である.数列がXYZを含むものは何通り有るか答えよ. ただし,XYZを含むとは: を満たすが存在す…

yukicoder No.371 - ぼく悪いプライムじゃないよ

問題 No.371 ぼく悪いプライムじゃないよ - yukicoder 問題概要 の合成数のうち,最小の素因数が最大のものを答えよ.そのようなものが複数ある場合には元の整数が最も大きい物を答えよ. アイデア まず,整数に対して,最小の素因数を調べることはでできる…

2016/7 Solved(1)

7/1 AOJ 1092 - Make KND So Fat 予算に関して増やせる体重の最大値を保存するDPをすればよい.最初逆に体重に関するDPを考えてしまっていたが,増加しうる体重の最大値が大きく,おそらく間に合わない. 7/2 ABC 041 A - 添字 ABC 041 B - 直方体 ABC 041 C…

2016/6 Solved(2)

6/16 S8PC #2 B - Division 2 満点解法みて,めっちゃ賢い...ってなった.後ろから埋めていく(この状態にたどり着くには前の段階で割るか割らないかのどちらかだが,割る場合は前との積がn以下,割らない場合はそこのaで割り切れないことが条件になっている)…

ACM-ICPC 2016 国内予選 に参加しました

そもそもACM-ICPCって何って方はここを見てください(http://icpc.iisf.or.jp/2016-tsukuba/?lang=ja). チーム決め 4月くらいには,メンバーが集まり,この3人で出ようということになっていたと記憶しています.3人とも学部4年でしたが,ICPCに参加するのは…

CF 670 F - Restore a Number

問題 Problem - F - Codeforces 問題概要 ある数字があり,それにの桁数を合わせて書いておいた紙があったが,桁の順番がめちゃくちゃになってしまった.(例:として3342が与えられる時,その桁数は4なので紙には33424と書かれるがその順番が入れ替わって3434…

2016/6 Solved(1)

6/1 お誕生日コンテスト A - A + B A+Bが特殊な形で実装されているので穴を探す問題.3番に関しては適当にいじってたら反例を見つけてしまったのでよくわかってない... 6/2 TDPC E - 数 シンプルな桁DP.dp[now][sum][small](今上からnow文字目に注目してて…

AOJ 0537 - Bingo

問題 Bingo | Aizu Online Judge 問題概要 ビンゴカードは正方形となっているが,実際これは1次元配列として考えても差し支えがない. つまり,「要素数がで,各要素の値が以上以下で,全ての要素の合計がであるような厳密に単調増加する数列として考えられ…

GCJ 2016 Round2 B - Red Tape Committee

問題 Dashboard - Round 2 2016 - Google Code Jam 問題概要 人の人がいる.そして,YesかNoかで投票をしてもらい多数決をしようとしている.人に関して,Yesに投票する確率がである(つまり,Noに投票する確率は). 今,この中から人を選んでその人に投票し…

GCJ 2016 Round 1C C - Fashion Police

問題 Dashboard - Round 1C 2016 - Google Code Jam 問題概要 個のジャケットと個のパンツと個のシャツを持っている.これらの関係としてが成り立つ. 1日ごとに,その中から1つずつジャケットとパンツとシャツと選び,outfitとして着る.その日の夜に選択…

GCJ 2016 Round 1B C - Technobabble

問題 Dashboard - Round 1B 2016 - Google Code Jam 問題概要 先生が学会での発表者を募集している.参加したい生徒たちが発表のタイトルを英単語2つで紙に書いていく.ただし,既に書かれているタイトルは書いていけない(同じタイトルはダメ).締め切りの後…

GCJ 2016 Round 1B B - Close Match

問題 Dashboard - Round 1B 2016 - Google Code Jam 問題概要 2チームが対戦していて,表示板にそれぞれのチームのスコアが表示されている(それぞれのスコアについて,先頭に複数の0がある可能性もある).いま,表示板のいくつかの表示部分が壊れてしまって…

GCJ 2016 Round 1A C - BFFs

問題 Dashboard - Round 1A 2016 - Google Code Jam 問題概要 人の子どもがいる.それぞれの子どもにはIDがまでそれぞれ与えられている.そして,どの子どもも1人ずつbest friend forever(BFF)を持っていて,それが誰なのかわかっている. 何人かの子どもの…

GCJ 2016 Round 1A B - Rank and File

問題 Dashboard - Round 1A 2016 - Google Code Jam 問題概要 兵士を1辺がの正方形のグリッドに1人ずつ立たせる.兵士にはそれぞれ身長があり,身長に関してどの行を左から順にみても厳密に増加する列になっているし,どの列を前方からみても厳密に増加する…

GCJ 2016 Qual Round D - Fractiles

問題 Dashboard - Qualification Round 2016 - Google Code Jam 問題概要 gold(G)のタイルとlead(L)のタイルが一直線上に並んだものがある.それはフラクタル構造を持っており,次のような規則を満たしている: 2つのパラメータによってフラクタルは決定づけ…

2016/5 Solved(2)

5/17 AOJ 1517 - Challenge from Grandfather 行列回転のところでバグらせて悩んでしまった。また、島反転は、与えられた位置からBFSすることによってどのエリアが反転するかを求めることが出来る。 AOJ 0232 - Life Game 確率のDP。dp[いるマス][持っている…

GCJ 2016 Qual Round C - Coin Jam

問題 Dashboard - Qualification Round 2016 - Google Code Jam 問題概要 jamcoinという長さの文字列がある.jamcoinは以下の性質を満たす: 全ての桁が0か1で構成される. 最上位の桁と最下位の桁は必ず1である. この文字列を2進数から10進数のどの数とし…

CF 676 E - The Last Fight Between Human and AI

問題 Problem - E - Codeforces 問題概要 多項式が与えられる.初期状態ではこの多項式の係数は全て未定になっている. 人間とAIがゲームをする.まずはじめに,ある整数が与えられる.そして,AIが先手となりゲーム開始となる.ターンごとに,そのターンが…

SRM 660 Div1 Easy - Coversta

問題 TopCoder Statistics - Problem Statement 問題概要 行列のグリッドが与えられる.各グリッドの中には0~9のいずれかの数字が書かれている.そして,stationをに設置すると, ()内に書かれている数字の合計をポイントとして得ることが出来る. 今,stati…

AOJ 2022 - Princess, a Cryptanalyst

問題 Princess, a Cryptanalyst | Aizu Online Judge 問題概要 個の文字列が与えられる.この個の文字列に対してSSS(Shortest Secret String)を求めたい.SSSとは,個の文字列を全て部分文字列として含み,なおかつその長さが最小であるような文字列のことを…

2016/5 Solved(1)

5/1 imulan.hatenablog.jp 5/2 (なにもしてない) 5/3 AOJ 2589 - North North West AOJ 1249 - Make a Sequence AOJ 2590 - Unknown Switches AOJ 2619 - Thread Tree AOJ 1193 - Chain Disappearance Puzzle AOJ 1286 - Expected Allowance 5/4 SRM 690 Div…

AOJ 2386 - Sightseeing Tour

問題 Sightseeing Tour | Aizu Online Judge 問題概要 はじめ、頂点数の完全無向グラフが与えられる。これらの無向辺をすべて、有効辺に置き換えることにした(頂点と頂点の間の辺は→か→のどちらかのみが張られる)。そのときのコストがで与えられる。全ての頂…

CF 670 E - Correct Bracket Sequence Editor

問題 Problem - E - Codeforces 問題概要 Correct Bracket Sequence(CBS)という文字列のみに対して動作するテキストエディタを考える。CBSとは、(と)の2種類の文字のみで構成される文字列であり、全てのカッコの開閉が1つ1つ対応付けられているものである((…

TCO 2015 Round 1B Hard - TheTreeAndMan

問題 TopCoder Statistics - Problem Statement 問題概要 頂点数がの根付き木を考える。そして、全ての辺は根から離れていく方向に向いている(つまり、どの個の頂点にも根からたどり着くことが可能)。頂点をそれぞれ~で番号をふる。の頂点を根とする。また、…

2016/4 Solved(2)

4/16 GCJ Round1Aに参加 Aしか解けなかった...Round2への参加権は1Bと1Cにかける... ARC 051に参加 ABの2完、Cはほとんど方針合ってたけどちょっとずれて多分オーバーフローさせてたっぽい、多分Pythonで書けばいけてたのかなあ... 4/17 yukicoder No.358 - …

TCO 2015 Round 1B Med - TheTips

問題 TopCoder Statistics - Problem Statement 問題概要 脱出ゲームみたいなもの。部屋の中に個の手がかりが隠されている。次の正方行列によって番目の手がかりを見つけると番目の手がかりを見つけられるかどうかがY/Nで書かれている。Yなら番目の手がかり…

2016/4 Solved(1)

4/1 QUPC2014 C - 案内所 mapを使う。 4/2 QUPC2014 D - 切符分割 前からと後ろからとdijkstraして、中継点を全探索する。 4/3 imulan.hatenablog.jp 4/4 k2pc-easy E - お気に入りの数2 4/5 SRM 665 Div1 Easy - LuckySum 解説の方法よりも下の桁から見てい…

TCO 2015 Round 1A Hard - Revmatching

問題 TopCoder Statistics - Problem Statement 問題概要 重み付き2部グラフが与えられる。それぞれのグループに対して、頂点数が個ある(つまり、グラフの頂点数は合計で個)。そして、次の正方行列が与えられて、は片方のグループの頂点からもう片方のグルー…

SRM 664 Div1 Easy - BearPlays

問題 TopCoder Statistics - Problem Statement 問題概要 石を積んだ柱が2本ある。最初は片方に個、もう一方に個積まれている。次のような操作を回繰り返す: 石が少ない方に、多い方から少ない方の数と同じぶんを持ってくる(つまり、X<=Yのとき、Y-=X,X+=X)…

SRM 666 Div1 Easy - WalkOverATree

問題 TopCoder Statistics - Problem Statement 問題概要 頂点数がの木が与えられる。これらの頂点には~と番号が振られている。今、をスタート地点として、この木の上を移動することを考える。ステップの移動が許されている時に、訪れることのできる頂点数の…

2016/3 Solved (2)

3/17 imulan.hatenablog.jp 3/18 CF 644 A - Parliament of Berland 市松模様をイメージしてジグザグに並べていく。 CF 644 B - Processing Queries キューに入っていく様子をシミュレーションする。キューに入ったものの先頭と取り出し、実行→その実行が終…

CF 631 D - Messenger

問題 Problem - D - Codeforces 問題概要 メッセージの履歴から自分が指定した文字列を検索したい。メッセージは特殊な形に圧縮されて送信される。そのフォーマットはというペアの列によって表される。ここで、は数字、は英小文字であり、そのペアによってと…

CF 632 C - The Smallest String Concatenation

問題 Problem - 632C - Codeforces 問題概要 個の文字列が与えられる。この個の文字列を全てを結合させることを考える。その中で辞書順最小となるものを求めよ。 文字は全て英小文字 文字列の長さの合計はを超えない。 アイデア これは割と典型なテクらしい…

2016/3 Solved (1)

3/1 imulan.hatenablog.jp 3/2 Educational CF #9に参加 ABの2完。Cで悩み続けた。Dは後で見たら出来そうだった... CODE FESTIVAL 2014 リレー F - ループを探せ 再帰を使ったDFSをしながら、根からの距離を更新しつつ、最短でない辺が見つかったらそこがル…

SRM 667 Div1 Easy - OrderOfOperations

問題 TopCoder Statistics - Problem Statement 問題概要 メモリの領域が個あるコンピュータがあり、そのそれぞれの領域にまでの番号を付ける。そのコンピュータを使って個のプログラムを実行することを考える。1つのプログラムは文字で構成されており、その…

SRM 669 Div1 Easy - SubdividedSlimes

問題 TopCoder Statistics - Problem Statement 問題概要 スライムを分割するゲームをする。最初は大きさがのスライムが1体いる。ゲームはターン制で、1ターンの内に次のことを行う: 今いるスライムの中から1体を選んで、2体に分裂させる。選んだ1体のスラ…

SRM 670 Div1 Easy - Bracket107

問題 TopCoder Statistics - Problem Statement 問題概要 (と) のみで構成された文字列が与えられる。いま、"correct bracket sequences"なる文字列を定義する。文字列全体として(の数と)の数が一致し、すべてのprefixに対して(の数のほうが)の数よりも多く…

CF 635 C - XOR Equation

問題 Problem - C - Codeforces 問題概要 2つの正の整数に関して、との和を、とのビットごとのXORをで表す。とが与えられる時、の組としてあり得る組合せの数を求めよ。 アイデア まず、に関しての全探索はサイズ的に間に合わない。そこで桁DPで試みる。 小…

2016/2 Solved (2)

2/16 ARC 010 B - 超大型連休 1年を1/1を基準とした日数の1次元配列に落としこむと、休日の設定が楽。振替休日の設定もwhileで1つずつ後ろをみていくだけで十分に間に合う(submission)。 ARC 011 B - ルイス・キャロルの記憶術 辞書型で変換表を作り、順番に…

SRM 671 Div1 Easy - BearCries

問題 TopCoder Statistics - Problem Statement 問題概要 ;_;とか;___;みたいな泣いている顔文字(両端がセミコロンで間に1つ以上のアンダーバー)をcrying emoticonと呼ぶ。文字列が与えられる時、いくつかの部分列に分解(連続でなくて良い)して、それぞれがc…

SRM 672 Div1 Easy - Procrastination

問題 TopCoder Statistics - Problem Statement 問題概要 とある巨大な会社には従業員が無限にいる。従業員には1,2,3,...と番号が振られている。番の従業員は仕事をし始める時は番のタスクを請け負っている。その会社の就業時間は無限にあり、仕事時間が1時…

SRM 673 Div1 Easy - BearCavalry

問題 TopCoder Statistics - Problem Statement 問題概要 人の戦士と体の馬がいる。それぞれに対しての番号をふる。番目の戦士、馬の強さをそれぞれ、と表す。そして、戦士1人と馬1体でユニットを組み、合計個のユニットを組むことを考える。このとき、ユニ…

CF 628 D - Magic Numbers

問題 Problem - D - Codeforces 問題概要 10進表記の数字を考えて、上から数えて偶数桁目の数が全てdで、奇数桁目の数がdではないものをd-magicであるという。a以上b以下の数字のうち、mの倍数かつd-magicであるものの個数をで割った余りを求めよ。ただし、a…

SRM 680 Div2 Hard - BearFair2

問題 TopCoder Statistics - Problem Statement 問題概要 次のような条件を満たす数字の集合が存在するか判定せよ。 集合の要素数はであり、各要素は互いに異なる正の値である。 はで割り切れる数である。 すべての要素は以上以下である。 集合の要素に関し…

ARC 025 C - ウサギとカメ

問題 C: ウサギとカメ - AtCoder Regular Contest 025 | AtCoder アイデア 方針はすぐに思いついたけど、実装でバグらせまくって時間かかったのでメモ。 まず、各頂点どうしの最短経路を求めておいた方がよさそうだな、と思いワーシャルフロイドだとかかって…

2016/2 Solved (1)

2/1 ARC 024 A - くつがくっつく ARC 024 B - 赤と黒の木 2/2 yukicoder No.338 - アンケート機能 2/3 yukicoder No.133 - カードゲーム yukicoder No.327 - アルファベット列 2/4 yukicoder No.198 - キャンディー・ボックス2 yukicoder No.144 - エラトス…