問題概要 1000桁以下の数が与えられる。数が2桁以上の時、連続する2つの数字をその和で置き換える。数が1桁の時自分の番だと負け。先手が勝つか後手が勝つか判定する問題。 解法 実は戦略関係ない。なので適当に戦略を決め打ちしてシミュレーションしてやれ…

問題概要 3次方程式が与えられるので、正の根と負の根の個数を求める問題。 解法 変曲点はすぐに求まるので3分探索して極大値や極小値を求める、とかだと誤差が怖い。なので判別式使って全部整数で処理する。場合分けゲーになって甚だ不本意だけど数学系の問…

keyword 二分探索 誤差 中間値の定理 C++ 問題概要 濃度p[i]%の液体がa[i]リットルある。濃度need%の液体を最大でどれだけつくることができるか求める問題。 解法 答えに関して二分探索する。xリットルの液体を作るとき、濃度の低い順にxリットル取ってきた…

プログラミングコンテストで、特に幾何の問題とか解いてると「EPS変えたら通った」みたいなことがよくある。僕のような自分に優しい人間は「まあ本質的な部分は合ってたんだしいいか」と考えてしまいがち。この態度を「甘い」ととる人もいればそうでない人も…

問題概要 演算子の間に優先順位がないとき、計算結果は何通りに解釈できるか求める問題。演算子の個数は10以下。 解法 基本的にはただの構文解析だけど、返り値をsetにしておいて区間DPで求める。

解法 ビットDP。この手の、状態遷移でビットが立つだけ、みたいな問題は何も考えずに0から順に回してよい。集合をビットで表現したとき、包含関係が成り立つなら数値としての大小関係も満たされるから。

解法 タイトル通りにBFSする。Javaで配列をHashSetに突っ込もうとして引っかかった。

解法 やるだけ。入れ替わりとかはxorとってやればよい。

前回の記事の続き 何とか赤コーダーになれた。学生ぢから全開で時間を大量につぎ込んだだけに今回で決められてよかった。 次のRound 3は上位者が本気を出してくれる数少ない機会なので、自分も最大限誠意を持って取り組みたい。 Onsiteの12時間マラソンは時…

赤コーダーの安定感すごい。結果が出たらまた追加で書くつもり。採点システムについてとか、順位表の使い方とか、考えていたこととか。 解法の前提 small(点の数=500)は別物。smallでは最適解を目指さないと上位は厳しい。 あと、向こうのサーバはgettimeofd…

解法 間に合うので全探索で。

keyword greedy C++ 問題概要 K個のグループがある。各グループについて過半数のメンバーが賛成すればそのグループ全体の意見は賛成となる。K個のグループのうち過半数が賛成すれば全体で賛成となる。全体で賛成となるために最小何人必要か求める問題。 解法…

問題概要＝解法 母音の数を数えるだけ。

keyword Dijkstra C++ 問題概要 ノード数V( 解法 Dijkstraするだけ。各ノードまでの最短距離のうち2番めに短いものまで覚えておけばよい。実装時間15分くらい。

問題概要 最初に順番に積まれたトランプがある。ある方法でシャッフルを繰り返した時に、一番上にどれがくるかを求める問題。 解法 普通にシミュレーションしても通る。この手のシャッフルする問題を解くテクニックに、逆向きにシミュレーションして、終了時…

問題概要 数列x[i]とy[i]が与えられる(長さ8以下, 0 解法 公式の解説を参考にして解いた。文字列を前に追加するのには長さに比例したコストが必要なことを留意しないとTLEの可能性があるかもしれない。

keyword 乱択アルゴリズム C++ 問題概要 N( 解法 三角形が1つなら長さをソートして連続する3つを順に見ていけば良い。なので、問題を分割する。棒を半分に分けてそれぞれ三角形を1個ずつ作る。棒を半分に分けたとき、ただしく分割される確率は1/32なので、試…

問題概要 ノード数Nの完全グラフから、K種類の互いに辺を共有しない全域木を構成する問題。 解法 解説を参考にして実装した。円上にノードを配置してぐるぐる回すという方法で、様々な作り方があるらしい。

問題概要 配置された直方体の箱に触れないようにある線分上で玉を転がしたい。最大半径を求める問題。 解法 一目でわかる二分探索。2線分間の距離を求めるライブラリさえもっておけば楽勝。問題文やサンプルがとにかく親切。

keyword BruteForce C++ 問題概要 覆面算を解く。 解法 特に工夫せず全探索で通った。出現する文字数をMとすると、{0,..,9}のうちサイズMの部分集合を列挙しながらnext_permutationで全ての割り当てを作る。その割り当てが正しいかどうかは先頭の文字になっ…

自分がこれまでに解いたICPC国内予選の過去問をまとめてみた。古いのもあって今見返すと妙に気恥ずかしい。問題全体を眺めてみると他のコンテストに比べて実装重めな気がする。記事書いてない問題や解いてない問題もあるので解決し次第追加していく方向で。 …

keyword 平面幾何 C++ 問題概要 レーザー光を上手く反射させて最短距離で目標物に当てる問題。 解法 鏡の枚数が少なく、反射の回数に制限があるので全ての反射の場合を総当たりする。反射をまともにシミュレーションするのは大変なので、鏡にぶつかる度に鏡…

解法 x座標、y座標それぞれについて最大値と最小値を覚えておくだけ。

keyword 動的計画法 Java 問題概要 整数N( 解法 前からDPで計算量O(N^(4/3))程度。メモ化再帰だと書き方によってはスタックオーバーフローするかもしれない。 感想 ソースコード失くしたので書き直した。

keyword Dijkstra 文字列 C++ 問題概要 ノード数N( 解法 後ろからベルマンフォードとか1文字ずつ分解とかいろいろ頭の良い解法があるのは知っているけど適当に前処理をかけた後普通にDijkstraっぽく解いてみた。ただしDijkstraをそのまま適用するのはダメだ…