問題リンク： https://csacademy.com/contest/archive/task/cntgigelmat 問題概要： 0と1を含むの行列が与えられる. 主対角線と境界が全て1であるような部分正方行列の個数を数えてください. 解法： まず「対角線を結ぶ2点を固定して, 条件を満たすかどうか…
https://icpc.iisf.or.jp/2021-yokohama/icpc.iisf.or.jp ICPC2021国内予選に自分(hamray), gomatamagoさん, UさんとSA-naIStというチーム名で参加しました. 結果はAB2完の133位でした.参加記念であったり, NAISTでのICPCへの取り組みみたいなことを調べる人…
問題リンク https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1604 問題概要 次の処理を行う. 10個のスレッドのうち一つをランダムに選び命令を行う. 仮に命令が数字である場合, 他のスレッドにより数字に対応するロックが獲得されていなければそ…
リンク https://csacademy.com/contest/archive/task/critical-cells/ 問題概要 のグリッド上に個の特別なセルが存在する。 いまからまで右方向と下方向のみを使って移動するとき、できるだけ多くの特別なセルを経由したい。次の状態を満たすような特別なセ…
リンク https://csacademy.com/contest/archive/task/xor-submatrix/ 問題概要 長さの配列が与えられる。 このとき行列を次のように定義する。 xor このとき, 部分行列のxorの最大値を求める。 制約 解法 xorの性質に従って, 次の3つに場合分けをする。 1. …
問題リンク https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2447 解法 1,2階の状態を一つのグリッドで表現するのでかなり分かりにくいが, 整理するとマスの位置, 今いるフロアの階数, スイッチの状態をもってBFSをすればよいことが分かる. 少し…
2021年初投稿です。最近はProject Eulerを埋めているのでそこの問題から。 問題概要 集合 {1, 2, 3, 4} の各数字をちょうど一度用い, また四則演算 (+, －, *, /) と括弧を使うことにより, 異なる正の整数を作ることができる. 例えば, 8 = (4 * (1 + 3)) / 2…
問題リンク codeforces.com 問題概要 n*mのグリッドが与えられる. ここにk匹の魚を配置する(各グリッドに高々1匹). このときグリッド上で等確率でr*rの正方形を指定したとき, 魚の個数の期待値を最大化したい. この値を求める.制約 解法 任意の魚について, …
CodinGame FALL CHALLENGE 2020に参加しました。 https://www.codingame.com/contests/fall-challenge-2020結果は全体267位/7011, 国内67位/320でした。 初めてCodinGameのコンペに参加しましたがゴールドに到達できて嬉しいです。日本人の参加者が多く、良…
3完68位で国内予選を突破したみたいです. いまいち実感がないのですがアジア地区でも頑張りたいと思います.やったこと ずば抜けて強い人がいないので, A~Cを早く解けるように適当な年度のA~Cを解くみたいなのを2度ほどやった 個人としては、DEFが解けるよう…
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1236問題文が長いので, 概要だけ説明すると, 深さとある頂点の辺の数が与えられるので, ここからグラフを復元する問題解法 まず頂点数は正の数の総数であることが分かる. すなわち, i…
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2740&lang=jp
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2566
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2709&lang=jp
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401最大11個の変数が含まれる式が与えられるので, 常に式が成立するかチェックする. 常に, の部分は各変数の0/1をbit全探索する. 式については気合で構文解析をする.AND, OR, IMP等の…
問題リンク atcoder.jp問題概要 頭のラクダがおり, それぞれ重さが決まっている いま任意の順番にラクダを並べて, 個の橋を渡ろうとしている. 橋には長さと耐久値が決まっており, その橋に乗っているラクダの総体重が耐久値を超えた場合, 崩れてしまう. その…
www.spoj.com概要 次のいずれかのクエリがQ個与えられるので, クエリ1に対して結果を出力する クエリ0 区間l, rが与えられるので, その区間の全ての要素に1を足す. クエリ1 区間l, rが与えられるので, 3で割り切れる要素の数を出力する.
問題リンク codeforces.com問題概要 文字からなる文字列が与えられるので, を（連続でなくてもよい）部分列として含むような最小文字数の正規括弧列を出力する.正規括弧列の定義は次の通り 1. 空文字 2. ある正規括弧列が存在して, '(' A ')' のこの順に連結…
問題リンク codeforces.com問題概要 N個の要素をもつ配列が与えられる. このとき, を満たすようなについて, の最大値を求める.
最近ブログを書いてなかったので...問題リンク www.ioi-jp.org問題概要 分母がM以下であるような1未満の分数について小さい方からk番目の分数を出力する. 存在しない場合, -1を出力する.
問題リンク Problem - E - Codeforces問題概要 n*nの正方形を白か黒のどちらかで塗りつぶすとき, 次の条件を満たすものの組み合せ数を答える ・隣接する行および列は同じ色か異なる色でなければならない. （言い換えると, 白に縦1*横3と塗っている場合, その…
問題文 codeforces.com概要 n個の区間が与えられる. 区間ごとに番号をふり, 区間同士が交差するときその番号間に辺を張る. このようにしてできたグラフが木かどうか判定する.
問題リンク atcoder.jpiとwからなる文字列sが与えられる. s中の連続部分列が"iwi"となっているとき文字から削除できる（削除した後は左の文字列と右の文字列がマージされる）. このとき削除操作の最大回数を求める.
問題概要 覆面算を解く. なお以下の条件を満たしているものとする. それぞれの文字はそれぞれ独立した数字を表す が2以上のとき, Leading zeroは不可 与えられる文字列数は3以上12以下, 文字列全体に含まれる文字の種類数は1以上10以下 解法 適当な全探索コ…
atcoder.jp典型的な貪欲問題問題概要 N人の人とM個の枕がある。 N人はそれぞれ以上以下高さの枕が好みである。 それぞれの枕がせいぜい一度しか選べないとき、好みの枕を使用できる人の最大数を求める。考えたこと 制約からかが見える。とりあえず貪欲で考え…
問題リンク https://codeforces.com/contest/1003/problem/F問題概要 n個の単語が与えられる。単語同士の間に空白をおいて連結した文字列について、2つ以上の単語を連結したものを略語で表すとき最小の長さはいくつになるか。 例えば、to be or not to be な…
問題概要 無向グラフについて2点, の最短経路をとしたとき、 （ただし, ）を満たす辺を追加したときの, 間の最短経路がとなるような辺はいくつ存在するか。 各辺の重みは1とする。考えたこと いまを考えた時, を満たせばよい。 すなわち, を考えればよく, こ…
問題概要 N×Mのグリッドが与えられる。各空白マスについて上下左右を見た時、最も近いアルファベット付きマスを取り出し、同じ文字のペアが存在する場合削除する。 これを繰り返したとき最大いくつ削除できるか。考えたこと 各文字はせいぜい0か2個しか含ま…
問題概要 1~Nのマスとサイコロがある。各マスには数字が書き込まれている。 ・ が正数の時、駒をだけ進める。 ・ が負数の時、駒をだけ戻す。 ・ が0の時、サイコロを振りのいずれかに移動する。このとき1からNに到達するために必要なサイコロの振る回数は何…
問題リンク http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1249問題概要 3次元空間でTic-Tac-Toe（マルバツゲーム）を行う。x座標, y座標, z座標のそれぞれの方向ベクトルについてM個以上同じ色が隣接している場合その手を打った色が勝ちとなる…
