裏紙

ほぼ競プロ、たまに日記

solved

2018/9 solved(1)

9/1 CF 1029 F - Multicolored Markers まず、全体が長方形にならないといけないので面積がa+bの長方形ができる必要があり、その全パターンは約数の個数に一致するので、まずa+bの約数を列挙し、それらが実現可能かをそれぞれチェックする。以下、h*wの長方…

2018/8 solved(2)

8/17 8/18 CF 980 C - Posterized 辞書順最小→貪欲(submission)。 CF 980 D - Perfect Groups 同じグループにできるのは、正負が一致かつ素因数の個数の偶奇が一致するものが同じグループにすることができる。ただし、0だけは特別扱いする必要があり(0はどの…

2018/8 solved(1)

8/1 CF 992 A - Nastya and an Array 8/2 CF 992 B - Nastya Studies Informatics まず、lcmとgcdの関係から、xy = abが成り立ってないといけないが、これを満たすようなaの個数は約数の個数で抑えられており、それはlogで抑えられていると考えれば、xとyを…

2018/7 solved(2)

7/17 imulan.hatenablog.jp 7/18 CF 1009 A - Game Shopping CF 1009 B - Minimum Ternary String 1が自由に動けて、0と2の順序はどう頑張っても入れ替えられないことに注目すれば、2の後に来る0を境目として0...01...12...2のような文字列が繰り返されるこ…

2018/7 solved(1)

7/1 JAG 国内模擬 に参加 6完だった。Gも考察はできてて、サンプルも合ったんだけど、間に合わせられず...国内予選のリハーサルをできて動きを確認した(両面印刷はやめよう)。 ARC 100 に参加 久々に参加した。もっと時間作って参加したいんだけど、どうして…

2018/6 solved(2)

6/16 AOJ 1238 - True Liars V(=T+L)人いるときに、頂点数2Vのグラフを作る(各頂点は、i番目の人がdivine/devilに対応)。すると、与えられる情報から、2本の辺を貼ることができる。x,y,"yes"なら、xのdivineとyのdivine、xのdevilとyのdevilの間に辺をはり、…

2018/6 solved(1)

6/1 6/2 6/3 AOJ 2729 - Delete Files 長さが短い方から注目して消していくことを考えると、残ってる中で一番短いのを消すことを考えるときには、矩形の左側はそれを含むように取れる必要がある。あとは、それを上下にどれくらい伸ばせるかをチェックして、…

2018/5 solved(2)

5/17 AOJ 1281 - The Morning after Halloween 今3体がどこにいるかをkeyにしてBFS/DPをする。一見間に合わなさそうに見えるが、壁が多いのでなんだかんだ探索範囲は狭くなる。(submission)。 5/18 AOJ 2596 - Points and Lines 区間に対して、再帰的に計算…

2018/5 solved(1)

5/1 AOJ 1360 - Bringing Order to Disorder 和と積と大小関係を情報に持ちながら桁dpする。積の部分は、大きい値になりうるけどsparseなのでmapで管理する(submission)。 AOJ 1331 - Let There Be Light 各光源に対して、光を到達させるために取り除くべき…

2018/4 solved(2)

4/16 AOJ 1312 - Where's Wally 2次元ロリハのverify(submission)。 CF 938 A - Word Correction 4/17 CF 938 B - Run For Your Prize CF 938 C - Constructing Tests 4/18 CF 938 D - Buy a Ticket 初めに初期値を全部突っ込んでおいてdijkstraする。dijkst…

2018/4 solved(1)

4/1 AOJ 2326 - Number Sorting dp[i] := iがsubsetの中で最大になるような適切な選び方は何通りあるかを計算する。このとき、文字列でソートされた順でiを処理していくと、i未満の部分のdpの和を取ることでdp[i]の値を得ることが出来るので、部分和を高速に…

2018/3 solved(2)

3/16 yukicoder No.235 - めぐるはめぐる (5) HL分解を使って解く。そこよりもどういうSegmentTreeを作るかに時間がかかった。区間Addをするが、そのAddに頂点ごとに異なる係数がかかるので、一様にAddできない、どうしようってなった。ただ、区間sumを求め…

2018/3 solved(1)

3/1 CF #411(Div.1) Virtual ABCの3完。Cの解釈に時間掛けすぎたけど、木という条件を利用することでクリークがそれ以上大きくならないというふうに考えることができ、色は貪欲に決まる。Dも途中までは考察できてたので、Dは解説見ずに通したい。 3/2 3/3 3/…

2018/2 solved(2)

2/15 imulan.hatenablog.jp CF #416(Div.2) Virtual ABCDの4完。Bはちゃんと愚直ソートを殺すケースが入っていた(ひっかかった)。 2/16 imulan.hatenablog.jp CF 895 D - String Mark それぞれの文字列a,bに対して、strictlyに辞書順で小さいaのpermutation…

2018/2 solved(1)

2/1 imulan.hatenablog.jp 2/2 CF 894 A - QAQ CF 894 B - Ralph And His Magic Field よくわからなかったけど、実験してみると規則性があったのでそれを実装した。 考え方としては、まず全てのセルには1か-1しか置くことが出来ない。その上で、k=-1のとき、…

2018/1 solved(2)

1/17 ARC 083 C - Sugar Water 水の量と砂糖の量を全探索する。砂糖の量は、bool配列などにその量が作れるかを持っておけば計算量的にOK(submission)。 ARC 083 D - Restoring Road Network Warshall-Floyd法によって、最短距離を計算して、入力と一致するか…

2018/1 solved(1)

一昨年やってたのを復活させます。去年は「これあんまり意味ないかもなあ、もっとちゃんと解説書く問題を増やしたほうがいいでしょ」と思ったが、辞めた結果そもそも解説書く問題が減った(ダメ)。他人に読んでもらうことは特に意識せず書きます。 1/1 AOJ 20…

2016/12 solved(2)

12/17 yukicoder No.467 - 隠されていたゲーム Wikipediaの画像ながめて、正方形の周上に移動できるのかーってなったときに、最大のdの内側に入ってるなら2回でどこでもいけるのではという事に気づいてからは場合分けで一瞬だった... AOJ 2601 - Evacuation …

2016/12 solved(1)

12/1 yukicoder No.450 - ベー君のシャトルラン 往復したりなんだりでなんだかややこしそうに見えるが、結局シャトルランを続ける時間は2つの電車が出会うまでなので、その時間は簡単に求められる。その時間が求まれば総移動距離も簡単に分かる。 POJ 3293 -…

2016/11 solved(2)

11/16 AOJ 0282 - Programming Contest segtreeを使って最大得点のチームを管理。 AOJ 0269 - East Wind 愚直にシミュレーション。香りが届くかどうかの判定は、距離チェックと角度チェックをそれぞれすればよい。 AOJ 0221 - FizzBuzz シミュレーションすれ…

2016/11 solved(1)

11/1 CF #378(Div2)に参加 ABCDの4完だった。codeforcesは実装に罠が多い問題が多いような感じがしてきた。今回はちゃんと出したやつを全部通せたけど、実装方針とかは場数がどうしても必要になる感じがある。ここで紫に到達。 AOJ 2758 - Sendame AOJ 2759 …

2016/10 solved(2)

10/17 imulan.hatenablog.jp ARC 021 C - 増築王高橋君 まず、個の家に対して、どこまで増築していいか値段を二分探索する。が大きいので、それぞれの家に増築の回数を1回ずつ余地を残すために回以下の増築が許されるところを探索して、それがおわったらそこ…

2016/10 solved(1)

10/1 CF 721 C - Journey 方針自体は(現在地,訪れた超点数)=かかる時間の最小値というシンプルなDPだったのだけど、queueとBFSで実装してしまい本番はMLEで死んだ。dfsに書き直して様々な修正をしてようやくできた(submission)。 CF 721 D - Maxim and Array…

2016/9 solved(2)

9/16 ABC 045 A - 台形 / Trapezoids ABC 045 B - 3人でカードゲームイージー / Card Game for Three (ABC Edit) 最近簡単な問題を意識してPythonで解いている。 9/17 imulan.hatenablog.jp 9/18 CF 716 A - Crazy Computer ただシミュレーションしていく。 …

2016/9 solved(1)

9/1 CSAcademy - Addition CSAcademy - Great Common Divisor CSAcademy - Matrix Exploration CSAcademy Tasksのチュートリアル的3問。3問目は個の点を始めにqueueに入れてBFSすればよい。 9/2 CSAcademy #1 - Word Ordering CSAcademy #2 - Word Permutati…

2016/8 Solved(2)

8/17 ABC 043 A - キャンディーとN人の子供イージー / Children and Candies (ABC Edit) ABC 043 B - バイナリハックイージー / Unhappy Hacking (ABC Edit) 8/18 WUPC2nd A - 団子とうさぎ 和の公式と剰余. WUPC2nd B - 雨上がり 最低限踏む水たまりの数を…

2016/8 Solved(1)

8/1 AGC 002 D - Stamp Rally UnionFindと二分探索を「クエリ全部に同時並行的に」行っていく.まず,クエリが1つだったときのことを考えてみるとこの兄弟はスコアi以内で収まるかどうかというものを判定しながら二分探索していくことになる.その際に,i番…

2016/7 Solved(2)

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

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で割り切れないことが条件になっている)…