問題概要 木が数直線上にN( 解法 平面走査法するだけ。ただし、確率を計算する時は0のときに注意する必要があり、またアンダーフローにも気を配る必要がある。前者は0の出現回数をカウンタで持っておき、後者は対数に落とすことによって回避可能。

問題概要 長さL( 解法 1桁目は和が10になるようにして、それ以降は和が9になるのを選ぶ。そして0が余っていたらそれを末尾につける。

問題概要 長さL( 解法 いろいろ解き方があるらしいけど、長さ40を見ると半分全列挙が思い浮かぶ。TLEが結構厳しいので、文字列のまま扱うのではなく整数にエンコードするなどしたら間に合うようになる。

問題概要 長さL[i]のうなぎがある。これをM( 解法 20を切るのが得なので、10の倍数の小さいものから優先的に処理をしていく。もっと早くとくこともできるけど、分かりやすく書くのを最優先すべき。

結果。 easy落として精神的に大ダメージを受けた。medium通したのに遅すぎてeasyだけな人に負けるという悲しいことに。 今回も割り当て遅いなーと思っていたら開始が15分遅延していた。毎回思うけどあの割り当てシステムって遅い上に結構偏っているのであま…

問題概要 素数を1文字ずつ変化させてある素数からある素数への距離を求める問題。 解法 BFSで行けるはずだけど、何故か当時の自分はDijkstraしてた。それでも十分間に合う。

問題概要 n( 解法 5で何回割れるか。

問題概要 CRCを計算する。CRC自体はいろいろあるようだけど、問題文の定義では、元のメッセージMに2byte追加してM2とする。M2を定数g(given)で割ったあまりが0になるようにする。 解法 (M

問題概要 ノード数V( 解法 Warshall-Floyd。入出力が面倒。オンラインジャッジごとに必要なスペースの数が違う。

問題概要 L問解答が提出されて、その結果がproblem-name + ( accepted | time-limit exceeded | wrong answer | runtime error)で表される。その結果をスペースごとに区切ってランダムに並び替えたものが与えられるので、acceptedな判定がいくつあったかを求…

問題概要 ノード数V( 解法 辺の数が多いので愚直にやるとTLEする。しかし、普通の辺を使うときは実は両隣に行くことだけを考えればよいことが分かる。それに気づけば辺数(M+N)程度で抑えられるのでDijkstraが間に合う。

問題概要 正整数をいくつかとってきて、sum A[i] 解法 A[i]は合成数より素数をとった方が和を減らせるので得。なのでそのような素数の組み合わせについて全探索する。あまりに愚直な探索だとTLEするので、和が150を越えないことを利用した枝刈りくらいは必要…

結果。 1完。A問題はしばらく眺めた後見なかったことにした。Bは0は最初に使えるだけ使えばよいと思ったら間違っていた。Cは走査するだけだと思って書いたら(そもそも時間かかりすぎではあるけど)アンダーフローで死んだ。その後対数使って計算したら通るこ…

結果。 順位としてはそんなに悪くないけど、通せるのを通しただけという感じはする。ただノーミスなのはよかった。今回は最終提出時刻だけを問われるタイプのコンテストだったので序盤は全部の問題と順位表見ながら眺めておくことにしていた。ああこれはWAが…

結果。 開始が遅延した回の補填。いつもより人少なかったけどやっぱり割り当ても割とギリギリだった。250が何か苦手だなーと思いつつ書き始めたらやっぱりハマる。途中解法間違ってんじゃないかと思って別の解法探すもそもそも最初に思いついてたのでよかっ…

問題概要 ロボットの動き(右を向く、左を向く、前進する)をシミュレートする。ただし、ロボットは枠から落ちることがある。枠から落ちたロボットは最後にいた位置に匂いを残す。その匂いによって、それ以降のロボットはそのマスから落ちることを防ぐことがで…

問題概要 ノード数N( 解法 終点からの最短距離が大きい順にDPする。

問題概要 決められた規則に従って文字列を出力する問題。 解法 基本的にはやるだけ。入力の読み取りが面倒(今思えばJavaでやったほうが良かった気がする)。適宜!をはさむと処理が楽になるかも。

問題概要 文字がN( 解法 辞書順といえばgreedy。基本的には先頭から辞書順に小さい方からdfsしていけばよい。ある状態から次にその文字が選べるかどうかは、残っている文字のなかで極小かどうかで判定できる。その判定も前処理でビット情報に詰め込んでおく…

問題概要 (id, solved)の組み合わせがN(バブルソートと結果が同じにならなければならない。 解法 バブルソートと同じというのは、単純に安定ソートであれば良い。なのでstable_sortを用いれば良い。ちなみに、stable_sortの実装はマージソートだったような記…

問題概要 11010010001000010...という文字列のi文字目が何か答える問題。クエリ数Q( 解法 1,2,4,7,11,16,..という数列をあらかじめ持っておいて各クエリには二分探索で処理をする。

問題概要 長さN( 解法 2回出てくる数が打ち消されるような操作をすれば良い。もう少し具体的には、自分自身が自分自身の逆元となるような演算を決めて、単位元に加えつづければ良い。そのような操作は、例えばxorで実現できる。

問題概要 長さN(過半数回以上出現する値があればそれを出力する問題。 解法 各数が何回出現したかを数えておくだけ。

結果。 UVaのやや易しめなセットでSRMのDiv2 900くらいの難易度。動的計画法中心。P9, P10は問題に制約がかかれてなかったので無視した。

問題概要 0~9の並んだ列が与えられる(長さN 解法 1,2,3桁はそれぞれ真面目にやる。4桁以上のは、下3桁が8の倍数であればよいので、下3桁を全部試してそれ以上は非ゼロな要素の個数だけ足してやればよい。

問題概要 A,B(A>B)が与えられるので、A-Bの値を10進表記して1文字だけ変更する問題。 解法 leading zeroとpositive integerに気をつけてやるだけ。

結果。 2完で、簡単なのを解いただけというひどい有様。Quizが半分全列挙で行けそうだったので2時間位チャレンジしていたけど結局通らず。しばらく書いてから計算量危ういことに気づいて(嘘でない)枝刈りで高速化したけど、TLEでなくてWAが帰ってきて悲しか…

問題概要 次数に対するスコアが与えられる。ノード数N( 解法 1~Nの組み合わせで次数の合計が2*(N-2)になるように選ぶ。そのような次数列を持つ木が作れることは帰納的に示せる。

問題概要 0or1の行列(サイズ30*30以下)が与えられて、いくつかのマスには?が入っている。また、各列を適当に置換したものが与えられる。これにも?が入っている場合がある。?を適当に埋めて辞書順最小のものを求める問題。 解法 辞書順最小の定石どおり先頭か…

結果。 久しぶりの完全敗北。Easyが提出すらできなかった。Mediumは問題文を誤読していて、ただしく認識したら二部マッチングするだけなのは一瞬で見えたけど残り2~3分とかじゃきつかった。すごく勿体ない。問題名に謎のP8Xというのがついてたけど意味がよく…