点Aを中心とする半径1,2,3,...,Nの同心円と、点Bを中心とする半径1,2,3,...,Mの同心円がある。点Aと点Bの距離がDのとき、これらの同心円によっていくつの面が作られるか答えよ、という問題。 取り敢えずM個の同心円があるとして、N個の同心円を点Aを中心に書…

多分最後の参加。アカウント消す方法誰か教えてください。 A 整数列が与えられるので、特定の区間の要素を取り出してORした結果として得られる値はいくつあるか答えよ、という問題。 ORするのでビットカウントは単調増加。なので、自分より左側に進んでもせ…

参加することにまったく意義がない...。 A N以下の整数3つのLCMの最大値を答えよ、という問題。 時間とやる気がなかったので、N-100からNの範囲を全探索しておいた。大体あってる。 B N個のBool値についてそれぞれがTrueになる確率が与えられる。連続するK個…

Codeforcesって何が面白いんだろう？？？ A ()[]からなる文字列で、それぞれの括弧の対応が取れている文字列について、一番[をたくさん含むものを答えよ、という問題。 parseしましょう系。完全に慣れの問題。やったことないと色々と大変。 B 文字列が二つ与…

最低ラインを維持するのに必死な負け犬。 A 上下対象かつ左右対称なバイナリ正方行列のうち、1が隣接しないものを考える。1の数がK個あるもののうち、最小のサイズを答えよ、という問題。 基本的には1と0を交互に敷き詰めるのが最適配置で、それ以下のKであ…

頭悪すぎやしませんかね...。 A 1ステップでA個のものがK*A+B個になるとするとき、1個のものがNステップで増えた数以上にT個のものから開始して増やすには、何ステップ必要か、という問題。 T個よりたくさんになるのにかかる最小ステップ数を計算する。その…

正答者数で配点が変動するシステム。補正としては適切な気もするけれど、順位変動が凄く気持ち悪い。 A ある文字列の部分文字列(連続である必要はないが順番を変えてはいけない)のうち、辞書順で一番後ろのものを答えよ、という問題。 後ろから見ていって、…

イマイチセット。 A 文字列が与えられるので、隣接してはいけない文字のペア(すべての文字は高々一度しかペアに現れない)集合の条件を満たすように文字を削除するときの、最小数を答えよ、という問題。 ペアの文字のみからなる文字列について、少ない方の文…

問題が途中で別物になろうが何しようが、解ける人間がいる以上、解けない方が悪いのは事実。 A ある整数から開始して、1または自分以外の約数を取り出すという処理を交互に行うことを考える。先にその処理ができなくなるのはどちらか、答えよ、という問題。 …

今年に入ってからBetaでなくなったようで。 A 0と1からなる同じ長さの文字列が二つある。スワップまたは書き換えの処理を最小回数行って、同じ文字列にせよ、という問題。 違っている数と、違い方を調べる。違い方は2通りしかないので、そのうち大きい方(小…

良く見たらDiv2の問題でしたよ、と。 問題 二分探索木のうち、ノード数Nで深さK以上のものの個数を答えよ、という問題。 解答例 DPするだけ。ノードがA個あるとき、左右に適当に振り分ける方法はA通りで、それぞれの部分木の深さは高々ノード数となるので、…

A 文字列が4つずつ与えられるので、接尾辞が一致するパターンがどのようになっているか答えよ、という問題。 やるだけ。 B 整数が与えられるので、適当に各桁の数字をスワップしたものを二個作り、加算した結果の末尾の0が一番多くなるものを答えよ、という…

問題 N以下の数のうち、0と1以外の数字を含まないものの数を答えよ、という問題。 解答例 やるだけ。1から初めて、10倍した数と10倍して1加えた数の両方を再帰的にチェックしていく。int溢れに注意するだけ。 これそのものは意味のない問題だけれど、AとBだ…

やるだけ幾何。幾何といえばdoubleの精度を気にする問題。 問題 目的地と現在乗ったばかりのバスの停留所の座標と、バスの速度と自分の移動速度が与えられる。次以降の停留所で降りるとして、目的地に最短で到達することの出来るバス停(同じ時間のものが複数…

問題 Ax+By+C=0なる形式で与えられる直線が、格子点を通るかどうか答えよ、という問題。通るなら一つ点を答える。 解答例 拡張ユークリッドの互除法をやるだけ。Ax+Byの0ではない最小値と、そのときのxとyが求まるので、Cがそれで割り切れるかどうか判定する…

簡単な問題しか解けない病気...。 問題 (または)からなる文字列が与えられるので、バランスの取れている最長区間の長さと、その長さに該当する個数を答えよ、という問題。 解答例 バランスの取れている条件は、隣にバランスの取れているものがくっつくか、(…

問題 整数列が与えられるので、最大値と最小値の差分がK以下になるように取ることができる最長の連続領域の長さを求め、それに該当する区間をすべて列挙せよ、という問題。 解答例 とにかく最初から順番にできるだけ長い領域を確保する。こうすると次に入れ…

問題 N進数の掛け算の表を作れ、という問題。細かいレイアウトはしなくて良い。 解答例 普通に標準ライブラリに整数をN進数表記に変換する、というものがある言語の方が最近は多いと思うので、それを使えば問題なし。自分で書いても大して困らないとは思うけ…

普通に大敗。最初から勝ち目のない戦いという感じではあるけれども。 A 整数配列が与えられるので、任意の要素の値を別の値に変更してソートするという操作を一度だけ行ったとき、各位置にくる値の最小値を答えよ、という問題。 とにかく一番大きい値を出来…

英語読解力と実装力のテストにはちょうど良いみたいです。 A 文字列が与えられるので、各文字間の差分をビット列で逆順にしたものを出力せよ、という問題。(意訳かつちょっと違うけど。) 英語を読んでやるだけです。 B 矩形の形状に色が塗られている盤面があ…

想定解なんて知ってるわけないじゃん...。 問題 大きさ1のものと2のものしかないナップザック問題。 解答例 大きさごとに分けて、価値の大きい順にソートしておく。詰められる量が奇数なら、大きさ1の側から一番価値の大きいものを1個詰めておく。後は、大き…

典型的な誤差について考える幾何の問題。 問題 正N角形の頂点のうちの三つが指定されるので、可能な正N角形のうち、一番小さいものの面積を答えよ、という問題。 解答例 外心を計算して、各頂点との間でなす角の角度を求めてやる。それが正N角形のNを指定し…

過去問ちょこちょこ。4桁の人が解いている問題はやる必要ないとは思う。 問題 N*MのホールをカバーするようにA*Aの布を敷きたい。布は切ってはいけない。何枚必要か答えよ、という問題。 解答例 縦に何枚、横に何枚、というのを計算して乗算するだけ。乗算の…

参加資格剥奪です、といわれても仕方ないくらいひどいスコア。 A 8x8の盤面上を、下向きに移動する物体が配置されているので、上下左右斜め移動を駆使して全部回避できるかどうか判定せよ、という問題。 やるだけ。 B 文字列が与えられるので、その任意の部…

4と7からだけなる数字のセット。以下これをLucky数として...。 A Lucky数でceilingを計算することにして、AからBまでの数のceilingの合計値を答えよ、という問題。 Lucky数を求めておいて、飛び飛びにその区間をまとめて足すだけ。 B 文字列中の47という部分…

Bでトラブルがあったらしくレートなし。なんか激しくやる気出ない...。 A N個の石がある。二人のプレイヤーはそれぞれAとBという値を心に決めていて、残っている石の数との最大公約数だけ石を取り除く。交互にプレイするとき、最後の石を取るプレイヤーを答…

今回からDiv.1だそうで。(実際にはDiv.2の大会に参加できないという制約があるだけだけど。) A 整数A,B,Nが与えられるので、A*X^N=Bなる整数Xが存在すれば、それを答えよ、という問題。 Xの絶対値はBの絶対値以下であることと、Xをかけていく過程で絶対値が…

もっとまじめにやりましょう、って感じだった。 A 既に使った値を覚えておいて、使っていない最小の値を教えてくれるマシンがある。使った値のリストが与えられるとき、そのマシンに問い合わせた結果を答えよ、という問題。 やるだけ。 B N人の人が総当たり…