けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

2019-03-06から1日間の記事一覧

AOJ 3053 Phone Number (RUPC 2019 day2-C)

一瞬詰まった。とりあえず 9! できるなと思ったあと、長さ の文字列を処理するのはどうするんだろ...となっていた。前処理が本質な感じがする。 問題へのリンク 問題概要 "31415926535" のような 1 〜 9 からなる長さ の文字列 が与えられる。 今、 137 456 …

AOJ 3052 Milk (RUPC 2019 day2-B)

難しかった 問題へのリンク 問題概要 ちょうど 本の牛乳の空き瓶を持っていくと新たに 本の牛乳の入った瓶と交換できる。 最初に 本の牛乳の入った瓶を持っているとき、最大で何本分の牛乳を飲めるかを 1000000007 で割ったあまりを求めよ。 制約 < 考えたこ…

AtCoder World Tour Finals 2019 A - Magic (1000 点)

世界大会で注意力を問う罠枠だったのかな 問題へのリンク 問題概要 個の箱があってそのうちの一つに財宝が入っている。箱を 1 個 1 個開けて行くことで財宝を見つけたい。ただし、財宝が入っている箱を開けようとすると最大 回、財宝が他の箱に瞬間移動して…

AOJ 2903 Board (AUPC 2018 day1-H)

2 変数劣モジュラ関数の和を最小カットで表すという、とても面白い問題!!! 問題へのリンク 問題概要 × の二次元ボードが与えられる。以下のような "#" のところを最小個数の長方形で敷き詰めよ。例えば 4 10 ########## ....#..... ....#..... ..........…

AOJ 2939 オセロ (RUPC 2019 day1-C)

めちゃ面白い! 問題へのリンク 問題概要 オセロにおいて、黒石が 1 個だけない状態からスタートする。 ........ ........ ........ ...ox... ....o... ........ ........ ........ ここから通常のオセロルールでプレイする。今、 個のクエリが投げられ、各…

AOJ 2940 場所当てゲーム (RUPC 2019 day1-D)

発想はすごくシンプルで、実装頑張る 問題へのリンク 問題概要 整数 が与えられる。 ラウンドのインタラクティブゲームを行う。 まずあなたは 頂点の無向単純グラフを 1 つ作成して出力する。 相手はそのグラフを受け取り、各ラウンドのはじめに、いずれか 1…

AOJ 2943 イルミネーション (RUPC 2019 day1-G)

燃やす埋めるは今度こそちゃんとマスターする!!! 問題へのリンク 問題概要 × の各格子点に電球がある。 が偶数となるような について、 を頂点とする正方形の中心に装置があって、各装置を押すことで四隅の電球を点灯することができる。 ただし、装置を起…

AOJ 2941 LISum (RUPC 2019 day1-E)

最長増加部分列 (LIS) がセグ木上のインライン DP で求められることを思い出せば、それを少し頑張るとできる。 問題へのリンク 問題概要 長さ の数列 が与えられる。数列 の最長増加部分列 (狭義単調増加) のうち、その総和の最大値を求めよ。 制約 考えたこ…

AOJ 2942 Absum (RUPC 2019 day1-F)

難しくて、てんぷらたんが天才だった!!!!!!! とにかくすごかった!!!!! そしてすごく面白い問題だった!!!!! 問題へのリンク 問題概要 長さ の数列 が与えられる。数列の 2 要素を選んで swap する操作を高々 回まで行うことができる。 操作…