問題概要 サイト名がN(閾値以上含むサイトは危険であると判定され、そのサイトに含まれる全てのキーワードは危険なキーワードに追加される。危険なサイトを全て答える問題。 考えたこと (本番もひたすらアルゴリズムをシミュレートして通した記憶がある) 与…

問題概要 AとBの絶対パスが与えられるのでAから見たBの相対パスを返す問題。 考えたこと 一瞬LCAかと思ったがそこまで面倒な話ではない。 先頭から順に一致する部分を削って、いくつ戻るかカウントして../を付け加え、その後行き先の末尾をくっつけてやれば…

問題概要 ふたつの集合A, Bが与えられる。集合Aに、値を加える、値を減らす、値を変えるなどの操作をして最短手数でBと等しくなるようにする問題。 後から考えたこと 何か全然やる気が出なくてさっさと答えを見てしまった…。 何があっているか、は重要ではな…

問題概要 二次元配列A[i][j]が与えられる。A.length=N( 考えたこと これ必ず解がユニークに存在するのか？ 下から復元できるからユニークに復元できる。そしてそれが分かればその通りに実装すればよい。 updateを検出する書き方で書いたけど、左から右に舐め…

問題概要 長さN(jかつA[i] 考えたこと 長さ短いしvectorをキーにしたメモ化再帰で行ける？ 状態はループしないだろうか。 転倒数が単調減少なのでDAGになる。行ける。 後は書くだけ。無事通った。

問題概要 0,1,...,N(N 考えたこと (本番はO(N)でTLEした記憶がある。定数倍の速度差に負けた)。 TLE厳しいので、本意ではないが真面目に早いのを書こう。 基本的にはgreedy。後ろから7席置きに選んでいけばよい。 補充や配るのにかかる時間は先に計算してお…

問題概要 都市がN( 考えたこと (今でもかなり好きな問題の一つ。当時は通せなかったけどこのとき初めてDijkstraを書いた) 最小値の最大化なのだから定石は二分探索。 滞在時間の最小値を固定したらあとは移動時間T以下にできるかはDijkstraで判定できる。 解…

問題概要 [A,B](1 考えたこと なんか最近のDiv1 EasyでTheAlmostLuckyNumbersとかいう問題を見た気がする。それの簡単バージョン。 dfsで書いた。本当に書くだけすぎる…。

問題概要 数列Bが与えられる。あなたは次のような長さL( 考えたこと factor 1234567891でちゃんと素数になっていることを確認。 これ最後の数字を覚えておくだけでよいのではないだろうか。 4.*7とか4.*4とかの個数を数えておけば、ごくごく簡単な漸化式にな…

問題概要 N( 考えたこと (当時は手も足もでなかった。何か当時O(3^N)とか言ってたような記憶がおぼろげにある) N=15は確かに3^Nのような気もするけど、よく分からんのであまり気にしないようにしよう。 しばらく考えて、一度空や満杯になったビンは以降触る…

問題概要 今の値をxとする。xに対してx = (4*x+3)%MOD or x = (8*x+7)%MODという操作を施す。最低何回で0にできるか求める問題。MAX=10^5回やってたどり着けなかったら-1を返す。 考えたこと (この問題は記憶にあるしネタも覚えているけど当時通していたかど…

問題概要 a[0]=1, b[0]=1である。a[n+1]=b[n], b[n+1]=a[n]+b[n]、ただし、いくつかのnについてはb[n+1]=a[n]/2である。a[K]+b[K]をmod 10^9+9(=:P)で求める問題。K 考えたこと (当時は行列計算実装している間に終わった記憶がある) 漸化式の形に落とすこと…

問題概要 長さL( 考えたこと (当時はシミュレーションをひーひー言いながら通した記憶がある。その後editorialで綺麗な解答に感心した) これは解き方覚えてる。偶奇のマスは干渉しないし、うさぎは2匹ずつ消えるので偶奇のマスにいるうさぎの数を数えて、そ…

問題概要 辺に重みの付いた連結な無向グラフが与えられる(V 考えたこと (当時この問題見てたかどうかまったく記憶にない) とりあえず0からの最短路を求めよう。これはサイズ小さいからWarshall-Floydでいいや。 Dijkstraとか面倒だし… 0からの距離が近い順に…

問題概要 N( 考えたこと (何か見たことはあるけどもはや通したかどうかとか覚えていない) vectorをセットに突っ込んでいく？でもNがでかいから無理っぽい。 どうせほとんど0なんだから座標圧縮すれば良い。 一番実装が楽なのはmapをsetに突っ込むことだろう。…

問題概要 a,b,c( 考えたこと ビットで最小なんだから、本質的には辞書順最小。 すなわちgreedy。定石どおり考えると、cのビットを上から見ていってできるだけビットを使わないようにすれば良い。 ある桁でビットを立てるかどうか考えると後は再帰的に同じ問…

問題概要 整数集合A( 考えたこと 全探索は1000^3だけどこれは処理軽いから行ける気がする。 でも上限1000じゃないのか、まあ2000位まで調べてやれば大丈夫だろう。あと数が大きくなりすぎたら適当に打ちきるとか。 あとは書くだけ。無事通った。 予想通り100…

平日昼間の開催だったけれど、ちょうどhasi君が研究室の近くに来ていたのでふたりでチームを組んで参加した。これまではチーム名をICPCの頃の名残りでImoにしていることが多かったけど、imos君がいなくなってしまったので新しくチーム名をPotatoにしてみた。…

問題概要 H*W(H*W 答え 二次元RMQのライブラリ確認用にちょろっと投げるつもりだったけど、メモリ制約が非常に厳しく(普通にsegment treeでRMQを実装したら微妙に足りない)想定解法以外を許さない強い意志が感じられた。でも自分がやりたいのはライブラリの…

問題概要 円周上に等間隔にN( 考えたこと (当時はリストを使って実装して二分探索をやってTLEした記憶がある。リストはランダムアクセスが遅いので二分探索が意味を持たない) 直角三角形を求めるパートは簡単だ。円周角の定理より中心を通る線を選べば良い。…

問題概要 右を向く、左を向く、一歩進むという命令列がある。この命令列を無限に繰り返したとき移動範囲は有限になるかどうかを判定する問題。 考えたこと (当時はdyの値を間違えて-25をとってしまった記憶がある) コマンド列を4回繰り返したら必ず前を向く…

問題概要 N(有理数で、分母がN以下であるようなものが何通りあるか求める問題。テストケース10^6くらい。 考えたこと 即数列検索。 ヒット。何かΦ関数が見える。 言われてみればそれは自明。漸化式a[1]=2, a[i] = a[i-1] + card({x in [1..i] | xとiは互いに…

問題概要 A[i] = (e[i], s[i]), B[i] = (ee[i], ss[i])が与えられる(N 考えたこと DP臭がする。あとこれ入力で名前読み取る意味ないよね…。 シークレットとスタンダード(概要中のA, B)を別個に考えてよい気がする。 それぞれ、費用いくらのときの最大の満足…

問題概要 二次元ボード(W,H 考えたこと また随分と入力が読み取り辛いですなあ。 こんなん毎回幅優先すればいいでしょう。基本的には数字の大きいところからDP。 TLE。 幅優先するまでもなくマンハッタン距離でいいのか。修正。無事AC。 今考えると別に後ろ…

問題概要 頂点数N(B->Cという経路の最短路を求める問題。 考えたこと どう見てもただの最短路。途中によるとかはdist(A,B) + dist(B,C)を答えるだけでよい。 入力がやたら面倒くさい。頂点は文字列で与えられるしコストはx/40+yという辺な形になってるし…。 …

問題概要 [0,M]内におけるA[i](i 考えたこと 問題文が長くてうげー。 最初入力勘違いしていて一人が受け持つ問題が複数あると思ってた。 それでも整数の分割でサイズが小さければ解けそう。 ひとり一問なら単なるシミュレーションでよい。 最後の一人を特別…

問題概要 長さL( 暗号化の手順 a, b(0 b-aだけスワップさせた文字を逆方向にrotする。 考えたこと 後ろからシミュレーションするだけ。 何かサンプルの最後が合わない…。 アスキー記号だと後ろに大文字があるからオーバーフローは起きないはずなんだけどなあ…

問題概要 長さM( 考えたこと B[i] - A[i] Cが単調増加ということは最初にCでソートしておけばOK。 復元は直前の状態を覚えておけばよいから、総和を値としたDPか。 最小必要な状態は(いくつ目、何番目に選んだか、今のXの値)。もちろん今のXの値はa[i]からの…

問題概要 長さN( 考えたこと 答えが浮動小数点数だけど、合計点で考えればよいので実質整数でできる。 まだ不定なカードがあるとしたら、残ってるうち小さい方(大きい方)から貪欲に選んでいけばよい。 サブミット。wrong answer pretest 1。サンプル通って無…

問題概要 ふたりのプレイヤーがゲームをする。それぞれある値A,Bを持っている。今、山にN( 考えたこと いつも思うけど、こういうのはゲームと言わないと思う。あえて言うなら作業ゲー。 とはいえ、そう書かれていた方が問題文は理解しやすいのだけど。 シミ…