syamashi

atcoder(highest:1844)/42Tokyo2月1期(pass)

syamashi

atcoder(highest:1844)/42Tokyo2月1期(pass)

  • atcoder

    解説とは名ばかり。解けた人が読めばわかる怪文。

  • 42tokyo

  • 固定された記事

Hello world

ft_printf("Hello World"); 42Tokyo1期生 syamashi です。わずかな才能たよりに、情熱もって学習している畜生。 ◆プログラミング歴 2019 11月 atcoderで産声あげる（c++） https://atcoder.jp/users/merhorn 2020 2月 piscine参加（c言語）（Lv9.10突破/多分上位20%ほど） 2020 4月 atcoder 緑🐢 2020 6月 1stCircle KickOff 2020

syamashi

    • [ARC165] C - Social Distance on Graph

      [Q] https://atcoder.jp/contests/arc165/tasks/arc165_c 考察 0. 同じ色の頂点を結ぶすべてのパスのうち、最もコストの低いパスを最大化したい。 1. 適当に色を塗ってみると、3辺以上とるパスがないことに気づく。R-B-Rみたいな2辺またぎが最大。 2. 二部グラフで塗ることができれば最善で、各頂点ごとに、コストの低い2辺の和を見て、最小値をとればいい。 3. そうはいかない場合がある。辺のコストが小さい順番に辺を張ってい

      syamashi

      • [ABC320] F - Fuel Round Trip

        [Q] https://atcoder.jp/contests/abc320/tasks/abc320_f 考察 1. NとHが300なので、DP[300][300][300]でできないか考える。 2. 「ガソリンスタンドが1度しか使えない」の条件が厳しすぎる。bitset<300>で使ったスタンドを管理する、とかは無理そう。 3. なので、復路のときに、そのガソリンスタンドを使ったかどうか考える必要をなくしたい。ガソリンスタンドを見るときに、1回で往路と復路を同時に見たい

        syamashi

        • [ABC186] F - Rook on Grid

          [Q] https://atcoder.jp/contests/abc186/tasks/abc186_f 考察 1. 右下に移動した場合に、各列で何マスとるかを数列Dにすることはできる。 2. 下右に移動した場合に、各行で何マスとるかを数列Rにすることはできる。 3. 総和をとると、重複してカウントしてしまう。 4. 右下は全部加算するとして、下右のパターンで、増加分だけ加算したい。 5. 各行で0~rマスまで取るわけだけど、その中に自分のindexよりも小さいD[0]

          syamashi
        • 固定された記事

        Hello world

        syamashi

        マガジン

        マガジンをすべて見る すべて見る
        • atcoder
          syamashi
        • 42tokyo
          syamashi

        記事

        記事をすべて見る すべて見る

          [ARC123] C - 1, 2, 3 - Decomposition

          [Q]https://atcoder.jp/contests/arc123/tasks/arc123_c 考察 ・桁ごとの値を考える。 ・各桁について。1,2,3で分解したときに、最小で何個、最大で何個に分解できるかを考える。 ・上位桁がさっさと0になる分には問題ない。 ・分解回数が、上位桁の最小回数 > 下位桁の最大回数になった場合、処理できないので桁下げをする必要がある。(10とか、41とか、72とか) Q. 314 = 313 + 1にわけられる。・上位の桁を早めに

          syamashi

          [ARC123] C - 1, 2, 3 - Decomposition

          syamashi

          [AHC022] A - Exploring Another Space

          [Q] https://atcoder.jp/contests/ahc022/tasks 暫定162位でした。絶対スコアは7.0億。 絶対スコア3.3億のときに260位くらいでした。 問題の誤読 ・計測コスト = 100*(10+∣y∣+∣x∣) 質問でなげる|y|であって、座標上のyと勘違いしました。 終了前日の8/19夜にわかり、12時間チャレンジです。 考察 ・盤面を4分割、値を3通りに分ける。 だいたい、{"500 - S*3", "500", "500 + S

          syamashi

          [AHC022] A - Exploring Another Space

          syamashi

          [AGC064] B - Red and Blue Spanning Tree

          [Q] https://atcoder.jp/contests/agc064/tasks/agc064_b 解法が見えなかったので、とりあえず確実にありうることをポンポン実装していく150分だった。結果75/77ACまでしたけどダメだった。 考察 1. 条件が2つ。色条件を満たしていることと、連結であること。 色条件がかなり厳しそう。 連結かどうかは、UnionFindで適当にuniteしていけばいいから後回し。 2. N頂点に対してN-1辺しかない。 1辺で1頂点の色

          syamashi

          [AGC064] B - Red and Blue Spanning Tree

          syamashi

          [ABC314] G - Amulets

          [Q] https://atcoder.jp/contests/abc314/tasks/abc314_g レート溶けちゃった。 E,Fが苦手な期待値だったので、Gを頑張っていました。 考察 1. 入力順に処理していこうと思う。i = 0,1,…,(N-1)について、iを固定して考える。 2. type別の攻撃の総和を2つのmultisetで管理すればうまくいく。 受ける攻撃のattackedと、お守りで防ぐguardで管理。 3. 初期状態は、全部attackedに0の

          syamashi

          [ABC314] G - Amulets

          syamashi

          [AGC064] A - i i's

          [Q] https://atcoder.jp/contests/agc064/tasks/agc064_a 考察 ・しれっとあるけど、先頭と末尾の要素も条件の対象。見落としそう。 1 <= |A[L] - A[1]| <= 2 ・N=4のサンプルを活用しようと思う。 N=41 3 4 2 4 3 4 2 4 3N=5は？N=4にプラス1してみる。2 4 5 3 5 4 5 3 5 4ここに足りない値は、1,2,3,4,5。これをいい感じに配置する。A. (1) 2 4 5

          syamashi

          [AGC064] A - i i's

          syamashi

          [ABC313] E - Duplicate

          本番では問題を読むところまでいかなかった。 すんなり解けたので、n回目の問題先読みしましょうの教訓。 [Q] https://atcoder.jp/contests/abc313/tasks/abc313_e 考察 ・問題文通りの処理を行う関数を作って、法則性を見出す。 1. 22など、2以上の値が2つ並ぶと無限処理になり-1 2. 1Xのパターンが来た時に、上昇率がX倍されるようだ。 21:1212:32121:512:2121:41212:812121:1212121

          syamashi

          [ABC313] E - Duplicate

          syamashi

          [ABC311] G - One More Grid Task

          [Q] https://atcoder.jp/contests/abc311/tasks/abc311_g 考察 ・解説の2ページ目を見る。CartesianTree()を習得した。 Q. CartesianTree？ A. 数列を、最小値の二分木にするアルゴリズム。処理はO(N) A[] = {3, 1, 4, 1, 5}を考える。・rootrootはA[1] = 1が最寄りの最小値なので、1。・二分木G以下のindex分けになる。 1 0 3

          syamashi

          [ABC311] G - One More Grid Task

          syamashi

          [ABC313] D - Odd or Even

          [Q]https://atcoder.jp/contests/abc313/tasks/abc313_d いてえ結果でした。80分あがいてWAでした。 考察 ・K=1のとき ?1, ?2, …, ?Nで で簡単に特定できると思う。 ・とりあえずN通りの条件式を用意したい。 Q. K要素の連番を質問してみる。 ?123 ?234 ?345… とする場合はどうだろう？ A. ダメケースが存在する。 N=6, K=3の場合を考える。? 1 2 3? 2 3 4?

          syamashi

          [ABC313] D - Odd or Even

          syamashi

          [AGC063] B - Insert 1, 2, 3, ...

          [Q] https://atcoder.jp/contests/agc063/tasks/agc063_b 考察 ・生成可能なパターンの始まりはいつも"1"から。 ・なので1をもとにグルーピングしていく。 問題文サンプルを考える。 10 1 2 1 1 2 1 3 4 2 3 cnt: 1 0 2 3 0 4 0 0 0 0 pos: 0 0 2 3 3 5 3 3 2 2 add: 1 1 2 3 3 4 3 3 2 2 pos: どの1と同じ

          syamashi

          [AGC063] B - Insert 1, 2, 3, ...

          syamashi

          [AGC063] A - Mex Game

          [Q] https://atcoder.jp/contests/agc063/tasks/agc063_a 考察 ・AliceはBの文字を埋めたいし、BobはAの文字を埋めたい。 ・両者それぞれ、先頭に近い相手の文字を埋めていけばいい。 ・解答は、埋まっていない先頭文字が"A"ならAliceだし、"B"ならBobになる。 実装 int main() { cincout(); ll N; string S; cin >> N >> S; queue<ll> A,

          syamashi

          [AGC063] A - Mex Game

          syamashi

          [ABC310] D - Peaceful Teams

          [Q] https://atcoder.jp/contests/abc310/tasks/abc310_d 地獄の業火に90分焼かれました。 考察 こちら間違いルート。 ・10!=3628800 なので、N!*100くらいならいけそう。 ・とりあえずチーム人数の分け方は求まりそう。5人を2チームにわけるのは(1, 4)と(2, 3)の2通りだなと思うが、この道はTLEルート。間違い。 ・このあと、next_permutation()で探索かと思うが、これが、あっこの沼、深

          syamashi

          [ABC310] D - Peaceful Teams

          syamashi

          [ARC164] C - Reversible Card Game

          [Q] https://atcoder.jp/contests/arc164/tasks/arc164_c 考察 ・大きい数字が出ているカードを「裏返し」と考える。 ・シミュレーションすると、Bobがかなり有利っぽい。 ・Bobは次の2パターンしかなさそう。 1. 全部のカードの最大値をとれる 2. 1ペアだけ最大をとれない 取れないときはどんなとき？ ・場の全カードが低い値になってしまった場合、1ペアだけBobは低い値を取らざるを得ない。その後の展開はAliceが裏返した

          syamashi

          [ARC164] C - Reversible Card Game

          syamashi